Google
Google Scholar
Semantic Scholar
MS Academic
CiteSeerX
ORCIDEmanuele Viola
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2021
[i79]Timothy Gowers, Emanuele Viola:
Mixing in non-quasirandom groups. Electron. Colloquium Comput. Complex. 28: 17 (2021)- 2020
- [j42]Emanuele Viola:
Sampling Lower Bounds: Boolean Average-Case and Permutations. SIAM J. Comput. 49(1): 119-137 (2020) - [j41]Chin Ho Lee, Emanuele Viola:
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials. Theory Comput. 16: 1-50 (2020) - [c40]Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. SODA 2020: 426-445 - [i78]Emanuele Viola:
New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Colloquium Comput. Complex. 27: 15 (2020) - [i77]Emanuele Viola:
Fourier conjectures, correlation bounds, and Majority. Electron. Colloquium Comput. Complex. 27: 175 (2020) - [i76]Xuangui Huang, Emanuele Viola:
Average-case rigidity lower bounds. Electron. Colloquium Comput. Complex. 27: 193 (2020)
2010 – 2019
- 2019
- [j40]W. T. Gowers, Emanuele Viola:
Interleaved Group Products. SIAM J. Comput. 48(2): 554-580 (2019) - [j39]Emanuele Viola:
Guest Column: Non-abelian Combinatorics and Communication Complexity. SIGACT News 50(3): 52-74 (2019) - [j38]Emanuele Viola:
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds. Theory Comput. 15: 1-9 (2019) - [j37]Emanuele Viola:
Constant-Error Pseudorandomness Proofs from Hardness Require Majority. ACM Trans. Comput. Theory 11(4): 19:1-19:11 (2019) - [j36]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence versus Symmetric Tests. ACM Trans. Comput. Theory 11(4): 21:1-21:27 (2019) - [i75]Emanuele Viola, Omri Weinstein, Huacheng Yu:
How to Store a Random Walk. CoRR abs/1907.10874 (2019) - [i74]Emanuele Viola:
Pseudorandom bits and lower bounds for randomized Turing machines. Electron. Colloquium Comput. Complex. 26: 51 (2019) - [i73]Xuangui Huang, Emanuele Viola:
Approximate Degree-Weight and Indistinguishability. Electron. Colloquium Comput. Complex. 26: 85 (2019) - [i72]Emanuele Viola:
Matching Smolensky's correlation bound with majority. Electron. Colloquium Comput. Complex. 26: 175 (2019) - 2018
- [j35]Emanuele Viola, Avi Wigderson:
Local Expanders. Comput. Complex. 27(2): 225-244 (2018) - [j34]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reduction. Inf. Comput. 261: 281-295 (2018) - [j33]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. SIAM J. Comput. 47(2): 493-523 (2018) - [j32]Chin Ho Lee, Emanuele Viola:
The Coin Problem for Product Tests. ACM Trans. Comput. Theory 10(3): 14:1-14:10 (2018) - [c39]Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs. FOCS 2018: 956-966 - [c38]Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. ICALP 2018: 25:1-25:14 - [i71]Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. CoRR abs/1803.02270 (2018) - [i70]W. T. Gowers, Emanuele Viola:
Interleaved group products. CoRR abs/1804.09787 (2018) - [i69]Emanuele Viola:
Sampling lower bounds: boolean average-case and permutations. Electron. Colloquium Comput. Complex. 25: 60 (2018) - [i68]Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola:
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. Electron. Colloquium Comput. Complex. 25: 61 (2018) - [i67]Emanuele Viola:
Constant-error pseudorandomness proofs from hardness require majority. Electron. Colloquium Comput. Complex. 25: 133 (2018) - [i66]Emanuele Viola:
Lower bounds for data structures with space close to maximum imply circuit lower bounds. Electron. Colloquium Comput. Complex. 25: 186 (2018) - [i65]Emanuele Viola:
AC0 unpredictability. Electron. Colloquium Comput. Complex. 25: 209 (2018) - 2017
- [j31]Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. Comput. Complex. 26(2): 323-364 (2017) - [j30]Emanuele Viola:
Selected challenges in computational lower bounds. SIGACT News 48(1): 39-45 (2017) - [j29]Chin Ho Lee, Emanuele Viola:
Some Limitations of the Sum of Small-Bias Distributions. Theory Comput. 13(1): 1-23 (2017) - [c37]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. Computational Complexity Conference 2017: 14:1-14:30 - [i64]Chin Ho Lee, Emanuele Viola:
The coin problem for product tests. Electron. Colloquium Comput. Complex. 24: 90 (2017) - [i63]Emanuele Viola:
A sampling lower bound for permutations. Electron. Colloquium Comput. Complex. 24: 166 (2017) - [i62]Chin Ho Lee, Emanuele Viola:
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Electron. Colloquium Comput. Complex. 24: 167 (2017) - 2016
- [j28]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. Algorithmica 74(1): 326-343 (2016) - [j27]Emanuele Viola:
Quadratic Maps Are Hard to Sample. ACM Trans. Comput. Theory 8(4): 18:1-18:4 (2016) - [c36]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence vs. Moduli. APPROX-RANDOM 2016: 24:1-24:9 - [c35]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. CRYPTO (3) 2016: 593-618 - [c34]W. T. Gowers, Emanuele Viola:
The Multiparty Communication Complexity of Interleaved Group Products. FOCS 2016: 289-294 - [i61]Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded independence vs. moduli. Electron. Colloquium Comput. Complex. 23: 102 (2016) - [i60]Timothy Gowers, Emanuele Viola:
The multiparty communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. 23: 127 (2016) - [i59]Emanuele Viola, Avi Wigderson:
Local Expanders. Electron. Colloquium Comput. Complex. 23: 129 (2016) - [i58]Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded independence plus noise fools products. Electron. Colloquium Comput. Complex. 23: 169 (2016) - [i57]Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). IACR Cryptol. ePrint Arch. 2016: 343 (2016) - [i56]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. IACR Cryptol. ePrint Arch. 2016: 565 (2016) - 2015
- [j26]Emanuele Viola:
The communication complexity of addition. Comb. 35(6): 703-747 (2015) - [j25]Eric Miles, Emanuele Viola:
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. J. ACM 62(6): 46:1-46:29 (2015) - [j24]Eric Miles, Emanuele Viola:
On the Complexity of Constructing Pseudorandom Functions (Especially when They Don't Exist). J. Cryptol. 28(3): 509-532 (2015) - [c33]Oded Goldreich
, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Computational Complexity Conference 2015: 601-668 - [c32]Hamid Jahanjou, Eric Miles, Emanuele Viola:
Local Reductions. ICALP (1) 2015: 749-760 - [c31]Timothy Gowers, Emanuele Viola:
The communication complexity of interleaved group products. STOC 2015: 351-360 - [i55]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. 22: 3 (2015) - [i54]Chin Ho Lee, Emanuele Viola:
Some limitations of the sum of small-bias distributions. Electron. Colloquium Comput. Complex. 22: 5 (2015) - [i53]Timothy Gowers, Emanuele Viola:
The communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. 22: 44 (2015) - [i52]Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson:
Bounded Indistinguishability and the Complexity of Recovering Secrets. Electron. Colloquium Comput. Complex. 22: 182 (2015) - [i51]Emanuele Viola:
Quadratic maps are hard to sample. Electron. Colloquium Comput. Complex. 22: 205 (2015) - 2014
- [j23]Emanuele Viola:
Randomness Buys Depth for Approximate Counting. Comput. Complex. 23(3): 479-508 (2014) - [j22]Emanuele Viola:
Extractors for Circuit Sources. SIAM J. Comput. 43(2): 655-672 (2014) - [c30]Eli Ben-Sasson, Emanuele Viola:
Short PCPs with Projection Queries. ICALP (1) 2014: 163-173 - [i50]Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola:
Global Information Sharing under Network Dynamics. CoRR abs/1409.7771 (2014) - [i49]Eli Ben-Sasson, Emanuele Viola:
Short PCPs with projection queries. Electron. Colloquium Comput. Complex. 21: 17 (2014) - [i48]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Succinct and explicit circuits for sorting and connectivity. Electron. Colloquium Comput. Complex. 21: 37 (2014) - 2013
- [j21]Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola:
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates. IEEE Trans. Inf. Theory 59(10): 6611-6627 (2013) - [j20]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On Beating the Hybrid Argument. Theory Comput. 9: 809-843 (2013) - [j19]Alexander A. Razborov, Emanuele Viola:
Real Advantage. ACM Trans. Comput. Theory 5(4): 17:1-17:8 (2013) - [c29]Emanuele Viola:
The communication complexity of addition. SODA 2013: 632-651 - [c28]Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola:
On the Complexity of Information Spreading in Dynamic Networks. SODA 2013: 717-736 - [c27]Eric Miles, Emanuele Viola:
Shielding circuits with groups. STOC 2013: 251-260 - [i47]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. CoRR abs/1305.3827 (2013) - [i46]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. CoRR abs/1311.3171 (2013) - [i45]Emanuele Viola:
Challenges in computational lower bounds. CoRR abs/1311.5467 (2013) - [i44]Eric Miles, Emanuele Viola:
Shielding circuits with groups. Electron. Colloquium Comput. Complex. 20: 3 (2013) - [i43]Zahra Jafargholi, Emanuele Viola:
3SUM, 3XOR, Triangles. Electron. Colloquium Comput. Complex. 20: 9 (2013) - [i42]Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Local reductions. Electron. Colloquium Comput. Complex. 20: 99 (2013) - [i41]Emanuele Viola:
Challenges in computational lower bounds. Electron. Colloquium Comput. Complex. 20: 119 (2013) - [i40]Eric Miles, Emanuele Viola:
Shielding circuits with groups. IACR Cryptol. ePrint Arch. 2013: 1 (2013) - 2012
- [j18]Shachar Lovett, Emanuele Viola:
Bounded-Depth Circuits Cannot Sample Good Codes. Comput. Complex. 21(2): 245-266 (2012) - [j17]Emanuele Viola:
The Complexity of Distributions. SIAM J. Comput. 41(1): 191-218 (2012) - [j16]Emanuele Viola:
Bit-Probe Lower Bounds for Succinct Data Structures. SIAM J. Comput. 41(6): 1593-1604 (2012) - [c26]Emanuele Viola:
Extractors for Turing-Machine Sources. APPROX-RANDOM 2012: 663-671 - [c25]Eric Miles, Emanuele Viola:
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. CRYPTO 2012: 68-85 - [c24]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. ITCS 2012: 468-483 - [c23]Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola:
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. STOC 2012: 479-494 - [i39]Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). Electron. Colloquium Comput. Complex. 19: 19 (2012) - [i38]Emanuele Viola:
Extractors for Turing-machine sources. Electron. Colloquium Comput. Complex. 19: 47 (2012) - [i37]Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. Electron. Colloquium Comput. Complex. 19: 125 (2012) - [i36]Alexander A. Razborov, Emanuele Viola:
Real Advantage. Electron. Colloquium Comput. Complex. 19: 134 (2012) - [i35]Rocco A. Servedio, Emanuele Viola:
On a special case of rigidity. Electron. Colloquium Comput. Complex. 19: 144 (2012) - [i34]Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. Electron. Colloquium Comput. Complex. 19: 160 (2012) - 2011
- [j15]Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola:
Special Section on Foundations of Computer Science. SIAM J. Comput. 40(3): 770 (2011) - [j14]Emanuele Viola:
Selected Results in Additive Combinatorics: An Exposition. Theory Comput. 3: 1-15 (2011) - [c22]Shachar Lovett, Emanuele Viola:
Bounded-Depth Circuits Cannot Sample Good Codes. Computational Complexity Conference 2011: 243-251 - [c21]Emanuele Viola:
Extractors for Circuit Sources. FOCS 2011: 220-229 - [c20]Emanuele Viola:
Randomness Buys Depth for Approximate Counting. FOCS 2011: 230-239 - [c19]Eric Miles, Emanuele Viola:
On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators. TCC 2011: 522-539 - [i33]Frederic Green, Daniel Kreymer, Emanuele Viola:
In Brute-Force Search of Correlation Bounds for Polynomials. Electron. Colloquium Comput. Complex. 18: 39 (2011) - [i32]Emanuele Viola:
Extractors for circuit sources. Electron. Colloquium Comput. Complex. 18: 56 (2011) - [i31]Eric Miles, Emanuele Viola:
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs. Electron. Colloquium Comput. Complex. 18: 76 (2011) - [i30]Emanuele Viola:
Reducing 3XOR to listing triangles, an exposition. Electron. Colloquium Comput. Complex. 18: 113 (2011) - [i29]Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola:
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Electron. Colloquium Comput. Complex. 18: 150 (2011) - [i28]Emanuele Viola:
The communication complexity of addition. Electron. Colloquium Comput. Complex. 18: 152 (2011) - [i27]Eric Miles, Emanuele Viola:
The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs. IACR Cryptol. ePrint Arch. 2011: 226 (2011) - 2010
- [j13]Andrej Bogdanov, Emanuele Viola:
Pseudorandom Bits for Polynomials. SIAM J. Comput. 39(6): 2464-2486 (2010) - [j12]Ronen Shaltiel, Emanuele Viola:
Hardness Amplification Proofs Require Majority. SIAM J. Comput. 39(7): 3122-3154 (2010) - [j11]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. SIAM J. Comput. 39(8): 3441-3462 (2010) - [c18]Emanuele Viola:
The Complexity of Distributions. FOCS 2010: 202-211 - [c17]Mihai Patrascu, Emanuele Viola:
Cell-Probe Lower Bounds for Succinct Partial Sums. SODA 2010: 117-122 - [i26]Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola:
Is It Real, or Is It Randomized?: A Financial Turing Test. CoRR abs/1002.4592 (2010) - [i25]Shachar Lovett, Emanuele Viola:
Bounded-depth circuits cannot sample good codes. Electron. Colloquium Comput. Complex. 17: 115 (2010) - [i24]Emanuele Viola:
Randomness buys depth for approximate counting. Electron. Colloquium Comput. Complex. 17: 175 (2010) - [i23]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. Electron. Colloquium Comput. Complex. 17: 186 (2010)
2000 – 2009
- 2009
- [j10]Emanuele Viola:
The Sum of D Small-Bias Generators Fools Polynomials of Degree D. Comput. Complex. 18(2): 209-217 (2009) - [j9]Emanuele Viola:
On Approximate Majority and Probabilistic Time. Comput. Complex. 18(3): 337-375 (2009) - [j8]Emanuele Viola, Avi Wigderson:
One-way multiparty communication lower bound for pointer jumping with applications. Comb. 29(6): 719-743 (2009) - [j7]Emanuele Viola:
On the Power of Small-Depth Computation. Found. Trends Theor. Comput. Sci. 5(1): 1-72 (2009) - [j6]Emanuele Viola:
Guest Column: correlation bounds for polynomials over {0 1}. SIGACT News 40(1): 27-44 (2009) - [j5]Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication. ACM Trans. Comput. Theory 1(2): 5:1-5:20 (2009) - [c16]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. FOCS 2009: 171-180 - [c15]Emanuele Viola:
Bit-probe lower bounds for succinct data structures. STOC 2009: 475-482 - [i22]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. CoRR abs/0902.3757 (2009) - [i21]Emanuele Viola:
Cell-Probe Lower Bounds for Prefix Sums. CoRR abs/0906.1370 (2009) - [i20]Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola:
A Computational View of Market Efficiency. CoRR abs/0908.4580 (2009) - [i19]Emanuele Viola:
Bit-Probe Lower Bounds for Succinct Data Structures. Electron. Colloquium Comput. Complex. 16: 5 (2009) - [i18]Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. Electron. Colloquium Comput. Complex. 16: 16 (2009) - [i17]Emanuele Viola:
Cell-Probe Lower Bounds for Prefix Sums. Electron. Colloquium Comput. Complex. 16: 54 (2009) - [i16]Emanuele Viola:
Are all distributions easy? Electron. Colloquium Comput. Complex. 16: 114 (2009) - 2008
- [j4]Emanuele Viola, Avi Wigderson:
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory Comput. 4(1): 137-168 (2008) - [c14]Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication. APPROX-RANDOM 2008: 371-384 - [c13]Emanuele Viola:
The Sum of d Small-Bias Generators Fools Polynomials of Degree d. Computational Complexity Conference 2008: 124-127 - [c12]Ronen Shaltiel, Emanuele Viola:
Hardness amplification proofs require majority. STOC 2008: 589-598 - 2007
- [j3]Emanuele Viola:
Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates. SIAM J. Comput. 36(5): 1387-1403 (2007) - [c11]Emanuele Viola, Avi Wigderson:
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. Computational Complexity Conference 2007: 141-154 - [c10]Emanuele Viola:
On Approximate Majority and Probabilistic Time. Computational Complexity Conference 2007: 155-168 - [c9]Andrej Bogdanov, Emanuele Viola:
Pseudorandom Bits for Polynomials. FOCS 2007: 41-51 - [c8]