Anup Rao

75 papers A* 17A 6Journal 46Unranked 5
YearRankTypeTitle / Venue / Authors
2025 J jnl
A criterion for decoding on the binary symmetric channel.
Adv. Math. Commun.
Anup Rao, Oscar Sprumont
2024 A* conf
An XOR Lemma for Deterministic Communication Complexity.
FOCS
Siddharth Iyer, Anup Rao
2024 J jnl
An XOR Lemma for Deterministic Communication Complexity.
CoRR
Siddharth Iyer, Anup Rao
2024 J jnl
An XOR Lemma for Deterministic Communication Complexity.
Electron. Colloquium Comput. Complex.
Siddharth Iyer, Anup Rao
2024 A* conf
XOR Lemmas for Communication via Marginal Information.
STOC
Siddharth Iyer, Anup Rao
2023 J jnl
XOR Lemmas for Communication via Marginal Information.
CoRR
Siddharth Iyer, Anup Rao
2023 J jnl
XOR Lemmas for Communication via Marginal Information.
Electron. Colloquium Comput. Complex.
Siddharth Iyer, Anup Rao
2022 J jnl
Anticoncentration and the Exact Gap-Hamming Problem.
SIAM J. Discret. Math.
Anup Rao, Amir Yehudayoff
2022 J jnl
On List Decoding Transitive Codes From Random Errors.
CoRR
Anup Rao, Oscar Sprumont
2022 J jnl
On List Decoding Transitive Codes From Random Errors.
Electron. Colloquium Comput. Complex.
Anup Rao, Oscar Sprumont
2022 J jnl
Sunflowers: from soil to oil.
Electron. Colloquium Comput. Complex.
Anup Rao
2021 J jnl
Tight bounds on the Fourier growth of bounded functions on the hypercube.
CoRR
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff
2021 J jnl
Tight bounds on the Fourier growth of bounded functions on the hypercube.
Electron. Colloquium Comput. Complex.
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff
2020 J jnl
On Expressing Majority as a Majority of Majorities.
SIAM J. Discret. Math.
Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao
2020 J jnl
The Communication Complexity of the Exact Gap-Hamming Problem.
Electron. Colloquium Comput. Complex.
Anup Rao, Amir Yehudayoff
2019 J jnl
Coding for Sunflowers.
CoRR
Anup Rao
2019 A* conf
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.
ICALP
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
2019 J jnl
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
2018 A conf
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.
CCC
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
2018 J jnl
Simplified Separation of Information and Communication.
Theory Comput.
Anup Rao, Makrand Sinha
2017 J jnl
Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers.
Electron. Colloquium Comput. Complex.
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
2017 J jnl
On Expressing Majority as a Majority of Majorities.
Electron. Colloquium Comput. Complex.
Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao
2016 — conf
A Direct-Sum Theorem for Read-Once Branching Programs.
APPROX-RANDOM
Anup Rao, Makrand Sinha
2016 J jnl
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem.
CoRR
Jan Hazla, Thomas Holenstein, Anup Rao
2016 J jnl
New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity.
Electron. Colloquium Comput. Complex.
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
2015 — ed.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, Princeton, NJ, USA, August 24-26, 2015
APPROX-RANDOM
Naveen Garg, Klaus Jansen, Anup Rao, José D. P. Rolim
2015 A conf
Circuits with Medium Fan-In.
CCC
Pavel Hrubes, Anup Rao
2015 A conf
How to Compress Asymmetric Communication.
CCC
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
2015 J jnl
How to Compress Asymmetric Communication.
Electron. Colloquium Comput. Complex.
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
2015 J jnl
On Parallelizing Streaming Algorithms.
Electron. Colloquium Comput. Complex.
Anup Rao, Makrand Sinha
2015 A conf
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.
CCC
Anup Rao, Amir Yehudayoff
2015 J jnl
Simplified Separation of Information and Communication.
Electron. Colloquium Comput. Complex.
Anup Rao, Makrand Sinha
2014 J jnl
Circuits with Medium Fan-In.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Anup Rao
2014 J jnl
Information Equals Amortized Communication.
IEEE Trans. Inf. Theory
Mark Braverman, Anup Rao
2014 J jnl
Pseudorandom Generators for Regular Branching Programs.
SIAM J. Comput.
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2014 J jnl
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness.
Electron. Colloquium Comput. Complex.
Anup Rao, Amir Yehudayoff
2014 J jnl
Toward Coding for Maximum Errors in Interactive Communication.
IEEE Trans. Inf. Theory
Mark Braverman, Anup Rao
2013 — conf
Direct Product via Round-Preserving Compression.
ICALP (1)
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 A* conf
Direct Products in Communication Complexity.
FOCS
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 J jnl
Direct product via round-preserving compression.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2013 J jnl
How to Compress Interactive Communication.
SIAM J. Comput.
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2012 J jnl
Direct Products in Communication Complexity.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
2012 A* conf
Formulas Resilient to Short-Circuit Errors.
FOCS
Yael Tauman Kalai, Allison B. Lewko, Anup Rao
2012 A conf
Restriction access.
ITCS
Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff
2012 J jnl
Special Issue "Conference on Computational Complexity 2011" Guest Editor's Foreword.
Comput. Complex.
Anup Rao
2012 J jnl
Spherical cubes: optimal foams from computational hardness amplification.
Commun. ACM
Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson
2011 J jnl
Deterministic extractors for small-space sources.
J. Comput. Syst. Sci.
Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman
2011 J jnl
Information Equals Amortized Communication
CoRR
Mark Braverman, Anup Rao
2011 A* conf
Information Equals Amortized Communication.
FOCS
Mark Braverman, Anup Rao
2011 J jnl
Parallel Repetition in Projection Games and a Concentration Bound.
SIAM J. Comput.
Anup Rao
2011 J jnl
Restriction Access.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff
2011 A* conf
Towards coding for maximum errors in interactive communication.
STOC
Mark Braverman, Anup Rao
2010 J jnl
Efficient Communication Using Partial Information.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao
2010 A* conf
How to compress interactive communication.
STOC
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2010 A* conf
Pseudorandom Generators for Regular Branching Programs.
FOCS
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010 J jnl
Pseudorandom Generators for Regular Branching Programs.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff
2010 J jnl
Towards Coding for Maximum Errors in Interactive Communication.
Electron. Colloquium Comput. Complex.
Mark Braverman, Anup Rao
2009 A* conf
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness.
FOCS
Yael Tauman Kalai, Xin Li, Anup Rao
2009 J jnl
Direct Sums in Randomized Communication Complexity.
Electron. Colloquium Comput. Complex.
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2009 A conf
Extractors for Low-Weight Affine Sources.
CCC
Anup Rao
2009 J jnl
Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources.
SIAM J. Comput.
Anup Rao
2009 — conf
Strong Parallel Repetition Theorem for Free Projection Games.
APPROX-RANDOM
Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel
2008 — conf
A 2-Source Almost-Extractor for Linear Entropy.
APPROX-RANDOM
Anup Rao
2008 J jnl
Extractors for Low-Weight Affine Sources.
Electron. Colloquium Comput. Complex.
Anup Rao
2008 — conf
Extractors for Three Uneven-Length Sources.
APPROX-RANDOM
Anup Rao, David Zuckerman
2008 A* conf
Network Extractor Protocols.
FOCS
Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman
2008 J jnl
Parallel Repetition in Projection Games and a Concentration Bound.
Electron. Colloquium Comput. Complex.
Anup Rao
2008 A* conf
Parallel repetition in projection games and a concentration bound.
STOC
Anup Rao
2008 A* conf
Rounding Parallel Repetitions of Unique Games.
FOCS
Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer
2008 A* conf
Spherical Cubes and Rounding in High Dimensions.
FOCS
Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson
2007 J jnl
An Exposition of Bourgain's 2-Source Extractor.
Electron. Colloquium Comput. Complex.
Anup Rao
2006 A* conf
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.
STOC
Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson
2006 A* conf
Deterministic extractors for small-space sources.
STOC
Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman
2006 A* conf
Extractors for a constant number of polynomially small min-entropy independent sources.
STOC
Anup Rao
2005 J jnl
Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources
Electron. Colloquium Comput. Complex.
Anup Rao