Emanuele Viola

ORCID

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 76

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

ACM Trans. Comput. Theory

SIAM J. Comput.

Publications

Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola
Pseudorandomness, symmetry, smoothing: I. CoRR (2024)
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola
Pseudorandomness, symmetry, smoothing: II. CoRR (2024)
Peter Ivanov, Emanuele Viola
Resilient functions: Optimized, simplified, and generalized. CoRR (2024)
Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola
Pseudorandomness, Symmetry, Smoothing: I. CCC (2024)
Ronen Shaltiel, Emanuele Viola
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. CoRR (2023)
Peter Ivanov, Liam Pavlovic, Emanuele Viola
On correlation bounds against polynomials. CoRR (2023)
Emanuele Viola
New Sampling Lower Bounds via the Separator. CCC (2023)
Peter Ivanov, Liam Pavlovic, Emanuele Viola
On Correlation Bounds Against Polynomials. CCC (2023)
Peter Ivanov, Raghu Meka, Emanuele Viola
Efficient resilient functions. SODA (2023)
Harm Derksen, Emanuele Viola
Quasirandom groups enjoy interleaved mixing. Electron. Colloquium Comput. Complex. (2022)
Ronen Shaltiel, Emanuele Viola
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. ITCS (2022)
Peter Ivanov, Raghu Meka, Emanuele Viola
Efficient resilient functions. Electron. Colloquium Comput. Complex. (2022)
Xuangui Huang, Peter Ivanov, Emanuele Viola
Affine Extractors and AC0-Parity. APPROX/RANDOM (2022)
Peter Ivanov, Liam Pavlovic, Emanuele Viola
On correlation bounds against polynomials. Electron. Colloquium Comput. Complex. (2022)
W. T. Gowers, Emanuele Viola
Mixing in Non-Quasirandom Groups. ITCS (2022)
Emanuele Viola
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines. Theory Comput. 18 (2022)
Harm Derksen, Emanuele Viola
Fooling polynomials using invariant theory. Electron. Colloquium Comput. Complex. (2022)
Harm Derksen, Emanuele Viola
. FOCS (2022)
Xuangui Huang, Emanuele Viola
Approximate Degree, Weight, and Indistinguishability. ACM Trans. Comput. Theory 14 (1) (2022)
Emanuele Viola
Correlation bounds against polynomials. Electron. Colloquium Comput. Complex. (2022)
Timothy Gowers, Emanuele Viola
Mixing in non-quasirandom groups. Electron. Colloquium Comput. Complex. 28 (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
-Polynomials and Applications. APPROX-RANDOM (2021)
Emanuele Viola
Fourier Conjectures, Correlation Bounds, and Majority. ICALP (2021)
Xuangui Huang, Peter Ivanov, Emanuele Viola
Affine extractors and AC0-Parity. Electron. Colloquium Comput. Complex. 28 (2021)
Ronen Shaltiel, Emanuele Viola
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. Electron. Colloquium Comput. Complex. 28 (2021)
Emanuele Viola
AC0 Unpredictability. ACM Trans. Comput. Theory 13 (1) (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. Electron. Colloquium Comput. Complex. 28 (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. CoRR (2021)
Xuangui Huang, Emanuele Viola
Average-Case Rigidity Lower Bounds. CSR (2021)
Emanuele Viola
Lower bounds for samplers and data structures via the cell-probe separator. Electron. Colloquium Comput. Complex. 28 (2021)
Emanuele Viola, Omri Weinstein, Huacheng Yu
How to Store a Random Walk. SODA (2020)
Emanuele Viola
New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Colloquium Comput. Complex. 27 (2020)
Xuangui Huang, Emanuele Viola
Average-case rigidity lower bounds. Electron. Colloquium Comput. Complex. 27 (2020)
Emanuele Viola
Fourier conjectures, correlation bounds, and Majority. Electron. Colloquium Comput. Complex. 27 (2020)
Emanuele Viola
Sampling Lower Bounds: Boolean Average-Case and Permutations. SIAM J. Comput. 49 (1) (2020)
Chin Ho Lee, Emanuele Viola
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials. Theory Comput. 16 (2020)
Emanuele Viola
Matching Smolensky's correlation bound with majority. Electron. Colloquium Comput. Complex. 26 (2019)
Emanuele Viola
Pseudorandom bits and lower bounds for randomized Turing machines. Electron. Colloquium Comput. Complex. 26 (2019)
W. T. Gowers, Emanuele Viola
Interleaved Group Products. SIAM J. Comput. 48 (2) (2019)
Emanuele Viola
Constant-Error Pseudorandomness Proofs from Hardness Require Majority. ACM Trans. Comput. Theory 11 (4) (2019)
Emanuele Viola, Omri Weinstein, Huacheng Yu
How to Store a Random Walk. CoRR (2019)
Emanuele Viola
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds. Theory Comput. 15 (2019)
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
Bounded Independence versus Symmetric Tests. ACM Trans. Comput. Theory 11 (4) (2019)
Emanuele Viola
Guest Column: Non-abelian Combinatorics and Communication Complexity. SIGACT News 50 (3) (2019)
Xuangui Huang, Emanuele Viola
Approximate Degree-Weight and Indistinguishability. Electron. Colloquium Comput. Complex. 26 (2019)
W. T. Gowers, Emanuele Viola
Interleaved group products. CoRR (2018)
Emanuele Viola
Constant-error pseudorandomness proofs from hardness require majority. Electron. Colloquium Comput. Complex. 25 (2018)
Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang
Revisiting Frequency Moment Estimation in Random Order Streams. CoRR (2018)
Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Local reduction. Inf. Comput. 261 (2018)
Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. Electron. Colloquium Comput. Complex. 25 (2018)
Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang
Revisiting Frequency Moment Estimation in Random Order Streams. ICALP (2018)
Chin Ho Lee, Emanuele Viola
The Coin Problem for Product Tests. ACM Trans. Comput. Theory 10 (3) (2018)
Emanuele Viola
Lower bounds for data structures with space close to maximum imply circuit lower bounds. Electron. Colloquium Comput. Complex. 25 (2018)
Elad Haramaty, Chin Ho Lee, Emanuele Viola
Bounded Independence Plus Noise Fools Products. SIAM J. Comput. 47 (2) (2018)
Emanuele Viola
AC0 unpredictability. Electron. Colloquium Comput. Complex. 25 (2018)
Emanuele Viola, Avi Wigderson
Local Expanders. Comput. Complex. 27 (2) (2018)
Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs. FOCS (2018)
Emanuele Viola
Sampling lower bounds: boolean average-case and permutations. Electron. Colloquium Comput. Complex. 25 (2018)
Emanuele Viola
Selected challenges in computational lower bounds. SIGACT News 48 (1) (2017)
Emanuele Viola
A sampling lower bound for permutations. Electron. Colloquium Comput. Complex. 24 (2017)
Chin Ho Lee, Emanuele Viola
Some Limitations of the Sum of Small-Bias Distributions. Theory Comput. 13 (1) (2017)
Chin Ho Lee, Emanuele Viola
The coin problem for product tests. Electron. Colloquium Comput. Complex. 24 (2017)
Frederic Green, Daniel Kreymer, Emanuele Viola
Block-symmetric polynomials correlate with parity better than symmetric. Comput. Complex. 26 (2) (2017)
Elad Haramaty, Chin Ho Lee, Emanuele Viola
Bounded Independence Plus Noise Fools Products. Computational Complexity Conference (2017)
Chin Ho Lee, Emanuele Viola
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Electron. Colloquium Comput. Complex. 24 (2017)
Elad Haramaty, Chin Ho Lee, Emanuele Viola
Bounded independence plus noise fools products. Electron. Colloquium Comput. Complex. 23 (2016)
Emanuele Viola, Avi Wigderson
Local Expanders. Electron. Colloquium Comput. Complex. 23 (2016)
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
Bounded Indistinguishability and the Complexity of Recovering Secrets. CRYPTO (3) (2016)
Eric Miles, Emanuele Viola
On the complexity of constructing pseudorandom functions (especially when they don't exist). IACR Cryptol. ePrint Arch. 2016 (2016)
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
Bounded Indistinguishability and the Complexity of Recovering Secrets. IACR Cryptol. ePrint Arch. 2016 (2016)
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
Bounded independence vs. moduli. Electron. Colloquium Comput. Complex. 23 (2016)
Emanuele Viola
Quadratic Maps Are Hard to Sample. ACM Trans. Comput. Theory 8 (4) (2016)
Timothy Gowers, Emanuele Viola
The multiparty communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. 23 (2016)
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
Bounded Independence vs. Moduli. APPROX-RANDOM (2016)
W. T. Gowers, Emanuele Viola
The Multiparty Communication Complexity of Interleaved Group Products. FOCS (2016)
Zahra Jafargholi, Emanuele Viola
3SUM, 3XOR, Triangles. Algorithmica 74 (1) (2016)
Eric Miles, Emanuele Viola
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. J. ACM 62 (6) (2015)
Emanuele Viola
The communication complexity of addition. Comb. 35 (6) (2015)
Emanuele Viola
Quadratic maps are hard to sample. Electron. Colloquium Comput. Complex. 22 (2015)
Hamid Jahanjou, Eric Miles, Emanuele Viola
Local Reductions. ICALP (1) (2015)
Chin Ho Lee, Emanuele Viola
Some limitations of the sum of small-bias distributions. Electron. Colloquium Comput. Complex. 22 (2015)
Oded Goldreich, Emanuele Viola, Avi Wigderson
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. 22 (2015)
Timothy Gowers, Emanuele Viola
The communication complexity of interleaved group products. STOC (2015)
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
Bounded Indistinguishability and the Complexity of Recovering Secrets. Electron. Colloquium Comput. Complex. 22 (2015)
Timothy Gowers, Emanuele Viola
The communication complexity of interleaved group products. Electron. Colloquium Comput. Complex. 22 (2015)
Eric Miles, Emanuele Viola
On the Complexity of Constructing Pseudorandom Functions (Especially when They Don't Exist). J. Cryptol. 28 (3) (2015)
Oded Goldreich, Emanuele Viola, Avi Wigderson
On Randomness Extraction in AC0. Computational Complexity Conference (2015)
Emanuele Viola
Randomness Buys Depth for Approximate Counting. Comput. Complex. 23 (3) (2014)
Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Succinct and explicit circuits for sorting and connectivity. Electron. Colloquium Comput. Complex. 21 (2014)
Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola
Global Information Sharing under Network Dynamics. CoRR (2014)
Eli Ben-Sasson, Emanuele Viola
Short PCPs with projection queries. Electron. Colloquium Comput. Complex. 21 (2014)
Emanuele Viola
Extractors for Circuit Sources. SIAM J. Comput. 43 (2) (2014)
Eli Ben-Sasson, Emanuele Viola
Short PCPs with Projection Queries. ICALP (1) (2014)
Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola
On Beating the Hybrid Argument. Theory Comput. 9 (2013)
Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Local reductions. Electron. Colloquium Comput. Complex. 20 (2013)
Emanuele Viola
Challenges in computational lower bounds. CoRR (2013)
Zahra Jafargholi, Emanuele Viola
3SUM, 3XOR, Triangles CoRR (2013)
Zahra Jafargholi, Emanuele Viola
3SUM, 3XOR, Triangles. Electron. Colloquium Comput. Complex. 20 (2013)
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) (2013)
Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola
On the Complexity of Information Spreading in Dynamic Networks. SODA (2013)

Emanuele Viola.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Emanuele Viola