Avi Wigderson

According to our database1, Avi Wigderson
  • authored at least 333 papers between 1982 and 2018.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Barriers for Rank Methods in Arithmetic Complexity.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals.
Theory of Computing, 2017

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.
SIAM J. Comput., 2017

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Barriers for Rank Methods in Arithmetic Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory.
CoRR, 2017

Interactions of Computational Complexity Theory and Mathematics.
CoRR, 2017

Barriers for Rank Methods in Arithmetic Complexity.
CoRR, 2017

Much Faster Algorithms for Matrix Scaling.
CoRR, 2017

Technical Perspective: Low-depth arithmetic circuits.
Commun. ACM, 2017

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Much Faster Algorithms for Matrix Scaling.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Population recovery and partial identification.
Machine Learning, 2016

Local Expanders.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Degree and Sensitivity: tails of two distributions.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Degree and Sensitivity: tails of two distributions.
CoRR, 2016

Algorithmic aspects of Brascamp-Lieb inequalities.
CoRR, 2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
CoRR, 2016

Symmetric LDPC codes and local testing.
Combinatorica, 2016

Towards Optimal Deterministic Coding for Interactive Communication.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Degree and Sensitivity: Tails of Two Distributions.
Proceedings of the 31st Conference on Computational Complexity, 2016

Proof Complexity Lower Bounds from Algebraic Circuit Complexity.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Non-Commutative Arithmetic Circuits with Division.
Theory of Computing, 2015

Reed-Muller Codes for Random Erasures and Errors.
IEEE Trans. Information Theory, 2015

Invited Articles Foreword.
J. ACM, 2015

Teaching and compressing for low VC-dimension.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
Electronic Colloquium on Computational Complexity (ECCC), 2015

On Randomness Extraction in AC0.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Towards Optimal Deterministic Coding for Interactive Communication.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Teaching and compressing for low VC-dimension.
CoRR, 2015

Sum-of-squares lower bounds for planted clique.
CoRR, 2015

Sum-of-Squares Lower Bounds for Sparse PCA.
CoRR, 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
CoRR, 2015

A deterministic polynomial time algorithm for non-commutative rational identity testing.
CoRR, 2015

Sum-of-squares Lower Bounds for Planted Clique.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Reed-Muller Codes for Random Erasures and Errors.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Sum-of-Squares Lower Bounds for Sparse PCA.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Compressing and Teaching for Low VC-Dimension.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

On Randomness Extraction in AC0.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
Reed-Muller codes for random erasures and errors.
CoRR, 2014

On derandomizing algorithms that err extremely rarely.
Proceedings of the Symposium on Theory of Computing, 2014

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.
Proceedings of the Symposium on Theory of Computing, 2014

Breaking the quadratic barrier for 3-LCC's over the reals.
Proceedings of the Symposium on Theory of Computing, 2014

Non-commutative arithmetic circuits with division.
Proceedings of the Innovations in Theoretical Computer Science, 2014

2013
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On Derandomizing Algorithms that Err Extremely Rarely.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Breaking the quadratic barrier for 3-LCCs over the Reals.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Breaking the quadratic barrier for 3-LCCs over the Reals.
CoRR, 2013

Interactive proofs of proximity: delegating computation in sublinear time.
Proceedings of the Symposium on Theory of Computing Conference, 2013

2012
New Direct-Product Testers and 2-Query PCPs.
SIAM J. Comput., 2012

Population Recovery and Partial Identification.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Improved rank bounds for design matrices and a new proof of Kelly's theorem.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Sylvester-Gallai type theorems for approximate collinearity.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Sylvester-Gallai type theorems for approximate collinearity
CoRR, 2012

Improved rank bounds for design matrices and a new proof of Kelly's theorem
CoRR, 2012

Spherical cubes: optimal foams from computational hardness amplification.
Commun. ACM, 2012

Restriction access.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Population Recovery and Partial Identification.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Kakeya Sets, New Mergers, and Old Extractors.
SIAM J. Comput., 2011

Partial Derivatives in Arithmetic Complexity and Beyond.
Foundations and Trends in Theoretical Computer Science, 2011

Restriction Access.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

On the Circuit Complexity of Perfect Hashing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Simplified Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Yao's XOR-Lemma.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
Monotone Expanders: Constructions and Applications.
Theory of Computing, 2010

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized.
SIAM J. Comput., 2010

Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors.
J. ACM, 2010

Relationless completeness and separations.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Non-commutative circuits and the sum-of-squares problem.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
CoRR, 2010

Non-commutative circuits and the sum-of-squares problem.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Public-key cryptography from different assumptions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Symmetric LDPC Codes and Local Testing.
Proceedings of the Property Testing, 2010

Symmetric LDPC Codes and Local Testing.
Proceedings of the Innovations in Computer Science, 2010

