The following pages link to Avi Wigderson (Q178716):
Displaying 50 items.
- Population recovery and partial identification (Q255358) (← links)
- Symmetric LDPC codes and local testing (Q519972) (← links)
- One-way multiparty communication lower bound for pointer jumping with applications (Q532058) (← links)
- Near optimal seperation of tree-like and general resolution (Q558312) (← links)
- Extractors and rank extractors for polynomial sources (Q626610) (← links)
- Combinatorial characterization of read-once formulae (Q685684) (← links)
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions (Q685705) (← links)
- Expanders in group algebras (Q812790) (← links)
- Reducing the seed length in the Nisan-Wigderson generator (Q879167) (← links)
- A lower bound on the area of permutation layouts (Q922710) (← links)
- (Q958229) (redirect page) (← links)
- Neighborly embedded manifolds (Q958230) (← links)
- Constructing a perfect matching is in random NC (Q1103639) (← links)
- Simulations among concurrent-write PRAMs (Q1104097) (← links)
- The complexity of parallel search (Q1106664) (← links)
- A tradeoff between search and update time for the implicit dictionary problem (Q1108806) (← links)
- Rubber bands, convex embeddings and graph connectivity (Q1121282) (← links)
- Expanders that beat the eigenvalue bound: Explicit construction and applications (Q1125612) (← links)
- Linear-size constant-depth polylog-threshold circuits (Q1182085) (← links)
- Geometric medians (Q1201233) (← links)
- On read-once threshold formulae and their randomized decision tree complexity (Q1208407) (← links)
- On data structures and asymmetric communication complexity (Q1273860) (← links)
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs (Q1321029) (← links)
- Hardness vs randomness (Q1337458) (← links)
- Non-deterministic communication complexity with few witnesses (Q1337464) (← links)
- Lower bounds on arithmetic circuits via partial derivatives (Q1377574) (← links)
- On interactive proofs with a laconic prover (Q1413647) (← links)
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus (Q1416118) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- Entropy waves, the zig-zag graph product, and new constant-degree expanders (Q1613289) (← links)
- Local expanders (Q1653336) (← links)
- Universal traversal sequences for expander graphs (Q1802060) (← links)
- On the second eigenvalue of hypergraphs (Q1842569) (← links)
- Derandomized graph products (Q1842777) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- On rank vs. communication complexity (Q1906852) (← links)
- Super-logarithmic depth lower bounds via the direct sum in communication complexity (Q1918946) (← links)
- A method for obtaining randomized algorithms with small tail probabilities (Q1923864) (← links)
- 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction (Q1928613) (← links)
- Superpolynomial lower bounds for monotone span programs (Q1977413) (← links)
- Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) (Q2054204) (← links)
- Prediction from partial information and hindsight, with application to circuit lower bounds (Q2311545) (← links)
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom (Q2365817) (← links)
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness (Q2460032) (← links)
- Smooth Boolean Functions are Easy (Q2800553) (← links)
- Quantum Computing Since Democritus, A Book Review (Q2813227) (← links)
- Pseudorandomness for network algorithms (Q2817628) (← links)
- Tiny families of functions with random properties (preliminary version) (Q2817652) (← links)
- On the power of finite automata with both nondeterministic and probabilistic states (preliminary version) (Q2817662) (← links)
- Short proofs are narrow—resolution made simple (Q2819584) (← links)
