Publication List

Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computing
2023 Edsger W. Dijkstra Prize in Distributed Computing
Proceedings of the 20th Symposium on the Theory of Computing (STOC), May 1988
An Optimal "It Ain't Over Till It's Over" Theorem
Accepted to STOC 2023
arXiv:2208.03450v1, August 2022
On Linear-Algebraic Notions of Expansion
arXiv:2212.13154v2, January 2023
Asymptotic Spectra: Theory, Applications and Extensions
Draft of a Final Version, October 2023
Connections Between Graphs and Matrix Spaces
Accepted into Israel Journal of Mathematics, January 2023
arXiv:2206.04815v1, June 2022
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
arXiv:2209.07024v1, September 2022
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Theory of Computing, Theory of Computing 17(10), 2021, 1-88, DOI: 10.4086/toc.2021.v017a010
Proceedings of the Computational Complexity Conference (CCC) 2016, vol. 50, pp. 32:1-32:17, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.32
Electronic Colloquium on Computational Complexity (ECCC), 23: 98, 2016.
The Uncertainty Principle: Variations on a Theme
Bulletin of the American Mathematical Society (BAMS), Volume 58, Number 2, April 2021, Pages 225-261
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
TheoretiCS, 2022
Computational Complexity Conference (CCC) 2021, LIPIcs, Volume 200
Electronic Colloquium on Computational Complexity (ECCC) Report TR20-149, September 2020
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model
Proceedings of Foundations of Computer Science (FOCS) 2021
Electronic Colloquium on Computational Complexity (ECCC) Report TR20-160, November 2020
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network
accepted to Israel Journal of Mathematics, December 2021
Electronic Colloquium on Computational Complexity (ECCC) Report TR20-192, December 2020
Polynomial Time Algorithms In Invariant Theory For Torus Actions
Computational Complexity Conference (CCC) 2021, LIPIcs, Volume 200
arXiv:2102.07727, February 2021
On the Power and Limitations of Branch and Cut
Computational Complexity Conference (CCC) 2021, LIPIcs, Volume 200
Electronic Colloquium on Computational Complexity (ECCC) Report TR21-012, February 2021
Search Problems in Algebraic Complexity, GCT, and Hardness of Generator for Invariant Rings
Accepted into Proceedings of the Computational Complexity Conference (CCC) 2020
arXiv:1910.01251
Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)
arXiv:1909.00857
Journal für die reine und angewandte Mathematik (Crelle's Journal), 2021
Operator Scaling: Theory and Applications
Foundations of Computational Mathematics, Volume 20, Number 2, April 2020
arXiv:1511.03730v4
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
SIAM Journal on Computing (SICOMP) Volume 49, Issue 3, pp. 465-496 (2020)
Proceedings of the Innovations in Theoretical Computer Science (ITCS) 2019, pp. 32:1-32:20, 2019
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
Springer, Computational Complexity, 2019, https://doi.org/10.1007/s00037-019-00177-4
Electronic Colloquium on Computational Complexity (ECCC) Report TR17-149, pp. 1-22, 2017.
Subspace arrangements, graph rigidity and derandomization
arXiv:1901.09423
More barriers for rank methods, via a "numeric to symbolic" transfer
Accepted into Proceedings of Foundations of Computer Science (FOCS) 2019
arXiv:1904.04299
Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes
Proceedings of 60th IEEE Symposium on Foundations of Computer Science (FOCS'19), pp. 845-861, 2019
arXiv:1910.12375
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
Proceedings of the Innovations in Theoretical Computer Science (ITCS) 2018, pp. 24:1-24:20, 2018. https://doi.org/10.4230/LIPIcs.ITCS.2018.24
arXiv:1711.08039v1
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Proceedings of the Symposium on Theory of Computing (STOC) 2018, pp. 172-181, 2018.
On the nature of the Theory of Computation (ToC)
Electronic Colloquium on Computational Complexity (ECCC) Report TR18-072, pp. 1-49, 2018.
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
Proceedings of Foundations of Computer Science (FOCS) 2018.
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling
Geometric and Functional Analysis 2018, https://doi.org/10.1007/s00039-018-0434-2
Proceedings of the Symposium on Theory of Computing (STOC) 2017, pp. 397-409, 2017.
arXiv:1607.06711
Toward Better Formula Lower Bounds: the Composition of a Function and a Universal Relation
SIAM Journal on Computing (SICOMP), vol. 46, no. 1, pp. 114-131, 2017. https://doi.org/10.1137/15M1018319
Explicit Capacity Approaching Coding for Interactive Communication
IEEE Transactions on Information Theory, vol. 64, no. 10, pp. 6546-6560, Oct. 2018, doi: 10.1109/TIT.2018.2829764
IEEE Transactions on Information Theory, 2017.
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals
Theory of Computing, vol. 13(11), pp. 1-36, 2017.
Barriers for Rank Methods in Arithmetic Complexity
Proceedings of the Innovations in Theoretical Computer Science (ITCS) 2018, pp. 1:1-1:19, 2018.
Electronic Colloquium on Computational Complexity (ECCC) Report TR17-162, vol. 24, pp. 162, 2017.
Much Faster Algorithms for Matrix Scaling
Proceedings of Foundations of Computer Science (FOCS) 2017, pp. 890-901, 2017.
Symmetric LDPC codes and local testing
Combinatorica, vol. 36, no. 1, pp. 92-120, 2016. https://doi.org/10.1007/s00493-014-2715-1
Proceedings of Innovations in Computer Science (ICS) 2010, pp. 406-421, 2010.
Population Recovery and Partial Identification
Journal of Machine Learning, vol. 102, no. 1, pp. 29-56, 2016. https://doi.org/10.1007/s10994-015-5489-9
Foundations of Computer Science (FOCS) 2012, pp. 390-399, 2012.
Towards Optimal Deterministic Coding for Interactive Communication
Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016, pp. 1922-1936, 2016.
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-165, pp. 1-26, 2015.
Degree and Sensitivity: tails of two distributions
Electronic Colloquium on Computational Complexity (ECCC) Report TR16-069, pp. 1-31, 2016.
Degree and Sensitivity: tails of two distributions
Proceedings of the Computational Complexity Conference (CCC) 2016, pp. 13:1-13:23, 2016. https://doi.org/10.4230/LIPIcs.CCC.2016.13
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing
Proceedings of Foundations of Computer Science (FOCS) 2016, pp. 109-117, 2016. https://doi.org/10.1109/FOCS.2016.95.
Local Expanders
Springer, Computational Complexity, 2017, DOI 10.1007/s00037-017-0155-1
Electronic Colloquium on Computational Complexity (ECCC) Report TR16-129, pp. 1-13, 2016.
Reed-Muller codes for random erasures and errors
IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5229-5252, 2015.
Proceedings of the Symposium on Theory of Computing (STOC) 2015, pp. 297-306, 2015.
On Randomness Extraction in ACo
Proceedings of the Computational Complexity Conference (CCC) 2015, pp. 601-668, 2015.
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-003, pp. 1-70, 2015.
Teaching and compressing for low VC-dimension
Accepted into "Journey Through Discrete Mathematics. A Tribute to Jiri Matousek"
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-025, pp. 1-24, 2015.
Sum-of-squares lower bounds for planted clique
Proceedings of the Symposium on Theory of Computing (STOC) 2015, pp. 87-96, 2015.
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Proceedings of the Innovations in Theoretical Computer Science (ITCS) 2016, pp. 59-70, 2016.
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-131, 2015.
Sum-of-Squares Lower Bounds for Sparse PCA
Neural Information Processing Systems (NIPS) 2015, pp. 1612-1620, 2015.
Improved rank bounds for design matrices and a new proof of Kelly's theorem
Forum of Mathematics, Sigma 4, vol. 2, 2014
Electronic Colloquium on Computational Complexity (ECCC) Report TR12-138, 2012.
Non-commutative arithmetic circuits with division
Theory of Computing, vol. 11, pp. 357-393, 2015.
Proceedings of ITCS (Innovations in Theoretical Computer Science) 2014, pp. 49-66, 2014.
Breaking the Quadratic Barrier for 3-LCC's over the Reals
Proceedings of Symposium on the Theory of Computing (STOC) 2014, pp. 784-793, 2014.
Sylvester-Gallai Type Theorems for Approximate Collinearity
Forum of Mathematics, Sigma, vol. 2, 2014.
On Derandomizing Algorithms that Err Extremely Rarely
Proceedings of Symposium on the Theory of Computing (STOC) 2014, pp. 1-21, 2014.
Electronic Colloquium on Computational Complexity (ECCC) Report TR13-152, pp. 1-21, 2013.
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
Proceedings of Symposium on the Theory of Computing (STOC) 2014, pp. 1-48, 2014.
Electronic Colloquium on Computational Complexity (ECCC) Report TR13-190, pp. 1-48, 2013.
Interactive proofs of proximity: delegating computation in sublinear time
Proceedings of Symposium on the Theory of Computing (STOC) 2013, pp. 793-802, 2013
An Asymptotic Bound on the Composition Number of Integer Sums of Squares Formulas
Canadian Mathematical Society, vol. 56, no. 1, pp. 70-79, 2013.
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
Electronic Colloquium on Computational Complexity (ECCC) Report TR13-043, pp. 1-40, 2013.
2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
Annals of Mathematics, vol. 176, no. 3, pp.1483-1543, 2012.
Restriction Access
Proceedings of ITCS (Innovations in Theoretical Computer Science) 2012, pp. 19-33, 2012.
Fractional Sylvester-Gallai theorems
Proceedings of the National Academy of Sciences of the United States of America 2012.
Spherical Cubes: Optimal Foams from Computational Hardness Amplification
Communications of the ACM, vol. 55, no. 10, pp. 90-97, 2012.
Non-commutative circuits and the sum-of-squares problem
Journal of the American Mathematical Society, vol. 24, no. 3, pp. 871-898, 2011.
Proceedings of the Symposium on Theory of Computing (STOC) 2010, pp. 667-676, 2010.
Kakeya Sets, New Mergers and Old Extractors
SIAM Journal on Computing, vol. 40, no. 3, pp. 778-792, 2011
Proceedings of the 49th Annual Foundations of Computer Science (FOCS) 2008, vol. 15, pp. 625-633, 2008.
Partial Derivatives in Arithmetic Complexity and Beyond
Foundations and Trends in Theoretical Computer Science (FTTCS), vol. 6, no. 1-2, pp. 1-138, 2011.
Simplified Derandomization of BPP Using a Hitting Set Generator
Studies in Complexity and Cryptography, vol. 6650, pp. 59-67, 2011.
Electronic Colloquium on Computational Complexity, Volume 7, 2000.
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
Journal of the ACM (JACM), vol. 57, no. 4, pp. 20:1 - 20:52, 2010.
Relationless completeness and separations
Electronic Colloquium on Computational Complexity (ECCC) Report TR10-040, pp. 1-29, 2010.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), pp.280-290, 2010.
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Proceedings of STOC 2008, pp. 579-588, 2008.
Society for Industrial and Applied Mathematics (SIAM) J. Comput., vol. 39, no. 4, pp. 1637-1665, 2010.
Public Key Cryptography from Different Assumptions
Proceedings of Symposium on Theory of Computing (STOC) 2010, pp. 1-57, 2010.
Extractors and rank extractors for polynomial sources
Proceedings of the Foundations of Computer Science (FOCS) 2007 conference, pp. 52-62, 2007.
Electronic Colloquium on Computational Complexity (ECCC) Report TR07-056, 2007.
Computational Complexity (CC), vol. 18, no. 1, pp. 1-58, 2009.
New Direct-Product Testers and 2-Query PCPs
Proceedings of Symposium on Theory of Computing (STOC) 2009, pp. 131-140, 2009.
Electronic Colloquium on Computational Complexity (ECCC) Report TR09-090, 2009.
Towards a study of low-complexity graphs
Proceedings of International Colloquium on Automata, Languages and Programming (ICALP) 2009, pp. 119-131.
Linear systems over composite moduli
Proceedings of Foundations of Computer Science (FOCS) 2009, pp. 43-62, 2009.
Monotone expanders - constructions and applications
Electronic Colloquium on Computational Complexity (ECCC) Report TR09-135, 2009.
Randomness extractors - applications and constructions
Foundations of Software Technology and Theoretical Computer Science FSTTCS), pp. 471-473, 2009.
The Work of Leslie Valiant
Proceedings of Symposium on Theory of Computing (STOC), pp. 1-2, 2009.
Norms, XOR lemmas, and lower bounds for \(GF(2)\) polynomials and multiparty protocols
Proceedings of the Conference on Computational Complexity (CCC) 2007, pp. 141-154, 2007.
Theory of Computing, vol. 4, Article 7, pp. 137-168, 2008.
Algebrization: A New Barrier in Complexity Theory
Proceedings of STOC 2008, pp. 731-740, 2008.
Neighborly Embedded Manifolds
Discrete and Computational Geometry, vol. 40, no. 3, pp. 319-324, 2008.
Spherical Cubes and Rounding in High Dimensions
Proceedings of the 49th Annual Foundations of Computer Science (FOCS) 2008, vol pp. 189-198, 2008.
Euclidean sections of \(l_1^N\) with sublinear randomness and error-correction over the reals
APPROX-RANDOM 2008, pp. 444-454.
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
Theory of Computing, vol. 4, no. 1, pp. 53-76, 2008.
Randomness - A Computational Complexity Perspective
Computer Science – Theory and Applications, vol. 5010, pp. 1-2, 2008.
P, NP and Mathematics - a computational complexity perspective
Proceedings of the ICM 06 (Madrid), vol. 1, EMS Publishing House, Zurich, pp. 665-712, 2007.
One-way multi-party communication lower bound for pointer jumping with applications
Proceedings of the Foundations of Computer Science (FOCS) 2007 Conference, pp. 427-437, 2007.
ECCC Report TR07-079, 2007.
The Randomized Communication Complexity of Set Disjointness
Theory of Computing, vol. 3, no. 1, pp. 211-219, 2007.
Extracting randomness using few independent sources
Proceedings of the 45th FOCS 2004, pp. 384-393, 2004.
SICOMP, vol. 36, no. 4, pp. 1095-1118, 2006.
2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction
Proceedings of STOC 2006, pp. 671-680, 2006.
Applications of the Sum-Product Theorem in Finite Fields
IEEE Conference on Computational Complexity, p. 111, 2006.
Extracting Randomness via Repeated Condensing
Proceedings of the 41st Foundations of Computer Science (FOCS), pp. 22-31, 2000.
SIAM Journal on Computing, vol. 35, no. 5, pp. 1185-1209, 2006.
Derandomizing homomorphism testing in general groups
36th Annual ACM Symposium, STOC 2004, pp. 427-435, 2004.
SICOMP, vol. 36, no. 4, pp. 1215-1230, 2006.
A Strong Direct Product Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
CCC 2005, pp. 52-66, 2005.
Computational Complexity, vol. 15, no. 4, pp. 391-432, 2006.
Iterative construction of Cayley expander graphs
Theory of Computing, vol. 2, no. 1, pp. 91-120, 2006. A shorter version appeared in STOC 2004.
Robust local testability of tensor products of LDPC codes
Proceedings of the 2006 RANDOM conference, pp. 304-315, 2006.
ECCC Report TR06-118, 2006
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
Theory of Computing, vol. 4 (2008), article 3, pp. 53-76.
ECCC Report TR06-105, 2006.
Expander graphs and their applications
Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439-561, 2006.
Reducing the seed length in the Nisan-Wigderson generator
Combinatorica, vol. 26, no. 6, pp. 647-681, 2006.
The Power and Weakness of Randomness in Computation
Latin, pp. 28-29, 2006.
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
Proceedings of the 46th Symposium on Theory of Computing (STOC) 2005, pp. 1-10, 2005.
A randomness-efficient sampler for matrix-valued functions and applications
46th Annual Symposium of Foundations of Computer Science (FOCS) 2005, pp. 397-406, 2005.
Pairwise Independence and Derandomization
Foundations and Trends in Theoretical Computer Science (FTTCS), vol. 1, no. 4, pp. 239-301, 2005.
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Proceedings of IEEE Conference on Computational Complexity, pp. 52-66, 2005.
Pseudorandom Generators in Propositional Proof Complexity
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 34, no. 1, pp. 67-88, 2004. Preliminary version appeared in Symposium on Theory of Computing (STOC) 2000.
Expanders in Group Algebras
Combinatorica, vol. 24, no. 4, pp. 659-680, 2004.
Near Optimal Separation of Tree-like and General Resolution
Combinatorica, vol. 24, no. 4, pp. 585-604, 2004.
A new family of Cayley expanders (?)
36th Annual ACM Symposium on Theory of Computing (STOC), 2004, pp. 445-454, 2004.
Depth Through Breadth, or Why Should We Attend Talks in Other Areas?
Proceedings of Symposium on Theory of Computing (STOC) 2004, p. 579.
The Quantum Communication Complexity of Sampling
Society for Industrial and Applied Mathematics (Siam) Journal on Computing, vol. 32, pp. 1570-1585, 2003.
Simple Analysis of Graph Tests for Linearity and PCP
Random Structures and Algorithms, vol. 22, no. 2, pp 139-160, 2003.
Conference on Computational Complexity, pp. 244-255, 2001. (see also ECCC)
Read-once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
Combinatorica, vol. 22, no. 4, pp. 555-574, 2003.
The Quantum Communication Complexity of Sampling
SIAM Journal on Computing, vol. 32, no. 6, pp 1570-1585, 2003.
Computational Analogues of Entropy
11th International Conference on Random Structures and Algorithms, pp. 200-215, August 2003.
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets
35th Annual ACM Symposium, Symposium on Theory of Computing (STOC) 2003, pp. 612-621, 2003.
Extractors: Optimal up to Constant Factors
35th Annual ACM Symposium, Symposium on Theory of Computing (STOC) 2003, pp. 602-611, 2003.
On Interactive Proofs With a Laconic Power
Journal of Computational Complexity, vol. 2076, p. 334, 2003.
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
Annals of Mathematics, vol. 155, no.1, pp. 157-187, 2002.
Computing Graph Properties by Randomized Subcube Partitions
Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 105-113, 2002.
Derandomization that is Rarely Wrong from Short Advice that is Typically Good
Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 209-223, 2002.
Randomness Conductors and Constant-Degree Expansion Beyond the Degree /2 Barrier
Proceedings of the 34th Symposium on Theory of Computing (STOC), pp. 659-668, 2002.
Expanders from Symmetric Codes
IEEE Conference on Computational Complexity, p. 0016, 2002.
Semi-direct product in groups and Zig-zag product in graphs: Connections and applications
Proceedings of the 42nd Foundations of Computer Science (FOCS), pp. 630-637, 2001.
On Interactive Proofs with a Laconic Power
Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), pp. 334-345, 2001.
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time
Journal of Computer Systems and Sciences (JCSS), vol. 65, no. 4, pp. 672-694, 2002.
Conference on Computational Complexity, pp. 2-12, 2001.
Space Complexity in Propositional Calculus
Society for Industrial and Applied Mathematics (SIAM) Journal of Computing, vol. 31, no. 4, pp. 1184-1211, 2001. Preliminary version appeared in Symposium on Theory of Computing (STOC) 2000.
A \((\log n )^{4/3}\) space algorithm for (s,t) connectivity in undirected graphs
Preliminary version in Proceedings of the 29th Symposium on the Theory of Computing (STOC), pp. 230-239, 1997.
Journal of the ACM, vol. 47, no. 2, 294-311, 2000.
Extractors and Pseudo-random Generators with Optimal Seed Length
Proceedings of the 32nd Symposium on the Theory of Computing (STOC), pp. 1-10, 2000.
On Pseudorandomness with respect to Deterministic Observers
Proceedings of the satellite workshops of the 27th International Colloquium on Automata, Languages and Programming (ICALP), Carleton Scientific (Proc. in Informatics 8), pp. 77-84, 2000.
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Proceedings of the 41st Foundations of Computer Science (FOCS), pp. 3-13, 2000.
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Proceedings of 30th Symposium on the Theory of Computing (STOC), pp. 644-652, 1998.
Combinatorica, 20, 4, 2000.
Superpolynomial lower bounds for monotone span programs
Combinatorica, vol. 19, no. 3, 301-319, 1999.
Techniques for bounding the convergence rate of genetic algorithms
Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Accepted to Journal of Computational Complexity, vol. 10, no. 1, pp. 1-27, 2001.
Preliminary version in Proceedings of the 14th Conference on Computational Complexity, pp. 87-97, 1999.
Deterministic Amplification of Space-Bounded Probabilistic Algorithms
Proceedings of the 14th Conference on Computational Complexity, pp. 188-199, 1999.
Improved derandomization of BPP using a hitting set generator
Proceedings of the RAMDOM 99 Conference, pp. 131-137, 1999.
Near-optimal Conversion of Hardness into Pseudo-randomness
Proceedings of the 40th Foundations of Computer Science (FOCS), pp. 181-190, 1999.
Short Proofs are Narrow -- Resolution made Simple
Proceedings of the 31th STOC, pp. 517-526, 1999.
Journal of the ACM, vol. 48, no. 2, pp. 149-169, 2001.
ECCC Report TR99-022, 1999.
De-randomizing BPP: The State of the Art
IEEE Conference on Computational Complexity, pp. 76-77, 1999.
Probabilistic and Deterministic Approximations of the Permanent
RANDOM / APPROX 1999.
Quantum vs. Classical Communication and Computation
Proceedings of 30th Symposium on Theory of Computing (STOC), pp. 63-68, 1998.
Randomness vs. Time: De-randomization under a uniform assumption
Proceedings of the 39th Foundations of Computer Science (FOCS), pp.734-743, 1998.
Do probabilistic algorithms outperform deterministic ones?
International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 1443, pp. 212-214, 1998.
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Random Structures and Algorithms, vol. 11, no. 4, pp. 315-343, 1997.
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and Transversal Calculus
Proceedings of the 29th Symposium on Theory of Computing (STOC), pp. 739-748, 1997.
Direct Product Results and the GCD Problem, in Old and New Communication Models
Proceedings of the 29th Symposium on Theory of Computing (STOC), pp. 363-372, 1997.
P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
Proceedings of the 29th Symposium on Theory of Computing (STOC), pp. 220-229, 1997.
Theory of Computing: A Scientific Perspective
SIGACT News, vol 28, no. 3, pp 100-102, 1997.
On the Circuit Complexity of Perfect Hashing
Electronic Colloquium on Computational Complexit (ECCC) Report TR96-041, pp. 26-29, 1996.
Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy
Society for Industrial and Applied Mathematics (SIAM) Journal on Discrete Mathematics, vol. 8 no. 4, pp. 78-87, 1996.
A Method for Obtaining Probabilistic Algorithms with Small Tail Probabilities
Algorithmica, vol. 16, no. 4-5, pp. 543-547, 1996.
Lower Bounds on Arithmetic Circuits via Partial Derivatives
Preliminary version in Proceedings of the 36th Foundations of Computer Science ( FOCS), pp. 16-25, 1995.
Computational Complexity, vol. 6, no. 3, pp. 217-234, 1996.
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
Proceedings of 28th Symposium on the Theory of Computing (STOC), pp. 603-611, 1996.
A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
Proceedings of Israel Symposium on Theory of Computing and Systems (ISTCS) 1996, pp. 56-65, 1996.
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
Proceedings of the 37th Foundations of Computer Science (FOCS), pp. 412-421, 1996.
The Future of Computational Complexity Theory: Part I
SIGACT News, vol. 27, no. 3, pp. 6-12, 1996.
Derandomized Graph Products
Computational Complexity, pp. 60-75, 1995.
Search Problems in the Decision Tree Model
Society for Industrial and Applied Mathematics (SIAM) Journal on Discrete Math., vol. 8, pp. 119-132, 1995. (Preliminary version appeared at Proceedings of the 32nd Foundations of Computer Science (FOCS) conference, pp. 576-585, 1991.)
Boolean Complexity Classes vs. Their Arithmetic Analogs
Random Structures and Algorithms, vol. 9, pp. 1-13, 1996.
ECCC Report TR05-049, 1995.
On Data Structures and Asymmetric Communication Complexity
Journal of Computer Systems and Sciences, (JCSS), vol. 57, no. 1, pp. 37-49, 1998.
Preliminary version appeared in Proceedings of the 27th Symposium on the Theory of Computing (STOC), pp. 103-111, 1995.
On the Complexity of Bilinear Forms
Proceedings of the 27th Symposium on the Theory of Computing (STOC), pp. 723-732, 1995.
Honest Verifier vs. Dishonest Verifier in Public Coin Zero-Knowledge Proofs
Advances in Cryptology -- Crypto 1995 (Proceedings), Lecture Note in Computer Science (963), Springer-Verlag, pp. 325-338, 1995.
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity
Computational Complexity, vol. 5, no. 3-4, pp. 191-204, 1995.
Computational Pseudo-Randomness
Israel Symposium on Theory of Computing and Systems (ISTCS), pp. 218-219, 1995.
On Yao's XOR-Lemma
ECCC, TR95-05, 1995.
Hardness vs. Randomness
Journal of Computer Systems and Sciences (JCSS), vol. 49, no. 2, pp. 149-167, 1994.
On the Power of Finite State Automata with both Nondeterministic and Probabilistic States
Society for Industrial and Applied Mathematics(SIAM) Journal on Computing, vol. 27, no. 3, pp. 739-762, June 1998.
Proceedings of the 26th Symposium on the Theory of Computing (STOC), pp. 676-685, 1994.
On Rank vs. Communication Complexity
Combinatorica, vol. 15, no. 4, pp. 557-566, 1995.
Also appeared in Proceedings of the 35th Foundations of Computer Science (FOCS), pp. 831-836, 1994.
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Proceedings of the 26th Symposium on the Theory of Computing (STOC), pp. 574-583, 1994.
Pseudorandomness for Network Algorithms
Proceedings of the 26th Symposium on the Theory of Computing (STOC), pp. 356-364, 1994.
NL/poly \(\subseteq \oplus\) L/poly
Proceedings of the 9th Structures in Complexity Conference, pp. 59-62, July 1994.
The Fusion Method for Lower Bounds in Circuit Complexity
Combinatorics, Paul Erdos is Eighty (vol. 1), Miklos, Sos and Szonyi (Eds.), Bolyai Math. Society, pp. 453-468, 1993.
Combinatorial Characterization of Read-Once Formulae
Journal of Discrete Math. vol. 114, pp. 275-282, 1993.
Rounds in Communication Complexity Revisited
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 22, no. 1, pp. 211-219, 1993.
Composition of the Universal Relation
Advances in Computational Complexity Theory, AMS-DIMACS book series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 119-134, 1993.
\(n^{\Omega(\log n)}\) Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom
Information Processing Letters (IPL), vol. 45, no. 6, pp. 303-307, 1993.
Expanders that beat the eigenvalue bound: explicit construction and applications
Combinatorica, vol. 19, no. 1, 125-138, 1999.
Preliminary version in Proceedings of the 25th Symposium on the Theory of Computing (STOC), pp. 245-251, 1993.
On Span Programs
Proceedings of the 8th Structures in Complexity conference, pp. 102-111, 1993.
On Characterizing Nondeterministic Circuit Size
Proceedings of the 25th Symposium on the Theory of Computing (STOC), pp. 532-545, 1993.
Deterministic Approximate Counting of Depth--2 Circuits
Proceedings of the 2nd ISTCS (Israeli Symposium on Theoretical Computer Science), pp. 18-24, 1993.
Nontrivial Zero-Knowledge Implies One--Way Functions
Proceedings of the 2nd ISTCS, pp. 3-17, 1993.
One-Way Functions are Essential for Non-Trivial Zero-Knowledge
Proceedings of Israel Symposium on Theory of Computing and Systems (ISTCS) 1993, pp. 3-17, 1993.
Geometric Medians
Discrete Math, vol. 108, no. 1, pp. 37-51, 1992.
Non-deterministic Communication Complexity with Few Witnesses
JCSS, vol. 49, no. 2, pp. 247-257, 1994.
Also appeared in 7th Structures in Complexity Theory Conference, pp. 275-281, 1992.
The Complexity of Graph Connectivity
Proceedings of the 17th Mathematical Foundations of Computer Science conference, Havel and Koubek (eds.), Lecture Notes in Computer Science 629, Springer-Verlag, pp. 112-132, 1992.
Quadratic Dynamical Systems
Proceedings of the 33rd FOCS conference, pp. 304-313, 1992.
Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems
Journal of the ACM, vol. 38, no. 1, pp. 691-729, 1991.
Linear--Size Constant--Depth Polylog-- Threshold Circuits,
Information Processing Letters, vol. 39, no. 3, pp. 143-46, 1991.
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs
Complexity Theory, vol. 3, pp. 307-318, 1993.
Proceedings of the 6th Structures in Complexity Theory Conference, pp. 213-19, July 1991.
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Complexity Theory, vol. 1, pp. 311-329, 1991.
Super--Logarithmic Depth Lower Bounds via Direct Sum in Communication Complexity
Computational Complexity, vol. 5, pp. 191-204, 1995.
Preliminary version Proceedings of the 6th Structures in Complexity Theory conference, pp. 299-304, July 1991.
Self Testing / Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd STOC, pp. 33-42, May 1991.
Rounds in Communication Complexity Revisited
Proceedings of the 23rd STOC, pp. 419-429, May 1991.
Siam Journal on Computing, vol. 22, no. 1, pp. 211-219
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Proceedings of the 6th Structures in Complexity Theory Conference, pp. 172-179, July 1991.
Search Problems in the Decision Tree Model
Proceedings of the 32nd FOCS conference, pp. 576-585, 1991.
Siam Journal on Computing, vol. 8, pp. 119-132, 1995
An Analysis of a Simple Genetic Algorithm
Proceedings of the 4th International Conference on Genetic Algorithms, pp. 215-221, July 1991.
Linear Circuits over GF(2)
SIAM Journal on Computing, vol. 19, no. 6 pp. 1064-067, 1990.
Towards Understanding Exclusive Reads
SIAM Journal on Computing, vol. 19, no. 4, pp. 718-727, 1990.
Monotone Circuits for Connectivity require Super-Logarithmic Depth
SIAM Journal on Discrete Mathematics, vol. 3, no. 2, pp. 255-65, 1990.
On Read--Once Threshold Formulae and their Randomized Decision Tree Complexity,
Theoretical Computer Science, vol. 107, no. 1, pp. 63-76, 1990.
Monotone Circuits for Matching require Linear Depth
Journal of the ACM, vol. 39, no. 3, pp. 736-744, July 1992.
Preliminary version in Proceedings of the 22nd STOC, pp. 287-292, May 1990.
On the Power of Randomization in On-line Algorithms
Algorithmica, vol. 11, no. 1, pp. 2-14, 1994.
Proceedings of the 22nd STOC, pp. 379-388, May 1990.
The Tree Model for Hashing: Lower and Upper Bounds
SIAM J. on Computing, vol. 25, no. 5, pp. 936-955, October 1996.
Preliminary version in Proceedings of the 22nd STOC, pp. 244-253, May 1990.
Towards Understanding Exclusive Read
Proceedings of 1st Symposium on Parallel Algorithms and Architectures, pp. 718-727, August 1990.
On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity
5th Structures in Complexity Theory, pp. 78-89, July 1990.
Elsevier, Theoretical Computer Science, 107, pp. 63-76, 1993.
Perfect Hashing, Graph Entropy and Circuit Complexity
Proceedings of the 5th Structures in Complexity Theory Conference, pp. 91-99, July 1990.
Deterministic Simulation of Probabilistic Constant-Depth Circuits
Advances in Computing Research - Randomness and Computation, Eds F. Preparata and S. Micali, vol. 5, pp. 199-23, 1989.
Proceedings of the 26th FOCS pp. 11-19, October 1985.
On Computations with Integer Division
Theoretical Informatics and Applications, vol. 23, no. 1, pp. 101-111, 1989.
Probabilistic Communication Complexity of Boolean Relations
Proceedings of the 30th FOCS, pp. 562-567, 1989.
Dispersers, Deterministic Amplification and Weak Random Sources
Proceedings of the 30th FOCS, pp. 14-19, 1989.
Efficient Identification Schemes Using Two Prover Interactive Proofs
Advances in Cryptography, CRYPTO 89, LNCS 435, Springer-Verlag, pp. 498-506, 1989.
Undirected Connectivity in $O(log^1.5 n)$ Space
Proceedings of the 30th FOCS conference, pp. 24-29, 1989.
The Discrete Logarithm Hides O(log n) Bits
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 17, no. 2, pp. 363-372, 1988.
Simulations among Concurrent-Write PRAMs
Algorithmica, vol. 3, pp. 43-51, 1988.
Relations between Concurrent-Write Models of Parallel Computation
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 17, no. 3, pp. 606-627, 1988.
A tradeoff between Search and Update Time for the Implicit Dictionary Problem
Theoretical Computer Science, vol. 58, pp. 57-68, 1988.
The Complexity of Parallel Search
Journal of Computer and System Sciences, vol. 36, no. 2, pp. 225-253, 1988.
Monotone Connectivity Circuits require Super-logarithmic Depth
Proceedings of the 20th Symposium on the Theory of Computing (STOC), pp. 539-550, May 1988.
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Proceedings of the 20th Symposium on the Theory of Computing (STOC), pp. 113-131, May 1988.
On Computations with Integer Division
Proceedings of the STACS conference, pp. 29-37, 1988.
Hardness vs. Randomness
Proceedings of the 29th Foundations of Computer Science (FOCS), pp. 2-11, 1988.
A Time-Space Tradeoff for Element Distinctness
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 16, no. 1, pp. 97-99, February 1987.
The Complexity of Parallel Sorting
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 16, no. 1, pp. 100-107, 1987.
Lower Bounds for Parallel Random Access Machines with Unbounded Shared Memory
Advances in Computing Research - Parallel and Distributed Computing, Ed. F. Preparata, vol. 4, pp. 1-6, 1987.
How to Play any Mental Game
Proceedings of the 19th Symposium on the Theory of Computing (STOC), pp. 218-229, May 1987.
Constructing a Perfect Matching is in Random NC
Combinatorica, vol. 6, no. 1, pp. 35-48, 1986.
Search in a Known Pattern
Journal of Political Economy, vol. 94, no. 1, pp. 225-230, 1986.
How to Share Memory in a Distributed System
Journal of the ACM, vol. 34, no. 1, pp.116-127, 1987.
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Proceedings of the 27th Foundations of Computer Science, pp. 29-38, October 1986.
Proofs that Yield Nothing but their Validity, and a Methodology of Cryptographic Protocol Design
Proceedings of the 27th FOCS, pp. 174-187, October 1986.
A Trade-off Between Search and Update Time for the Implicit Dictionary Problem
Lecture Notes in Comp. Sci., Springer-Verlag, vol. 226, pp. 50-59, 1986.
Elsevier, vol. 58, issues 1-3, pp. 57-68, June 1988
On Play by Means of Computing Machines
Conference on Theoretical Aspects of Reasoning about Knowledge, pp. 259-274, March 1986.
A Time-Space Tradeoff for Element Distinctness
Proceedings of STACS Conference, Lecture Notes in Comp. Sci., Springer Verlag, vol. 210, pp. 353-358, 1986.
Constructing a Perfect Matching is in Random NC
Proceedings of the 17th STOC, pp. 22-32, May 1985.
Depth-Width Trade-offs in Parallel Processing
SIAM Journal on Computing, vol. 14, no. 2, pp. 303-314, May 1985.
One, Two, Three...Infinity: Lower Bounds for Parallel Computation
Proceedings of the 17th STOC, pp. 48-58, May 1985.
Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th STOC, pp. 464-475, May 1985.
Deterministic Simulation of Probabilistic Constant- Depth Circuits
Proceedings of the 26th FOCS, pp. 11-19, October 1985.
The Complexity of Parallel Sorting
Proceedings of the 26th FOCS, pp. 532-540, October 1985.
The Complexity of Parallel Computation on Matroids
Proceedings of the 26th FOCS, pp. 541-550, October 1985.
Multilayer Grid Embedding
Proceedings of the 26th FOCS, pp. 186-196, October 1985.
Succinct Representation of Graphs
Information and Control, vol. 56, no. 3, pp. 183-198, March 1983.
Dynamic Parallel Memories
Information and Control, vol. 56, no. 3, pp. 174-182, March 1983.
A Fast Parallel Algorithm for the Maximal Independent Set Problem
Journal of the ACM, vol. 32, no. 4, pp.762-773, October 1985.
Preliminary version in Proceedings of the 16th STOC, pp. 266-272, May 1984.
Relations Between Concurrent-Write Models of Parallel Computation
Conference on the 3rd ACM Symposium on Principles of Distributed Computation, pp. 75-88, 1984.
How to Share Memory in a Distributed System
Proceedings of the 25th FOCS, pp. 171-180, October 1984.
Superconcentrators, Generalizers, and Generalized Connectors with Limited Depth
Proceedings of the 15th STOC, pp. 42-51, May 1983.
How Discreet is the Discrete Log?
Proceedings of the 15th STOC, pp. 413-420, May 1983.
Depth-Width Trade-offs in Parallel Computation
Proceedings of the 24th FOCS, pp. 146-153, November 1983.
Siam J. Comput., vol. 14, no. 2, pp. 303-314, May 1985
Planarity of Edge Ordered Graphs
Technical Report #307, Department of EECS, Princeton University, December 1982.
A New Approximate Graph Coloring Algorithm
Proceedings of the 14th STOC, pp. 325-329, May 1982.
The Security of Multi-Party Protocols in Distributed Systems
Proceedings of the Crypto 82 Conference, pp. 167-175, August 1982.
Rectilinear Graphs and their Embedding
Siam J. Comput., vol. 14, no.2, pp. 355-372, May 1985
Rubber Bands, Convex Embeddings and Graph Connectivity
Combinatorica, vol. 8, no. 1, pp. 91-102, 1988
The Parallel Complexity of Element Distinctness is \(\Omega\sqrt{\log n} \)
Siam J. Comput., vol. 1, no. 3, pp. 399-410, August 1988
On the Second Largest Eigenvalue of Hypergraphs
Combinatorica, vol. 15, no. 1, pp. 43-65, 1995.
Universal Sequences for Expander Graphs
Information Processing Letters, vol. 46, no. 2, pp. 67-69, 1993.
Constructing Small Sets that are Uniform in Arithmetic Progressions
Probability, Combinatorics and Complexity, vol. 2, pp. 513-518, 1993.
Information Theoretic Reasons for Computational Difficulty
Proceedings of the International Congress of Mathematicians, pp. 1537-1548, August 1990.
The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
Technical Report #298, Department of EECS, Princeton University, February 1982.
A Search Problem Related to Branch-and-Bound Procedures
Proceedings of the 27th FOCS, pp. 19-28, October, 1986.
A Physical interpretation of graph connectivity and its algorithmic applications
Proceedings of the 27th FOCS, pp.39-48, October 1986.
Not All Keys can be Hashed in Constant Time
Proceedings of the 22nd STOC, pp 244-253, May 1990.
On the Work of Madhu Sudan.no 1, pp. 45--50, 2003.
Computational Hardness and Explicit Constructions of Error Correcting Codes
44th Allerton Conference on Communication, Control and Computing, September 27-29, 2006
260.
The power and weakness of randomness (when you are short on time)
Expander codes over reals, Euclidean sections, and compressed sensing
Proceedings of the 2009 Allerton Conference