Relationless Completeness and Separations.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009
Algebrization: A New Barrier in Complexity Theory.
TOCT, 2009

New Direct-Product Testers and 2-Query PCPs.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Monotone expanders - constructions and applications.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Linear systems over composite moduli.
Electronic Colloquium on Computational Complexity (ECCC), 2009

One-way multiparty communication lower bound for pointer jumping with applications.
Combinatorica, 2009

Extractors And Rank Extractors For Polynomial Sources.
Computational Complexity, 2009

The work of Leslie Valiant.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

New direct-product testers and 2-query PCPs.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Towards a Study of Low-Complexity Graphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Randomness extractors -- applications and constructions.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Linear Systems over Composite Moduli.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications.
Theory of Computing, 2008

Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols.
Theory of Computing, 2008

Public Key Cryptography from Different Assumptions.
IACR Cryptology ePrint Archive, 2008

Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Kakeya sets, new mergers and old extractors.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Algebrization: A New Barrier in Complexity Theory.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Neighborly Embedded Manifolds.
Discrete & Computational Geometry, 2008

Uniform direct product theorems: simplified, optimized, and derandomized.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Algebrization: a new barrier in complexity theory.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Spherical Cubes and Rounding in High Dimensions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Kakeya Sets, New Mergers and Old Extractors.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Randomness - A Computational Complexity Perspective.
Proceedings of the Computer Science, 2008

Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.
Proceedings of the Approximation, 2008

2007
The Randomized Communication Complexity of Set Disjointness.
Theory of Computing, 2007

One-way multi-party communication lower bound for pointer jumping with applications.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Extractors and Rank Extractors for Polynomial Sources.
Electronic Colloquium on Computational Complexity (ECCC), 2007

One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Extractors and Rank Extractors for Polynomial Sources.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006
Iterative Construction of Cayley Expander Graphs.
Theory of Computing, 2006

Derandomizing Homomorphism Testing in General Groups.
SIAM J. Comput., 2006

Extracting Randomness via Repeated Condensing.
SIAM J. Comput., 2006

Extracting Randomness Using Few Independent Sources.
SIAM J. Comput., 2006

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Robust Local Testability of Tensor Products of LDPC Codes.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Reducing The Seed Length In The Nisan-Wigderson Generator.
Combinatorica, 2006

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Computational Complexity, 2006

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

The Power and Weakness of Randomness in Computation.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Applications of the Sum-Product Theorem in Finite Fields.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

Robust Local Testability of Tensor Products of LDPC Codes.
Proceedings of the Approximation, 2006

2005
Pairwise Independence and Derandomization.
Foundations and Trends in Theoretical Computer Science, 2005

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications
Electronic Colloquium on Computational Complexity (ECCC), 2005

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Pseudorandom Generators in Propositional Proof Complexity.
SIAM J. Comput., 2004

Expanders In Group Algebras.
Combinatorica, 2004

Near Optimal Separation Of Tree-Like And General Resolution.
Combinatorica, 2004

Depth through breadth, or why should we attend talks in other areas?
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Derandomizing homomorphism testing in general groups.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

A new family of Cayley expanders (?).
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Extracting Randomness Using Few Independent Sources.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
The Quantum Communication Complexity of Sampling.
SIAM J. Comput., 2003

Simple analysis of graph tests for linearity and PCP.
Random Struct. Algorithms, 2003

Extractors: optimal up to constant factors.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Computational Analogues of Entropy.
Proceedings of the Approximation, 2003

Zigzag Products, Expander Constructions, Connections, and Applications.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002
Space Complexity in Propositional Calculus.
SIAM J. Comput., 2002

In search of an easy witness: exponential time vs. probabilistic polynomial time.
J. Comput. Syst. Sci., 2002

Derandomization that is rarely wrong from short advice that is typically good
Electronic Colloquium on Computational Complexity (ECCC), 2002

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Combinatorica, 2002

On interactive proofs with a laconic prover.
Computational Complexity, 2002

Expanders from symmetric codes.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Randomness conductors and constant-degree lossless expanders.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Computing Graph Properties by Randomized Subcube Partitions.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Expanders from Symmetric Codes.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Randomness Conductors and Constant-Degree Lossless Expanders.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Randomness vs Time: Derandomization under a Uniform Assumption.
J. Comput. Syst. Sci., 2001

Short proofs are narrow - resolution made simple.
J. ACM, 2001

On Interactive Proofs with a Laconic Prover
Electronic Colloquium on Computational Complexity (ECCC), 2001

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Electronic Colloquium on Computational Complexity (ECCC), 2001

Depth-3 arithmetic circuits over fields of characteristic zero.
Computational Complexity, 2001

On Interactive Proofs with a Laconic Prover.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Simple Analysis of Graph Tests for Linearity and PCP.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs.
J. ACM, 2000

