Emanuele Viola

According to our database, Emanuele Viola authored at least 105 papers between 2001 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Pseudorandomness, symmetry, smoothing: II.

Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

CoRR, 2024

Resilient functions: Optimized, simplified, and generalized.

Peter Ivanov, Emanuele Viola

CoRR, 2024

Boosting Uniformity in Quasirandom Groups: Fast and Simple.

Harm Derksen, Chin Ho Lee, Emanuele Viola

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Pseudorandomness, Symmetry, Smoothing: I.

Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

Proceedings of the 39th Computational Complexity Conference, 2024

2023

New Sampling Lower Bounds via the Separator.

Emanuele Viola

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Correlation bounds against polynomials.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2022

On correlation bounds against polynomials.

Peter Ivanov, Liam Pavlovic, Emanuele Viola

Electron. Colloquium Comput. Complex., 2022

Efficient resilient functions.

Peter Ivanov, Raghu Meka, Emanuele Viola

Electron. Colloquium Comput. Complex., 2022

Fooling polynomials using invariant theory.

Harm Derksen, Emanuele Viola

Electron. Colloquium Comput. Complex., 2022

Quasirandom groups enjoy interleaved mixing.

Harm Derksen, Emanuele Viola

Electron. Colloquium Comput. Complex., 2022

Fooling polynomials using invariant theory^*.

Harm Derksen, Emanuele Viola

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Lower bounds for samplers and data structures via the cell-probe separator.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2021

On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.

Ronen Shaltiel, Emanuele Viola

Electron. Colloquium Comput. Complex., 2021

Affine extractors and AC0-Parity.

Xuangui Huang, Peter Ivanov, Emanuele Viola

Electron. Colloquium Comput. Complex., 2021

Mixing in non-quasirandom groups.

Timothy Gowers, Emanuele Viola

Electron. Colloquium Comput. Complex., 2021

Fourier growth of structured 𝔽₂-polynomials and applications.

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola

Electron. Colloquium Comput. Complex., 2021

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications.

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola

CoRR, 2021

2020

Sampling Lower Bounds: Boolean Average-Case and Permutations.

Emanuele Viola

SIAM J. Comput., 2020

Fourier conjectures, correlation bounds, and Majority.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2020

New lower bounds for probabilistic degree and AC0 with parity gates.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2020

Average-case rigidity lower bounds.

Xuangui Huang, Emanuele Viola

Electron. Colloquium Comput. Complex., 2020

How to Store a Random Walk.

Emanuele Viola, Omri Weinstein, Huacheng Yu

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Bounded Independence versus Symmetric Tests.

Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

ACM Trans. Comput. Theory, 2019

Guest Column: Non-abelian Combinatorics and Communication Complexity.

Emanuele Viola

SIGACT News, 2019

Interleaved Group Products.

W. T. Gowers, Emanuele Viola

SIAM J. Comput., 2019

Matching Smolensky's correlation bound with majority.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2019

Pseudorandom bits and lower bounds for randomized Turing machines.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2019

Approximate Degree-Weight and Indistinguishability.

Xuangui Huang, Emanuele Viola

Electron. Colloquium Comput. Complex., 2019

2018

Bounded Independence Plus Noise Fools Products.

Elad Haramaty, Chin Ho Lee, Emanuele Viola

SIAM J. Comput., 2018

Local reduction.

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Inf. Comput., 2018

AC0 unpredictability.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2018

Lower bounds for data structures with space close to maximum imply circuit lower bounds.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2018

Constant-error pseudorandomness proofs from hardness require majority.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2018

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs.

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Electron. Colloquium Comput. Complex., 2018

Local Expanders.

Emanuele Viola, Avi Wigderson

Comput. Complex., 2018

Revisiting Frequency Moment Estimation in Random Order Streams.

Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Selected challenges in computational lower bounds.

Emanuele Viola

SIGACT News, 2017

A sampling lower bound for permutations.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2017

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials.

Chin Ho Lee, Emanuele Viola

Electron. Colloquium Comput. Complex., 2017

The coin problem for product tests.

Chin Ho Lee, Emanuele Viola

Electron. Colloquium Comput. Complex., 2017

Block-symmetric polynomials correlate with parity better than symmetric.

Frederic Green, Daniel Kreymer, Emanuele Viola

Comput. Complex., 2017

2016

The multiparty communication complexity of interleaved group products.

Timothy Gowers, Emanuele Viola

Electron. Colloquium Comput. Complex., 2016

Bounded independence vs. moduli.

Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Electron. Colloquium Comput. Complex., 2016

2015

Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs.

Eric Miles, Emanuele Viola

J. ACM, 2015

Quadratic maps are hard to sample.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2015

Some limitations of the sum of small-bias distributions.

Chin Ho Lee, Emanuele Viola

Electron. Colloquium Comput. Complex., 2015

The communication complexity of interleaved group products.

Timothy Gowers, Emanuele Viola

Electron. Colloquium Comput. Complex., 2015

On Randomness Extraction in AC0.

Oded Goldreich, Emanuele Viola, Avi Wigderson

Electron. Colloquium Comput. Complex., 2015

Bounded Indistinguishability and the Complexity of Recovering Secrets.

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

Electron. Colloquium Comput. Complex., 2015

2014

Extractors for Circuit Sources.

Emanuele Viola

SIAM J. Comput., 2014

