Emanuele Viola

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Pseudorandom Bits and Lower Bounds for Randomized Turing Machines.

[BibT_eX]

[DOI]

Theory Comput., 2022

Correlation bounds against polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

On correlation bounds against polynomials.

[BibT_eX]

[DOI]

Peter Ivanov

Liam Pavlovic

Electron. Colloquium Comput. Complex., 2022

Efficient resilient functions.

[BibT_eX]

[DOI]

Peter Ivanov

Raghu Meka

Electron. Colloquium Comput. Complex., 2022

Fooling polynomials using invariant theory.

[BibT_eX]

[DOI]

Harm Derksen

Electron. Colloquium Comput. Complex., 2022

Quasirandom groups enjoy interleaved mixing.

[BibT_eX]

[DOI]

Harm Derksen

Electron. Colloquium Comput. Complex., 2022

Fooling polynomials using invariant theory*.

[BibT_eX]

[DOI]

Harm Derksen

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.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

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

[BibT_eX]

[DOI]

Ronen Shaltiel

Electron. Colloquium Comput. Complex., 2021

Affine extractors and AC0-Parity.

[BibT_eX]

[DOI]

Xuangui Huang

Peter Ivanov

Electron. Colloquium Comput. Complex., 2021

Mixing in non-quasirandom groups.

[BibT_eX]

[DOI]

Timothy Gowers

Electron. Colloquium Comput. Complex., 2021

Fourier growth of structured 𝔽2-polynomials and applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

2020

More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials.

[BibT_eX]

[DOI]

Theory Comput., 2020

Fourier conjectures, correlation bounds, and Majority.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Average-case rigidity lower bounds.

[BibT_eX]

[DOI]

Xuangui Huang

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

Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds.

[BibT_eX]

[DOI]

Theory Comput., 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

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

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

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

[BibT_eX]

[DOI]

Aryeh Grinberg

Ronen Shaltiel

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

2017

Some Limitations of the Sum of Small-Bias Distributions.

[BibT_eX]

[DOI]

Theory Comput., 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

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

2016

Bounded independence plus noise fools products.

[BibT_eX]

[DOI]

Elad Haramaty

Electron. Colloquium Comput. Complex., 2016

The multiparty communication complexity of interleaved group products.

[BibT_eX]

[DOI]

Timothy Gowers

Electron. Colloquium Comput. Complex., 2016

Bounded independence vs. moduli.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

3SUM, 3XOR, Triangles.

[BibT_eX]

[DOI]

Zahra Jafargholi

Algorithmica, 2016

2015

On the Complexity of Constructing Pseudorandom Functions (Especially when They Don't Exist).

[BibT_eX]

[DOI]

J. Cryptol., 2015

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

[BibT_eX]

[DOI]

J. ACM, 2015

Quadratic maps are hard to sample.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

The communication complexity of interleaved group products.

[BibT_eX]

[DOI]

Timothy Gowers

Electron. Colloquium Comput. Complex., 2015

On Randomness Extraction in AC0.

[BibT_eX]

[DOI]

Oded Goldreich

Electron. Colloquium Comput. Complex., 2015

Bounded Indistinguishability and the Complexity of Recovering Secrets.

[BibT_eX]

[DOI]

Andrej Bogdanov

Yuval Ishai

Christopher Williamson

Electron. Colloquium Comput. Complex., 2015

The communication complexity of addition.

[BibT_eX]

[DOI]

Comb., 2015

2014

Succinct and explicit circuits for sorting and connectivity.

[BibT_eX]

[DOI]

Hamidreza Jahanjou

Electron. Colloquium Comput. Complex., 2014

Short PCPs with projection queries.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Electron. Colloquium Comput. Complex., 2014

Global Information Sharing under Network Dynamics.

[BibT_eX]

[DOI]

CoRR, 2014

Randomness Buys Depth for Approximate Counting.

[BibT_eX]

[DOI]

Comput. Complex., 2014

2013

On Beating the Hybrid Argument.

[BibT_eX]

[DOI]

Theory Comput., 2013

Challenges in computational lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Shielding circuits with groups.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Local reductions.

[BibT_eX]

[DOI]

Hamidreza Jahanjou

Electron. Colloquium Comput. Complex., 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

The Complexity of Distributions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Extractors for Turing-machine sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

From RAM to SAT.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Bounded-Depth Circuits Cannot Sample Good Codes.

[BibT_eX]

[DOI]

Shachar Lovett

Comput. Complex., 2012

2011

Selected Results in Additive Combinatorics: An Exposition.

[BibT_eX]

[DOI]

Theory Comput., 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

Extractors for circuit sources.

[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

Kristoffer Arnsfelt Hansen

Electron. Colloquium Comput. Complex., 2011

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

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

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

2009

Improved Separations between Nondeterministic and Randomized Multiparty Communication.

[BibT_eX]

[DOI]

Matei David

Toniann Pitassi

ACM Trans. Comput. Theory, 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

Bit-Probe Lower Bounds for Succinct Data Structures.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Bounded Independence Fools Halfspaces.

[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

On Approximate Majority and Probabilistic Time.

[BibT_eX]

[DOI]

Comput. Complex., 2009

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

[BibT_eX]

[DOI]

Comput. Complex., 2009

2008

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

[BibT_eX]

[DOI]

Theory Comput., 2008

2007

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Hardness amplification proofs require majority.

[BibT_eX]

[DOI]

Ronen Shaltiel

Electron. Colloquium Comput. Complex., 2007

Pseudorandom bits for polynomials.

[BibT_eX]

[DOI]

Andrej Bogdanov

Electron. Colloquium Comput. Complex., 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

2006

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

2005

On Constructing Parallel Pseudorandom Generators from One-Way Functions.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2005

On Probabilistic Time versus Alternating Time

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

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

[BibT_eX]

[DOI]

Alexander Healy

Electron. Colloquium Comput. Complex., 2005

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

The complexity of constructing pseudorandom generators from hard functions.

[BibT_eX]

[DOI]

Comput. Complex., 2005

2004

Fooling Parity Tests with Parity Gates

[BibT_eX]

[DOI]

Dan Gutfreund

Electron. Colloquium Comput. Complex., 2004

Using Nondeterminism to Amplify Hardness

[BibT_eX]

[DOI]

Alexander Healy

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2004

On Parallel Pseudorandom Generators

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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]