Extracting Randomness via Repeated Condensing
Electronic Colloquium on Computational Complexity (ECCC), 2000

On Pseudorandomness with respect to Deterministic Observers.
Electronic Colloquium on Computational Complexity (ECCC), 2000

Pseudorandom Generators in Propositional Proof Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2000

Extractors and pseudo-random generators with optimal seed length
Electronic Colloquium on Computational Complexity (ECCC), 2000

Near-Optimal Separation of Treelike and General Resolution
Electronic Colloquium on Computational Complexity (ECCC), 2000

Simplified derandomization of BPP using a hitting set generator.
Electronic Colloquium on Computational Complexity (ECCC), 2000

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Combinatorica, 2000

Extractors and pseudo-random generators with optimal seed length.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Space complexity in propositional calculus.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On Pseudorandomness with respect to Deterministic Observes.
ICALP Satellite Workshops, 2000

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Extracting Randomness via Repeated Condensing.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Pseudorandom Generators in Propositional Proof Complexity.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Techniques for bounding the convergence rate of genetic algorithms.
Random Struct. Algorithms, 1999

Space Complexity in Propositional Calculus
Electronic Colloquium on Computational Complexity (ECCC), 1999

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Electronic Colloquium on Computational Complexity (ECCC), 1999

Short Proofs are Narrow - Resolution made Simple
Electronic Colloquium on Computational Complexity (ECCC), 1999

Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications.
Combinatorica, 1999

Superpolynomial Lower Bounds for Monotone Span Programs.
Combinatorica, 1999

Short Proofs are Narrow - Resolution Made Simple.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Probabilistic and Deterministic Approximations of the Permanent (abstract).
Proceedings of the Randomization, 1999

Improved Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Randomization, 1999

Near-Optimal Conversion of Hardness into Pseudo-Randomness.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

