Publications

Submitted by charlie on Thu, 2011-11-03 15:53

2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction
Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture
Singular Tuples of Matrices is Not a Null Cone (and, the Symmetries of Algebraic Varieties)
A Fast Parallel Algorithm for the Maximal Independent Set Problem
On the Power and Limitations of Branch and Cut
Polynomial Time Algorithms In Invariant Theory For Torus Actions
The Uncertainty Principle: Variations on a Theme
A Method for Obtaining Probabilistic Algorithms with Small Tail Probabilities
Fractional Sylvester-Gallai theorems
A New Approximate Graph Coloring Algorithm
A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
A Physical interpretation of graph connectivity and its algorithmic applications
A Search Problem Related to Branch-and-Bound Procedures
A Strong Direct Product Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Applications of the Sum-Product Theorem in Finite Fields
A Time-Space Tradeoff for Element Distinctness
A Time-Space Tradeoff for Element Distinctness
A Trade-off Between Search and Update Time for the Implicit Dictionary Problem
A $(\log n )^{4/3}$ space algorithm for (s,t) connectivity in undirected graphs
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
A new family of Cayley expanders (?)
On Linear-Algebraic Notions of Expansion
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
An Asymptotic Bound on the Composition Number of Integer Sums of Squares Formulas
An Optimal "It Ain't Over Till It's Over" Theorem
Barriers for Rank Methods in Arithmetic Complexity
Breaking the Quadratic Barrier for 3-LCC's over the Reals
Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computing
Computational Pseudo-Randomness
Connections Between Graphs and Matrix Spaces
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
De-randomizing BPP: The State of the Art
Degree and Sensitivity: tails of two distributions
Degree and Sensitivity: tails of two distributions
Depth Through Breadth, or Why Should We Attend Talks in Other Areas?
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
Do probabilistic algorithms outperform deterministic ones?
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
Expander codes over reals, Euclidean sections, and compressed sensing
Expanders from Symmetric Codes
Explicit Capacity Approaching Coding for Interactive Communication
Improved rank bounds for design matrices and a new proof of Kelly's theorem
Interactive proofs of proximity: delegating computation in sublinear time
Local Expanders
More barriers for rank methods, via a "numeric to symbolic" transfer
Much Faster Algorithms for Matrix Scaling
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model
Non-commutative arithmetic circuits with division
On Derandomizing Algorithms that Err Extremely Rarely
On Randomness Extraction in ACo
On Rank vs. Communication Complexity
On the Circuit Complexity of Perfect Hashing
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
On the nature of the Theory of Computation (ToC)
One-Way Functions are Essential for Non-Trivial Zero-Knowledge
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Operator Scaling: Theory and Applications
Pairwise Independence and Derandomization
Partial Derivatives in Arithmetic Complexity and Beyond
Population Recovery and Partial Identification
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
Probabilistic and Deterministic Approximations of the Permanent
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Randomness - A Computational Complexity Perspective
Randomness extractors - applications and constructions
Rectilinear Graphs and their Embedding
Reed-Muller codes for random erasures and errors
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
Search Problems in Algebraic Complexity, GCT, and Hardness of Generator for Invariant Rings
Simplified Derandomization of BPP Using a Hitting Set Generator
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
Spherical Cubes: Optimal Foams from Computational Hardness Amplification
Subspace arrangements, graph rigidity and derandomization
Sum-of-Squares Lower Bounds for Sparse PCA
Sum-of-squares lower bounds for planted clique
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals
Sylvester-Gallai Type Theorems for Approximate Collinearity
Teaching and compressing for low VC-dimension
The Future of Computational Complexity Theory: Part I
The Power and Weakness of Randomness in Computation
The Randomized Communication Complexity of Set Disjointness
The Work of Leslie Valiant
The power and weakness of randomness (when you are short on time)
Theory of Computing: A Scientific Perspective
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
Toward Better Formula Lower Bounds: the Composition of a Function and a Universal Relation
Towards Optimal Deterministic Coding for Interactive Communication
Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes
A randomness-efficient sampler for matrix-valued functions and applications
A tradeoff between Search and Update Time for the Implicit Dictionary Problem
Algebrization: A New Barrier in Complexity Theory
An Analysis of a Simple Genetic Algorithm
Are Search and Decision Problems Computationally Equivalent?
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs
Boolean Complexity Classes vs. Their Arithmetic Analogs
Combinatorial Characterization of Read-Once Formulae
Asymptotic Spectra: Theory, Applications and Extensions
Composition of the Universal Relation
Computational Analogues of Entropy
Computational Hardness and Explicit Constructions of Error Correcting Codes
Computing Graph Properties by Randomized Subcube Partitions
Constructing Small Sets that are Uniform in Arithmetic Progressions
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network
Constructing a Perfect Matching is in Random NC
Constructing a Perfect Matching is in Random NC
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Depth-Width Trade-offs in Parallel Computation
Depth-Width Trade-offs in Parallel Processing
Derandomization that is Rarely Wrong from Short Advice that is Typically Good
Derandomized Graph Products
Derandomizing homomorphism testing in general groups
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
Deterministic Amplification of Space-Bounded Probabilistic Algorithms
Deterministic Approximate Counting of Depth--2 Circuits
Deterministic Simulation of Probabilistic Constant- Depth Circuits
Deterministic Simulation of Probabilistic Constant-Depth Circuits
Direct Product Results and the GCD Problem, in Old and New Communication Models
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
Dispersers, Deterministic Amplification and Weak Random Sources
Dynamic Parallel Memories
Efficient Identification Schemes Using Two Prover Interactive Proofs
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
Euclidean sections of $l_1^N$ with sublinear randomness and error-correction over the reals
Expander graphs and their applications
Expanders in Group Algebras
Expanders that beat the eigenvalue bound: explicit construction and applications
Extracting Randomness via Repeated Condensing
Extracting randomness using few independent sources
Extractors and Pseudo-random Generators with Optimal Seed Length
Extractors and rank extractors for polynomial sources
Extractors: Optimal up to Constant Factors
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
Geometric Medians
Hardness vs. Randomness
Hardness vs. Randomness
Honest Verifier vs. Dishonest Verifier in Public Coin Zero-Knowledge Proofs
How Discreet is the Discrete Log?
How to Play any Mental Game
How to Share Memory in a Distributed System
How to Share Memory in a Distributed System
Improved derandomization of BPP using a hitting set generator
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time
Information Theoretic Reasons for Computational Difficulty
Iterative construction of Cayley expander graphs
Kakeya Sets, New Mergers and Old Extractors
Linear Circuits over GF(2)
Linear systems over composite moduli
Linear--Size Constant--Depth Polylog-- Threshold Circuits,
Lower Bounds for Parallel Random Access Machines with Unbounded Shared Memory
Lower Bounds on Arithmetic Circuits via Partial Derivatives
Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy
Monotone Circuits for Connectivity require Super-Logarithmic Depth
Monotone Circuits for Matching require Linear Depth
Monotone Connectivity Circuits require Super-logarithmic Depth
Monotone expanders - constructions and applications
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Multilayer Grid Embedding
NL/poly $\subseteq \oplus$ L/poly
Near Optimal Separation of Tree-like and General Resolution
Near-optimal Conversion of Hardness into Pseudo-randomness
Neighborly Embedded Manifolds
New Direct-Product Testers and 2-Query PCPs
Non-commutative circuits and the sum-of-squares problem
Non-deterministic Communication Complexity with Few Witnesses
Nontrivial Zero-Knowledge Implies One--Way Functions
Norms, XOR lemmas, and lower bounds for $GF(2)$ polynomials and multiparty protocols
Not All Keys can be Hashed in Constant Time
On Characterizing Nondeterministic Circuit Size
On Computations with Integer Division
On Computations with Integer Division
On Data Structures and Asymmetric Communication Complexity
On Interactive Proofs With a Laconic Power
On Interactive Proofs with a Laconic Power
On Play by Means of Computing Machines
On Pseudorandomness with respect to Deterministic Observers
On Read--Once Threshold Formulae and their Randomized Decision Tree Complexity,
On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity
On Span Programs
On Yao's XOR-Lemma
On the Complexity of Bilinear Forms
On the Power of Finite State Automata with both Nondeterministic and Probabilistic States
On the Power of Randomization in On-line Algorithms
On the Second Largest Eigenvalue of Hypergraphs
On the Work of Madhu Sudan.no 1, pp. 45--50, 2003.
One, Two, Three...Infinity: Lower Bounds for Parallel Computation
One-way multi-party communication lower bound for pointer jumping with applications
P, NP and Mathematics - a computational complexity perspective
P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
Perfect Hashing, Graph Entropy and Circuit Complexity
Planarity of Edge Ordered Graphs
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Probabilistic Communication Complexity of Boolean Relations
Proofs that Yield Nothing but their Validity, and a Methodology of Cryptographic Protocol Design
Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems
Pseudorandom Generators in Propositional Proof Complexity
Pseudorandomness for Network Algorithms
Public Key Cryptography from Different Assumptions
Quadratic Dynamical Systems
Quantum vs. Classical Communication and Computation
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Randomness Conductors and Constant-Degree Expansion Beyond the Degree /2 Barrier
Randomness vs. Time: De-randomization under a uniform assumption
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and Transversal Calculus
Read-once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
Rectilinear Graphs and their Embedding
Reducing the seed length in the Nisan-Wigderson generator
Relationless completeness and separations
Relations Between Concurrent-Write Models of Parallel Computation
Relations between Concurrent-Write Models of Parallel Computation
Restriction Access
Robust local testability of tensor products of LDPC codes
Rounds in Communication Complexity Revisited
Rounds in Communication Complexity Revisited
Rubber Bands, Convex Embeddings and Graph Connectivity
Search Problems in the Decision Tree Model
Search Problems in the Decision Tree Model
Search in a Known Pattern
Self Testing / Correcting for Polynomials and for Approximate Functions
Semi-direct product in groups and Zig-zag product in graphs: Connections and applications
Short Proofs are Narrow -- Resolution made Simple
Simple Analysis of Graph Tests for Linearity and PCP
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
Simulations among Concurrent-Write PRAMs
Space Complexity in Propositional Calculus
Spherical Cubes and Rounding in High Dimensions
Succinct Representation of Graphs
Super--Logarithmic Depth Lower Bounds via Direct Sum in Communication Complexity
Superconcentrators, Generalizers, and Generalized Connectors with Limited Depth
Superpolynomial lower bounds for monotone span programs
Symmetric LDPC codes and local testing
Techniques for bounding the convergence rate of genetic algorithms
The Complexity of Graph Connectivity
The Complexity of Parallel Computation on Matroids
The Complexity of Parallel Search
The Complexity of Parallel Sorting
The Complexity of Parallel Sorting
The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
The Discrete Logarithm Hides O(log n) Bits
The Fusion Method for Lower Bounds in Circuit Complexity
The Parallel Complexity of Element Distinctness is $\Omega\sqrt{\log n} $
The Quantum Communication Complexity of Sampling
The Quantum Communication Complexity of Sampling
The Security of Multi-Party Protocols in Distributed Systems
The Tree Model for Hashing: Lower and Upper Bounds
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Towards Understanding Exclusive Read
Towards Understanding Exclusive Reads
Towards a study of low-complexity graphs
Undirected Connectivity in $O(log^1.5 n)$ Space
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Universal Sequences for Expander Graphs
$n^{\Omega(\log n)}$ Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom

‹ Mika Göös up 2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction ›

Avi Wigderson

You are here