Anup Rao

Electron. Colloquium Comput. Complex., 2023

2022

Anticoncentration and the Exact Gap-Hamming Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

On List Decoding Transitive Codes From Random Errors.

[BibT_eX]

[DOI]

Oscar Sprumont

Electron. Colloquium Comput. Complex., 2022

Sunflowers: from soil to oil.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

Tight bounds on the Fourier growth of bounded functions on the hypercube.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

2020

On Expressing Majority as a Majority of Majorities.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

The Communication Complexity of the Exact Gap-Hamming Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

2019

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.

[BibT_eX]

[DOI]

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2019

Coding for Sunflowers.

[BibT_eX]

[DOI]

CoRR, 2019

2018

Simplified Separation of Information and Communication.

[BibT_eX]

[DOI]

Makrand Sinha

Theory Comput., 2018

Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

2016

New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem.

[BibT_eX]

[DOI]

Jan Hazla

Thomas Holenstein

CoRR, 2016

A Direct-Sum Theorem for Read-Once Branching Programs.

[BibT_eX]

[DOI]

Makrand Sinha

Proceedings of the Approximation, 2016

2015

On Parallelizing Streaming Algorithms.

[BibT_eX]

[DOI]

Makrand Sinha

Electron. Colloquium Comput. Complex., 2015

How to Compress Asymmetric Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

Toward Coding for Maximum Errors in Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

Information Equals Amortized Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Circuits with Medium Fan-In.

[BibT_eX]

[DOI]

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2014

2013

How to Compress Interactive Communication.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Direct product via round-preserving compression.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Special Issue "Conference on Computational Complexity 2011" Guest Editor's Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2012

Spherical cubes: optimal foams from computational hardness amplification.

[BibT_eX]

[DOI]

Commun. ACM, 2012

Formulas Resilient to Short-Circuit Errors.

[BibT_eX]

[DOI]

Yael Tauman Kalai

Allison B. Lewko

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Deterministic extractors for small-space sources.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Restriction Access.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

2010

Pseudorandom Generators for Regular Branching Programs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Towards Coding for Maximum Errors in Interactive Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Efficient Communication Using Partial Information.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

2009

Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Direct Sums in Randomized Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness.

[BibT_eX]

[DOI]

Yael Tauman Kalai

Xin Li

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

Strong Parallel Repetition Theorem for Free Projection Games.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Extractors for Low-Weight Affine Sources.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Parallel Repetition in Projection Games and a Concentration Bound.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Spherical Cubes and Rounding in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Network Extractor Protocols.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Rounding Parallel Repetitions of Unique Games.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Extractors for Three Uneven-Length Sources.

[BibT_eX]

[DOI]

David Zuckerman

Proceedings of the Approximation, 2008

A 2-Source Almost-Extractor for Linear Entropy.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

An Exposition of Bourgain's 2-Source Extractor.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

2006

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources

[BibT_eX]

[DOI]