Emanuele Viola

Electron. Colloquium Comput. Complex., 2025

Pseudorandomness, symmetry, smoothing: II.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Pseudorandom Bits for Non-Commutative Programs.

[BibT_eX]

[DOI]

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Resilient functions: Optimized, simplified, and generalized.

[BibT_eX]

[DOI]

CoRR, 2024

Boosting Uniformity in Quasirandom Groups: Fast and Simple.

[BibT_eX]

[DOI]

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

Pseudorandomness, Symmetry, Smoothing: I.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Efficient resilient functions.

[BibT_eX]

[DOI]

Raghu Meka

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

New Sampling Lower Bounds via the Separator.

[BibT_eX]

[DOI]

Proceedings of the 38th Computational Complexity Conference, 2023

On Correlation Bounds Against Polynomials.

[BibT_eX]

[DOI]

Liam Pavlovic

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Correlation bounds against polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Fooling polynomials using invariant theory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Quasirandom groups enjoy interleaved mixing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Ronen Shaltiel

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Mixing in Non-Quasirandom Groups.

[BibT_eX]

[DOI]

W. T. Gowers

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Fooling polynomials using invariant theory*.

[BibT_eX]

[DOI]

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

Affine Extractors and AC0-Parity.

[BibT_eX]

[DOI]

Xuangui Huang

Proceedings of the Approximation, 2022

2021

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Fourier Conjectures, Correlation Bounds, and Majority.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Average-Case Rigidity Lower Bounds.

[BibT_eX]

[DOI]

Xuangui Huang

Proceedings of the Computer Science - Theory and Applications, 2021

Fourier Growth of Structured 𝔽2-Polynomials and Applications.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

How to Store a Random Walk.

[BibT_eX]

[DOI]

Omri Weinstein

Huacheng Yu

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

2019

Bounded Independence versus Symmetric Tests.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

Guest Column: Non-abelian Combinatorics and Communication Complexity.

[BibT_eX]

[DOI]

SIGACT News, 2019

Interleaved Group Products.

[BibT_eX]

[DOI]

W. T. Gowers

SIAM J. Comput., 2019

Matching Smolensky's correlation bound with majority.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Pseudorandom bits and lower bounds for randomized Turing machines.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Approximate Degree-Weight and Indistinguishability.

[BibT_eX]

[DOI]

Xuangui Huang

Electron. Colloquium Comput. Complex., 2019

2018

Local reduction.

[BibT_eX]

[DOI]

Hamidreza Jahanjou

Inf. Comput., 2018

AC0 unpredictability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Constant-error pseudorandomness proofs from hardness require majority.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Sampling lower bounds: boolean average-case and permutations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Local Expanders.

[BibT_eX]

[DOI]

Comput. Complex., 2018

Revisiting Frequency Moment Estimation in Random Order Streams.

[BibT_eX]

[DOI]

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

Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs.

[BibT_eX]

[DOI]

Aryeh Grinberg

Ronen Shaltiel

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Selected challenges in computational lower bounds.

[BibT_eX]

[DOI]

SIGACT News, 2017

A sampling lower bound for permutations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

The coin problem for product tests.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Block-symmetric polynomials correlate with parity better than symmetric.

[BibT_eX]

[DOI]

Frederic Green

Daniel Kreymer

Comput. Complex., 2017

Bounded Independence Plus Noise Fools Products.

[BibT_eX]

[DOI]

Elad Haramaty

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

3SUM, 3XOR, Triangles.

[BibT_eX]

[DOI]

Zahra Jafargholi

Algorithmica, 2016

The Multiparty Communication Complexity of Interleaved Group Products.

[BibT_eX]

[DOI]

W. T. Gowers

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Bounded Indistinguishability and the Complexity of Recovering Secrets.

[BibT_eX]

[DOI]

Andrej Bogdanov

Yuval Ishai

Christopher Williamson

Proceedings of the Advances in Cryptology - CRYPTO 2016, 2016

Bounded Independence vs. Moduli.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Quadratic maps are hard to sample.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Some limitations of the sum of small-bias distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

The communication complexity of interleaved group products.

[BibT_eX]

[DOI]

Timothy Gowers

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Local Reductions.

[BibT_eX]

[DOI]

