Anup Rao

Oscar Sprumont

Adv. Math. Commun., 2025

2024

XOR Lemmas for Communication via Marginal Information.

[BibT_eX]

[DOI]

Siddharth Iyer

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

An XOR Lemma for Deterministic Communication Complexity.

[BibT_eX]

[DOI]

Siddharth Iyer

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

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

The Communication Complexity of the Exact Gap-Hamming Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

2019

Coding for Sunflowers.

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

Pavel Hrubes

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

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

On Expressing Majority as a Majority of Majorities.

[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

Simplified Separation of Information and Communication.

[BibT_eX]

[DOI]

Makrand Sinha

Electron. Colloquium Comput. Complex., 2015

On Parallelizing Streaming Algorithms.

[BibT_eX]

[DOI]

Makrand Sinha

Electron. Colloquium Comput. Complex., 2015

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

How to Compress Asymmetric Communication.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

Circuits with Medium Fan-In.

[BibT_eX]

[DOI]

Pavel Hrubes

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Toward Coding for Maximum Errors in Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2014

2013

Direct Product via Round-Preserving Compression.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Direct Products in Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

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

Restriction access.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 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

Towards coding for maximum errors in interactive communication.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Information Equals Amortized Communication.

[BibT_eX]

[DOI]

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

2010

Efficient Communication Using Partial Information.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

How to compress interactive communication.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Pseudorandom Generators for Regular Branching Programs.

[BibT_eX]

[DOI]

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

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

Extractors for Low-Weight Affine Sources.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Strong Parallel Repetition Theorem for Free Projection Games.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Parallel repetition in projection games and a concentration bound.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 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

Extractors for a constant number of polynomially small min-entropy independent sources.

[BibT_eX]

[DOI]

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

Deterministic extractors for small-space sources.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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]