Travelled to:1 × Denmark
1 × France
2 × Greece
25 × USA
3 × Canada
Collaborated with:∅ R.Impagliazzo O.Goldreich N.Nisan S.P.Vadhan R.M.Karp B.Barak E.Ben-Sasson M.Karchmer E.Upfal A.Shpilka R.Raz R.Shaltiel F.M.a.d.Heide Z.Dvir A.Yehudayoff V.Kabanets A.A.Razborov M.Ben-Or S.Goldwasser S.Aaronson O.Reingold R.Meshulam D.Zuckerman D.L.Long M.Sudan F.E.Fich A.Borodin E.Abbe R.Meka A.Potechin S.Saraf G.N.Rothblum B.Applebaum P.Hrubes S.Arora D.Steurer E.Rozenman A.Shalev H.Buhrman R.Cleve N.Linial A.Samorodnitsky I.Parnafes A.C.Yao J.Y.Gil S.Micali D.Gavinsky O.Meir O.Weinstein R.Jaiswal A.Rao C.Lu M.R.Capalbo M.Alekhnovich R.Armoni A.Ta-Shma S.Zhou P.B.Miltersen S.Safra A.Condon L.Hellerstein S.Pottle J.Kilian P.Ragde D.Dolev C.Dwork N.Pippenger G.Kindler B.Sudakov P.Gemmell R.J.Lipton R.Rubinfeld S.Ben-David G.Tardos L.Babai A.Gál J.Kollár L.Rónyai T.Szabó
Talks about:algorithm (7) complex (7) random (7) bound (6) new (6) problem (5) circuit (5) comput (5) proof (5) graph (5)
Person: Avi Wigderson
DBLP: Wigderson:Avi
Facilitated 1 volumes:
EdContributed to:
20152014201320112010
200920092008200620052004200320022001200019991998199819971996199519941993199119901988198719861985198419831982Wrote 60 papers:
- STOC-2015-AbbeSW #fault #random
- Reed-Muller Codes for Random Erasures and Errors (EA, AS, AW), pp. 297–306.
- STOC-2015-MekaPW #bound #clique
- Sum-of-squares Lower Bounds for Planted Clique (RM, AP, AW), pp. 87–96.
- STOC-2014-DvirSW #polynomial
- Breaking the quadratic barrier for 3-LCC’s over the reals (ZD, SS, AW), pp. 784–793.
- STOC-2014-GavinskyMWW #approach #bound #complexity #composition #towards
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture (DG, OM, OW, AW), pp. 213–222.
- STOC-2014-GoldreichW #algorithm #on the
- On derandomizing algorithms that err extremely rarely (OG, AW), pp. 109–118.
- STOC-2013-RothblumVW #interactive #proving #proximity #sublinear
- Interactive proofs of proximity: delegating computation in sublinear time (GNR, SPV, AW), pp. 793–802.
- STOC-2011-BarakDYW #bound #design #geometry #matrix #rank
- Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes (BB, ZD, AY, AW), pp. 519–528.
- STOC-2010-ApplebaumBW #encryption
- Public-key cryptography from different assumptions (BA, BB, AW), pp. 171–180.
- STOC-2010-HrubesWY #commutative #problem
- Non-commutative circuits and the sum-of-squares problem (PH, AW, AY), pp. 667–676.
- ICALP-v1-2009-AroraSW #case study #graph #towards
- Towards a Study of Low-Complexity Graphs (SA, DS, AW), pp. 119–131.
- STOC-2009-ImpagliazzoKW
- New direct-product testers and 2-query PCPs (RI, VK, AW), pp. 131–140.
- STOC-2009-Wigderson
- The work of Leslie Valiant (AW), pp. 1–2.
- STOC-2008-AaronsonW #complexity #named
- Algebrization: a new barrier in complexity theory (SA, AW), pp. 731–740.
- STOC-2008-ImpagliazzoJKW #theorem
- Uniform direct product theorems: simplified, optimized, and derandomized (RI, RJ, VK, AW), pp. 579–588.
- STOC-2006-BarakRSW #graph
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction (BB, AR, RS, AW), pp. 671–680.
- STOC-2005-BarakKSSW #graph #independence #simulation
- Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors (BB, GK, RS, BS, AW), pp. 1–10.
- STOC-2004-RozenmanSW #product line
- A new family of Cayley expanders (?) (ER, AS, AW), pp. 445–454.
- STOC-2004-ShpilkaW #morphism #testing
- Derandomizing homomorphism testing in general groups (AS, AW), pp. 427–435.
- STOC-2004-Wigderson #question #why
- Depth through breadth, or why should we attend talks in other areas? (AW), p. 579.
- STOC-2003-Ben-SassonSVW #testing
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets (EBS, MS, SPV, AW), pp. 612–621.
- STOC-2003-LuRVW #constant #named
- Extractors: optimal up to constant factors (CJL, OR, SPV, AW), pp. 602–611.
- STOC-2002-CapalboRVW
- Randomness conductors and constant-degree lossless expanders (MRC, OR, SPV, AW), pp. 659–668.
- STOC-2002-MeshulamW #symmetry
- Expanders from symmetric codes (RM, AW), pp. 669–677.
- ICALP-2001-GoldreichVW #interactive #on the #proving
- On Interactive Proofs with a Laconic Prover (OG, SPV, AW), pp. 334–345.
- STOC-2000-AlekhnovichBRW #calculus #complexity
- Space complexity in propositional calculus (MA, EBS, AAR, AW), pp. 358–367.
- STOC-2000-ImpagliazzoSW #generative #pseudo
- Extractors and pseudo-random generators with optimal seed length (RI, RS, AW), pp. 1–10.
- STOC-1999-Ben-SassonW #proving
- Short Proofs are Narrow — Resolution Made Simple (EBS, AW), pp. 517–526.
- ICALP-1998-Wigderson #algorithm #probability #question
- Do Probabilistic Algorithms Outperform Deterministic Ones? (AW), pp. 212–214.
- STOC-1998-BuhrmanCW #communication #quantum
- Quantum vs. Classical Communication and Computation (HB, RC, AW), pp. 63–68.
- STOC-1998-LinialSW #algorithm #approximate #matrix #polynomial #scalability
- A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (NL, AS, AW), pp. 644–652.
- STOC-1997-ArmoniTWZ
- SL <= L4/3 (RA, ATS, AW, SZ), pp. 230–239.
- STOC-1997-ImpagliazzoW #exponential
- P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma (RI, AW), pp. 220–229.
- STOC-1997-ParnafesRW #communication #modelling #problem
- Direct Product Results and the GCD Problem, in Old and New Communication Models (IP, RR, AW), pp. 363–372.
- STOC-1997-RazborovWY #branch #calculus #proving #source code
- Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus (AAR, AW, ACCY), pp. 739–748.
- STOC-1996-BabaiGKRSW #bound #graph #source code
- Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs (LB, AG, JK, LR, TS, AW), pp. 603–611.
- STOC-1995-MiltersenNSW #communication #complexity #data type #on the #symmetry
- On data structures and asymmetric communication complexity (PBM, NN, SS, AW), pp. 103–111.
- STOC-1995-NisanW #complexity #memory management #on the
- On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern (NN, AW), pp. 723–732.
- STOC-1994-CondonHPW #automaton #finite #nondeterminism #on the #power of #probability
- On the power of finite automata with both nondeterministic and probabilistic states (AC, LH, SP, AW), pp. 676–685.
- STOC-1994-GoldreichW #product line #random #trade-off
- Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing (OG, AW), pp. 574–584.
- STOC-1994-ImpagliazzoNW #algorithm #network #pseudo
- Pseudorandomness for network algorithms (RI, NN, AW), pp. 356–364.
- STOC-1994-Wigderson #independence #power of
- The amazing power of pairwise independence (AW), pp. 645–647.
- STOC-1993-KarchmerW #nondeterminism
- Characterizing non-deterministic circuit size (MK, AW), pp. 532–540.
- STOC-1993-WigdersonZ #bound
- Expanders that beat the eigenvalue bound: explicit construction and applications (AW, DZ), pp. 245–251.
- STOC-1991-GemmellLRSW #approximate #self
- Self-Testing/Correcting for Polynomials and for Approximate Functions (PG, RJL, RR, MS, AW), pp. 32–42.
- STOC-1991-NisanW #communication #complexity #revisited
- Rounds in Communication Complexity Revisited (NN, AW), pp. 419–429.
- STOC-1990-Ben-DavidBKTW #algorithm #on the #online #power of
- On the Power of Randomization in Online Algorithms (SBD, AB, RMK, GT, AW), pp. 379–386.
- STOC-1990-GilHW #constant
- Not All Keys Can Be Hashed in Constant Time (JYG, FMadH, AW), pp. 244–253.
- STOC-1990-RazW #linear
- Monotone Circuits for Matching Require Linear Depth (RR, AW), pp. 287–292.
- STOC-1988-Ben-OrGKW #how #interactive #multi #proving
- Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions (MBO, SG, JK, AW), pp. 113–131.
- STOC-1988-Ben-OrGW #distributed #fault tolerance #theorem
- Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (MBO, SG, AW), pp. 1–10.
- STOC-1988-KarchmerW
- Monotone Circuits for Connectivity Require Super-logarithmic Depth (MK, AW), pp. 539–550.
- STOC-1987-GoldreichMW #game studies #how #protocol #theorem
- How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority (OG, SM, AW), pp. 218–229.
- ICALP-1986-BorodinFHUW #problem #taxonomy #trade-off
- A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem (AB, FEF, FMadH, EU, AW), pp. 50–59.
- STOC-1985-FichHRW #bound #infinity #parallel
- One, Two, Three … Infinity: Lower Bounds for Parallel Computation (FEF, FMadH, PR, AW), pp. 48–58.
- STOC-1985-KarpUW #random
- Constructing a Perfect Matching is in Random NC (RMK, EU, AW), pp. 22–32.
- STOC-1985-KarpUW85a #problem #question
- Are Search and Decision Problems Computationally Equivalent? (RMK, EU, AW), pp. 464–475.
- STOC-1984-KarpW #algorithm #independence #parallel #performance #problem #set
- A Fast Parallel Algorithm for the Maximal Independent Set Problem (RMK, AW), pp. 266–272.
- STOC-1983-DolevDPW
- Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (DD, CD, NP, AW), pp. 42–51.
- STOC-1983-LongW #how #question
- How Discreet is the Discrete Log? (DLL, AW), pp. 413–420.
- STOC-1982-Wigderson #algorithm #approximate #graph
- A New Approximate Graph Coloring Algorithm (AW), pp. 325–329.