De-Randomizing BPP: The State of the Art.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Short Proofs Are Narrow - Resolution Made Simple (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

Deterministic Amplification of Space-Bounded Probabilistic Algorithms.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
On the Power of Finite Automata with Both Nondeterministic and Probabilistic States.
SIAM J. Comput., 1998

On Data Structures and Asymmetric Communication Complexity.
J. Comput. Syst. Sci., 1998

Deterministic Amplification of Space Bounded Probabilistic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 1998

A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Quantum vs. Classical Communication and Computation.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Do Probabilistic Algorithms Outperform Deterministic Ones?
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Randomness vs. Time: De-Randomization under a Uniform Assumption.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

The Quantum Communication Complexity of Sampling.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Theory of computing: a scientific perspective (extended abstract).
SIGACT News, 1997

Tiny families of functions with random properties: A quality-size trade-off for hashing.
Random Struct. Algorithms, 1997

Lower Bounds on Arithmetic Circuits Via Partial Derivatives.
Computational Complexity, 1997

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Direct Product Results and the GCD Problem, in Old and New Communication Models.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

SL <= L4/3.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996
The future of computational complexity theory: part I.
SIGACT News, 1996

The Tree Model for Hashing: Lower and Upper Bounds.
SIAM J. Comput., 1996

Boolean complexity classes vs. their arithmetic analogs.
Random Struct. Algorithms, 1996

On the Circuit Complexity of Perfect Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1996

Theory of Computing: A Scientific Perspective.
ACM Comput. Surv., 1996

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.
Algorithmica, 1996

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

A New NCAlgorithm for Perfect Matching in Bipartite Cubic Graphs.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy.
SIAM J. Discrete Math., 1995

Search Problems in the Decision Tree Model.
SIAM J. Discrete Math., 1995

On Yao's XOR-Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1995

Boolean Complexity Classes vs. Their Arithmetic Analogs
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Rank vs. Communication Complexity.
Combinatorica, 1995

On the Second Eigenvalue of Hypergraphs.
Combinatorica, 1995

Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity.
Computational Complexity, 1995

Derandomized Graph Products.
Computational Complexity, 1995

On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

On data structures and asymmetric communication complexity.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Computational Pseudo-Randomness.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs.
Proceedings of the Advances in Cryptology, 1995

1994
Hardness vs Randomness.
J. Comput. Syst. Sci., 1994

Non-Deterministic Communication Complexity with Few Witnesses.
J. Comput. Syst. Sci., 1994

Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1994

On Rank vs. Communication Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1994

On the Power of Randomization in On-Line Algorithms.
Algorithmica, 1994

The amazing power of pairwise independence (abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Pseudorandomness for network algorithms.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On the power of finite automata with both nondeterministic and probabilistic states (preliminary version).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

The Wonders of the Digital Envelope - A Crash Course in Modern Cryptography.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

On Rank vs. Communication Complexity
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

NL/poly <= +/poly (Preliminary Version).
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

A Direct Product Theorem.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity.
Theor. Comput. Sci., 1993

Rounds in Communication Complexity Revisited.
SIAM J. Comput., 1993

n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom.
Inf. Process. Lett., 1993

Universal Traversal Sequences for Expander Graphs.
Inf. Process. Lett., 1993

Combinatorial characterization of read-once formulae.
Discrete Mathematics, 1993

Constructing Small Sets that are Uniform in Arithmetic Progressions.
Combinatorics, Probability & Computing, 1993

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
Computational Complexity, 1993

Expanders that beat the eigenvalue bound: explicit construction and applications.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Characterizing non-deterministic circuit size.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Deterministic Approximate Counting of Depth-2 Circuits.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

On Span Programs.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Monotone Circuits for Matching Require Linear Depth.
J. ACM, 1992

Geometric medians.
Discrete Mathematics, 1992

The Complexity of Graph Connectivity.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Quadratic Dynamical Systems (Preliminary Version)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Undirected Connectivity in O(log ^1.5 n) Space
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Non-deterministic Communication Complexity with Few Witness.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.
J. ACM, 1991

Linear-Size Constant-Depth Polylog-Treshold Circuits.
Inf. Process. Lett., 1991

Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions.
Computational Complexity, 1991

A Lower Bound on the Area of Permutation Layouts.
Algorithmica, 1991

Rounds in Communication Complexity Revisited
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Self-Testing/Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

An Analysis of a Simple Genetic Algorithm.
Proceedings of the 4th International Conference on Genetic Algorithms, 1991

Search Problems in the Decision Tree Model (Preliminary Version)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990
Monotone Circuits for Connectivity Require Super-Logarithmic Depth.
SIAM J. Discrete Math., 1990

Toward Understanding Exclusive Read.
SIAM J. Comput., 1990

Linear Circuits over GF(2).
SIAM J. Comput., 1990

Monotone Circuits for Matching Require Linear Depth
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Not All Keys Can Be Hashed in Constant Time (Preliminary Version)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Randomization in Online Algorithms (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Composition of the Universal Relation.
Proceedings of the Advances In Computational Complexity Theory, 1990

Perfect Hashing, Graph Entropy, and Circuit Complexity.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
On Computations with Integer Division.
ITA, 1989

Deterministic Simulation of Probabilistic Constant Depth Circuits.
Advances in Computing Research, 1989

Towards Understanding Exclusive Read.
SPAA, 1989

Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Efficient Identification Schemes Using Two Prover Interactive Proofs.
Proceedings of the Advances in Cryptology, 1989

Hardness vs. Randomness - A Survey (abstract).
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Theor. Comput. Sci., 1988

The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)).
SIAM J. Discrete Math., 1988

The Discrete Logarithm Hides O(log n) Bits.
SIAM J. Comput., 1988

Relations Between Concurrent-Write Models of Parallel Computation.
SIAM J. Comput., 1988

The Complexity of Parallel Search.
J. Comput. Syst. Sci., 1988

Rubber bands, convex embeddings and graph connectivity.
Combinatorica, 1988

Simulations Among Concurrent-Write PRAMs.
Algorithmica, 1988

Monotone Circuits for Connectivity Require Super-logarithmic Depth
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

On Computations with Integer Division.
Proceedings of the STACS 88, 1988

Hardness vs. Randomness (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
The Complexity of Parallel Sorting.
SIAM J. Comput., 1987

A Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput., 1987

How to share memory in a distributed system.
J. ACM, 1987

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
Constructing a perfect matching is in random NC.
Combinatorica, 1986

On Play by Means of Computing Machines.
Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

A Time-Space Tradeoff for Element Distinctness.
Proceedings of the STACS 86, 1986

Proofs that Release Minimum Knowledge.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

On a Search Problem Related to Branch-and-Bound Procedures
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design.
Proceedings of the Advances in Cryptology, 1986

1985
A Fast Parallel Algorithm for the Maximal Independent Set Problem
J. ACM, October, 1985

Trade-Offs Between Depth and Width in Parallel Computation.
SIAM J. Comput., 1985

Rectilinear Graphs and their Embeddings.
SIAM J. Comput., 1985

Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Constructing a Perfect Matching is in Random NC
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Parallel Computation on Matroids
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

The Complexity of Parallel Sorting
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Multi-Layer Grid Embeddings
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
A Fast Parallel Algorithm for the Maximal Independent Set Problem
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Relations Between Concurrent-Write Models of Parallel Computation.
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

How to Share Memory in a Distributed System (A Preliminary Version)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Improving the Performance Guarantee for Approximate Graph Coloring
J. ACM, October, 1983

Dynamic Parallel Memories
Information and Control, March, 1983

Succinct Representations of Graphs
Information and Control, March, 1983

How Discreet is the Discrete Log?
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
A New Approximate Graph Coloring Algorithm
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

On the Security of Multi-Party Protocols in Distributed Systems.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982


  Loading...