Hamid Jahanjou

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On Randomness Extraction in AC0.

[BibT_eX]

[DOI]

Oded Goldreich

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Succinct and explicit circuits for sorting and connectivity.

[BibT_eX]

[DOI]

Hamidreza Jahanjou

Electron. Colloquium Comput. Complex., 2014

Global Information Sharing under Network Dynamics.

[BibT_eX]

[DOI]

CoRR, 2014

Short PCPs with Projection Queries.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Challenges in computational lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Shielding circuits with groups.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

The communication complexity of addition.

[BibT_eX]

[DOI]

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

On the Complexity of Information Spreading in Dynamic Networks.

[BibT_eX]

[DOI]

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

2012

On a special case of rigidity.

[BibT_eX]

[DOI]

Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2012

Real Advantage.

[BibT_eX]

[DOI]

Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2012

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

[BibT_eX]

[DOI]

Kristoffer Arnsfelt Hansen

Electron. Colloquium Comput. Complex., 2012

From RAM to SAT.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

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

[BibT_eX]

[DOI]

Anna Gál

Michal Koucký

Pavel Pudlák

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

On beating the hybrid argument.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2012, 2012

Extractors for Turing-Machine Sources.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Special Section on Foundations of Computer Science.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Reducing 3XOR to listing triangles, an exposition.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

In Brute-Force Search of Correlation Bounds for Polynomials.

[BibT_eX]

[DOI]

Frederic Green

Daniel Kreymer

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

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

Randomness Buys Depth for Approximate Counting.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Extractors for Circuit Sources.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Bounded-Depth Circuits Cannot Sample Good Codes.

[BibT_eX]

[DOI]

Shachar Lovett

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

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

[BibT_eX]

[DOI]

Jasmina Hasanhodzic

Andrew W. Lo

CoRR, 2010

Cell-Probe Lower Bounds for Succinct Partial Sums.

[BibT_eX]

[DOI]

Mihai Patrascu

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

The Complexity of Distributions.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

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

[BibT_eX]

[DOI]

SIGACT News, 2009

On the Power of Small-Depth Computation.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2009

Cell-Probe Lower Bounds for Prefix Sums.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Are all distributions easy?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

A Computational View of Market Efficiency

[BibT_eX]

[DOI]

Jasmina Hasanhodzic

Andrew W. Lo

CoRR, 2009

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

[BibT_eX]

[DOI]

Comb., 2009

The Sum of D Small-Bias Generators Fools Polynomials of Degree D.

[BibT_eX]

[DOI]

Comput. Complex., 2009

Bit-probe lower bounds for succinct data structures.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Bounded Independence Fools Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

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

[BibT_eX]

[DOI]

Theory Comput., 2008

Hardness amplification proofs require majority.

[BibT_eX]

[DOI]

Ronen Shaltiel

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Sum of d Small-Bias Generators Fools Polynomials of Degree d.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Improved Separations between Nondeterministic and Randomized Multiparty Communication.

[BibT_eX]

[DOI]

Matei David

Toniann Pitassi

Proceedings of the Approximation, 2008

2007

Selected Results in Additive Combinatorics: An Exposition.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Pseudorandom Bits for Polynomials.

[BibT_eX]

[DOI]

Andrej Bogdanov

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

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

[BibT_eX]

[DOI]

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

On Approximate Majority and Probabilistic Time.

[BibT_eX]

[DOI]

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

2006

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

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

[BibT_eX]

[DOI]

Alexander Healy

Proceedings of the STACS 2006, 2006

On Probabilistic Time versus Alternating Time.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

The complexity of constructing pseudorandom generators from hard functions.

[BibT_eX]

[DOI]

Comput. Complex., 2005

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

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

On Constructing Parallel Pseudorandom Generators from One-Way Functions.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

On Parallel Pseudorandom Generators

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Using nondeterminism to amplify hardness.

[BibT_eX]

[DOI]

Alexander Healy

Salil P. Vadhan

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Fooling Parity Tests with Parity Gates.

[BibT_eX]

[DOI]

Dan Gutfreund

Proceedings of the Approximation, 2004

2003

Hardness vs. Randomness within Alternating Time.

[BibT_eX]

[DOI]

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

2001

E-unifiability via Narrowing.

[BibT_eX]

[DOI]