Succinct and explicit circuits for sorting and connectivity.

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Electron. Colloquium Comput. Complex., 2014

Short PCPs with projection queries.

Eli Ben-Sasson, Emanuele Viola

Electron. Colloquium Comput. Complex., 2014

Global Information Sharing under Network Dynamics.

Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola

CoRR, 2014

Randomness Buys Depth for Approximate Counting.

Emanuele Viola

Comput. Complex., 2014

2013

Challenges in computational lower bounds.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2013

Shielding circuits with groups.

Eric Miles, Emanuele Viola

Electron. Colloquium Comput. Complex., 2013

Local reductions.

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Electron. Colloquium Comput. Complex., 2013

3SUM, 3XOR, Triangles.

Zahra Jafargholi, Emanuele Viola

Electron. Colloquium Comput. Complex., 2013

On the Complexity of Information Spreading in Dynamic Networks.

Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, Emanuele Viola

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Bit-Probe Lower Bounds for Succinct Data Structures.

Emanuele Viola

SIAM J. Comput., 2012

The Complexity of Distributions.

Emanuele Viola

SIAM J. Comput., 2012

Extractors for Turing-machine sources.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

On a special case of rigidity.

Rocco A. Servedio, Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

Real Advantage.

Alexander A. Razborov, Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

On the complexity of constructing pseudorandom functions (especially when they don't exist).

Eric Miles, Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

From RAM to SAT.

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

Bounded-Depth Circuits Cannot Sample Good Codes.

Shachar Lovett, Emanuele Viola

Comput. Complex., 2012

2011

Special Section on Foundations of Computer Science.

Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola

SIAM J. Comput., 2011

The communication complexity of addition.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

Reducing 3XOR to listing triangles, an exposition.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs.

Eric Miles, Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

In Brute-Force Search of Correlation Bounds for Polynomials.

Frederic Green, Daniel Kreymer, Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.

Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators.

Eric Miles, Emanuele Viola

Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

2010

Hardness Amplification Proofs Require Majority.

Ronen Shaltiel, Emanuele Viola

SIAM J. Comput., 2010

Bounded Independence Fools Halfspaces.

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola

SIAM J. Comput., 2010

Pseudorandom Bits for Polynomials.

Andrej Bogdanov, Emanuele Viola

SIAM J. Comput., 2010

On beating the hybrid argument.

Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola

Electron. Colloquium Comput. Complex., 2010

Is It Real, or Is It Randomized?: A Financial Turing Test

Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola

CoRR, 2010

Cell-Probe Lower Bounds for Succinct Partial Sums.

Mihai Patrascu, Emanuele Viola

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Improved Separations between Nondeterministic and Randomized Multiparty Communication.

Matei David, Toniann Pitassi, Emanuele Viola

ACM Trans. Comput. Theory, 2009

Guest Column: correlation bounds for polynomials over {0 1}.

Emanuele Viola

SIGACT News, 2009

On the Power of Small-Depth Computation.

Emanuele Viola

Found. Trends Theor. Comput. Sci., 2009

Cell-Probe Lower Bounds for Prefix Sums.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2009

Are all distributions easy?

Emanuele Viola

Electron. Colloquium Comput. Complex., 2009

A Computational View of Market Efficiency

Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola

CoRR, 2009

One-way multiparty communication lower bound for pointer jumping with applications.

Emanuele Viola, Avi Wigderson

Comb., 2009

On Approximate Majority and Probabilistic Time.

Emanuele Viola

Comput. Complex., 2009

The Sum of <i>D</i> Small-Bias Generators Fools Polynomials of Degree <i>D</i>.

Emanuele Viola

Comput. Complex., 2009

2008

Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols.

Emanuele Viola, Avi Wigderson

Theory Comput., 2008

2007

Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates.

Emanuele Viola

SIAM J. Comput., 2007

One-way multi-party communication lower bound for pointer jumping with applications.

Emanuele Viola, Avi Wigderson

Electron. Colloquium Comput. Complex., 2007

The sum of d small-bias generators fools polynomials of degree d.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2007

Selected Results in Additive Combinatorics: An Exposition.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2007

Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols.

Emanuele Viola, Avi Wigderson

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Using Nondeterminism to Amplify Hardness.

Alexander Healy, Salil P. Vadhan, Emanuele Viola

SIAM J. Comput., 2006

New correlation bounds for GF(2) polynomials using Gowers uniformity.

Emanuele Viola

Electron. Colloquium Comput. Complex., 2006

2005

On Constructing Parallel Pseudorandom Generators from One-Way Functions.

Emanuele Viola

IACR Cryptol. ePrint Arch., 2005

On Probabilistic Time versus Alternating Time

Emanuele Viola

Electron. Colloquium Comput. Complex., 2005

Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

Alexander Healy, Emanuele Viola

Electron. Colloquium Comput. Complex., 2005

The complexity of constructing pseudorandom generators from hard functions.

Emanuele Viola

Comput. Complex., 2005

2004

Fooling Parity Tests with Parity Gates

Emanuele Viola, Dan Gutfreund

Electron. Colloquium Comput. Complex., 2004

On Parallel Pseudorandom Generators

Emanuele Viola

Electron. Colloquium Comput. Complex., 2004

2003

Hardness vs. Randomness within Alternating Time.

Emanuele Viola

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2001

E-unifiability via Narrowing.

Emanuele Viola

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001