 | 2009 |
|---|
| 236 |       | Sanjeev Arora,
David Steurer,
Avi Wigderson:
Towards a Study of Low-Complexity Graphs.
ICALP (1) 2009: 119-131 |
| 235 | | Avi Wigderson:
The work of Leslie Valiant.
STOC 2009: 1-2 |
| 234 | | Russell Impagliazzo,
Valentine Kabanets,
Avi Wigderson:
New direct-product testers and 2-query PCPs.
STOC 2009: 131-140 |
| 233 | | Zeev Dvir,
Ariel Gabizon,
Avi Wigderson:
Extractors And Rank Extractors For Polynomial Sources.
Computational Complexity 18(1): 1-58 (2009) |
| 2008 |
|---|
| 232 | | Venkatesan Guruswami,
James R. Lee,
Avi Wigderson:
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.
APPROX-RANDOM 2008: 444-454 |
| 231 | | Avi Wigderson:
Randomness - A Computational Complexity Perspective.
CSR 2008: 1-2 |
| 230 | | Guy Kindler,
Ryan O'Donnell,
Anup Rao,
Avi Wigderson:
Spherical Cubes and Rounding in High Dimensions.
FOCS 2008: 189-198 |
| 229 | | Zeev Dvir,
Avi Wigderson:
Kakeya Sets, New Mergers and Old Extractors.
FOCS 2008: 625-633 |
| 228 | | Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets,
Avi Wigderson:
Uniform direct product theorems: simplified, optimized, and derandomized.
STOC 2008: 579-588 |
| 227 | | Scott Aaronson,
Avi Wigderson:
Algebrization: a new barrier in complexity theory.
STOC 2008: 731-740 |
| 226 | | Gil Kalai,
Avi Wigderson:
Neighborly Embedded Manifolds.
Discrete & Computational Geometry 40(3): 319-324 (2008) |
| 225 | | Scott Aaronson,
Avi Wigderson:
Algebrization: A New Barrier in Complexity Theory.
Electronic Colloquium on Computational Complexity (ECCC) 15(005): (2008) |
| 224 | | Zeev Dvir,
Avi Wigderson:
Kakeya sets, new mergers and old extractors.
Electronic Colloquium on Computational Complexity (ECCC) 15(058): (2008) |
| 223 | | Russell Impagliazzo,
Ragesh Jaiswal,
Valentine Kabanets,
Avi Wigderson:
Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized.
Electronic Colloquium on Computational Complexity (ECCC) 15(079): (2008) |
| 222 | | Emanuele Viola,
Avi Wigderson:
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols.
Theory of Computing 4(1): 137-168 (2008) |
| 221 | | Avi Wigderson,
David Xiao:
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications.
Theory of Computing 4(1): 53-76 (2008) |
| 2007 |
|---|
| 220 | | Emanuele Viola,
Avi Wigderson:
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications.
FOCS 2007: 427-437 |
| 219 | | Zeev Dvir,
Ariel Gabizon,
Avi Wigderson:
Extractors and Rank Extractors for Polynomial Sources.
FOCS 2007: 52-62 |
| 218 | | Emanuele Viola,
Avi Wigderson:
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols.
IEEE Conference on Computational Complexity 2007: 141-154 |
| 217 | | Zeev Dvir,
Ariel Gabizon,
Avi Wigderson:
Extractors and Rank Extractors for Polynomial Sources.
Electronic Colloquium on Computational Complexity (ECCC) 14(056): (2007) |
| 216 | | Emanuele Viola,
Avi Wigderson:
One-way multi-party communication lower bound for pointer jumping with applications.
Electronic Colloquium on Computational Complexity (ECCC) 14(079): (2007) |
| 215 | | Johan Håstad,
Avi Wigderson:
The Randomized Communication Complexity of Set Disjointness.
Theory of Computing 3(1): 211-219 (2007) |
| 2006 |
|---|
| 214 | | Irit Dinur,
Madhu Sudan,
Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes.
APPROX-RANDOM 2006: 304-315 |
| 213 | | Avi Wigderson:
Applications of the Sum-Product Theorem in Finite Fields.
IEEE Conference on Computational Complexity 2006: 111 |
| 212 | | Avi Wigderson:
The Power and Weakness of Randomness in Computation.
LATIN 2006: 28-29 |
| 211 | | Boaz Barak,
Anup Rao,
Ronen Shaltiel,
Avi Wigderson:
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.
STOC 2006: 671-680 |
| 210 | | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Reducing The Seed Length In The Nisan-Wigderson Generator.
Combinatorica 26(6): 647-681 (2006) |
| 209 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Computational Complexity 15(4): 391-432 (2006) |
| 208 | | Avi Wigderson,
David Xiao:
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.
Electronic Colloquium on Computational Complexity (ECCC) 13(105): (2006) |
| 207 | | Irit Dinur,
Madhu Sudan,
Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes.
Electronic Colloquium on Computational Complexity (ECCC) 13(118): (2006) |
| 206 | | Omer Reingold,
Ronen Shaltiel,
Avi Wigderson:
Extracting Randomness via Repeated Condensing.
SIAM J. Comput. 35(5): 1185-1209 (2006) |
| 205 | | Boaz Barak,
Russell Impagliazzo,
Avi Wigderson:
Extracting Randomness Using Few Independent Sources.
SIAM J. Comput. 36(4): 1095-1118 (2006) |
| 204 | | Amir Shpilka,
Avi Wigderson:
Derandomizing Homomorphism Testing in General Groups.
SIAM J. Comput. 36(4): 1215-1230 (2006) |
| 203 | | Eyal Rozenman,
Aner Shalev,
Avi Wigderson:
Iterative Construction of Cayley Expander Graphs.
Theory of Computing 2(1): 91-120 (2006) |
| 2005 |
|---|
| 202 | | Avi Wigderson,
David Xiao:
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications.
FOCS 2005: 397-406 |
| 201 | | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
IEEE Conference on Computational Complexity 2005: 52-66 |
| 200 | | Boaz Barak,
Guy Kindler,
Ronen Shaltiel,
Benny Sudakov,
Avi Wigderson:
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.
STOC 2005: 1-10 |
| 199 | | Avi Wigderson,
David Xiao:
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications
Electronic Colloquium on Computational Complexity (ECCC)(107): (2005) |
| 198 | | Michael Luby,
Avi Wigderson:
Pairwise Independence and Derandomization.
Foundations and Trends in Theoretical Computer Science 1(4): (2005) |
| 2004 |
|---|
| 197 | | Boaz Barak,
Russell Impagliazzo,
Avi Wigderson:
Extracting Randomness Using Few Independent Sources.
FOCS 2004: 384-393 |
| 196 | | Amir Shpilka,
Avi Wigderson:
Derandomizing homomorphism testing in general groups.
STOC 2004: 427-435 |
| 195 | | Eyal Rozenman,
Aner Shalev,
Avi Wigderson:
A new family of Cayley expanders (?).
STOC 2004: 445-454 |
| 194 | | Avi Wigderson:
Depth through breadth, or why should we attend talks in other areas?
STOC 2004: 579 |
| 193 | | Eli Ben-Sasson,
Russell Impagliazzo,
Avi Wigderson:
Near Optimal Separation Of Tree-Like And General Resolution.
Combinatorica 24(4): 585-603 (2004) |
| 192 | | Roy Meshulam,
Avi Wigderson:
Expanders In Group Algebras.
Combinatorica 24(4): 659-680 (2004) |
| 191 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity.
SIAM J. Comput. 34(1): 67-88 (2004) |
| 2003 |
|---|
| 190 | | Avi Wigderson:
Zigzag Products, Expander Constructions, Connections, and Applications.
FSTTCS 2003: 443 |
| 189 | | Boaz Barak,
Ronen Shaltiel,
Avi Wigderson:
Computational Analogues of Entropy.
RANDOM-APPROX 2003: 200-215 |
| 188 | | Chi-Jen Lu,
Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Extractors: optimal up to constant factors.
STOC 2003: 602-611 |
| 187 | | Eli Ben-Sasson,
Madhu Sudan,
Salil P. Vadhan,
Avi Wigderson:
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
STOC 2003: 612-621 |
| 186 | | Johan Håstad,
Avi Wigderson:
Simple analysis of graph tests for linearity and PCP.
Random Struct. Algorithms 22(2): 139-160 (2003) |
| 185 | | Andris Ambainis,
Leonard J. Schulman,
Amnon Ta-Shma,
Umesh V. Vazirani,
Avi Wigderson:
The Quantum Communication Complexity of Sampling.
SIAM J. Comput. 32(6): 1570-1585 (2003) |
| 2002 |
|---|
| 184 | | Michael R. Capalbo,
Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Randomness Conductors and Constant-Degree Lossless Expanders.
IEEE Conference on Computational Complexity 2002: 15 |
| 183 | | Roy Meshulam,
Avi Wigderson:
Expanders from Symmetric Codes.
IEEE Conference on Computational Complexity 2002: 16 |
| 182 | | Ehud Friedgut,
Jeff Kahn,
Avi Wigderson:
Computing Graph Properties by Randomized Subcube Partitions.
RANDOM 2002: 105-113 |
| 181 | | Oded Goldreich,
Avi Wigderson:
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good.
RANDOM 2002: 209-223 |
| 180 | | Michael R. Capalbo,
Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Randomness conductors and constant-degree lossless expanders.
STOC 2002: 659-668 |
| 179 | | Roy Meshulam,
Avi Wigderson:
Expanders from symmetric codes.
STOC 2002: 669-677 |
| 178 | | Alexander A. Razborov,
Avi Wigderson,
Andrew Chi-Chih Yao:
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Combinatorica 22(4): 555-574 (2002) |
| 177 | | Oded Goldreich,
Salil P. Vadhan,
Avi Wigderson:
On interactive proofs with a laconic prover.
Computational Complexity 11(1-2): 1-53 (2002) |
| 176 | | Oded Goldreich,
Avi Wigderson:
Derandomization that is rarely wrong from short advice that is typically good
Electronic Colloquium on Computational Complexity (ECCC)(039): (2002) |
| 175 | | Russell Impagliazzo,
Valentine Kabanets,
Avi Wigderson:
In search of an easy witness: exponential time vs. probabilistic polynomial time.
J. Comput. Syst. Sci. 65(4): 672-694 (2002) |
| 174 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Space Complexity in Propositional Calculus.
SIAM J. Comput. 31(4): 1184-1211 (2002) |
| 2001 |
|---|
| 173 |  | Noga Alon,
Alexander Lubotzky,
Avi Wigderson:
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications.
FOCS 2001: 630-637 |
| 172 | | Oded Goldreich,
Salil P. Vadhan,
Avi Wigderson:
On Interactive Proofs with a Laconic Prover.
ICALP 2001: 334-345 |
| 171 | | Russell Impagliazzo,
Valentine Kabanets,
Avi Wigderson:
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.
IEEE Conference on Computational Complexity 2001: 2-12 |
| 170 | | Johan Håstad,
Avi Wigderson:
Simple Analysis of Graph Tests for Linearity and PCP.
IEEE Conference on Computational Complexity 2001: 244-254 |
| 169 | | Amir Shpilka,
Avi Wigderson:
Depth-3 arithmetic circuits over fields of characteristic zero.
Computational Complexity 10(1): 1-27 (2001) |
| 168 | | Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Electronic Colloquium on Computational Complexity (ECCC) 8(18): (2001) |
| 167 | | Oded Goldreich,
Salil P. Vadhan,
Avi Wigderson:
On Interactive Proofs with a Laconic Prover
Electronic Colloquium on Computational Complexity (ECCC) 8(46): (2001) |
| 166 | | Eli Ben-Sasson,
Avi Wigderson:
Short proofs are narrow - resolution made simple.
J. ACM 48(2): 149-169 (2001) |
| 165 | | Russell Impagliazzo,
Avi Wigderson:
Randomness vs Time: Derandomization under a Uniform Assumption.
J. Comput. Syst. Sci. 63(4): 672-688 (2001) |
| 2000 |
|---|
| 164 | | Omer Reingold,
Ronen Shaltiel,
Avi Wigderson:
Extracting Randomness via Repeated Condensing.
FOCS 2000: 22-31 |
| 163 | | Omer Reingold,
Salil P. Vadhan,
Avi Wigderson:
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
FOCS 2000: 3-13 |
| 162 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity.
FOCS 2000: 43-53 |
| 161 | | Oded Goldreich,
Avi Wigderson:
On Pseudorandomness with respect to Deterministic Observes.
ICALP Satellite Workshops 2000: 77-84 |
| 160 | | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Extractors and pseudo-random generators with optimal seed length.
STOC 2000: 1-10 |
| 159 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Space complexity in propositional calculus.
STOC 2000: 358-367 |
| 158 | | Nathan Linial,
Alex Samorodnitsky,
Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
Combinatorica 20(4): 545-568 (2000) |
| 157 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity
Electronic Colloquium on Computational Complexity (ECCC) 7(23): (2000) |
| 156 | | Oded Goldreich,
Salil P. Vadhan,
Avi Wigderson:
Simplified derandomization of BPP using a hitting set generator.
Electronic Colloquium on Computational Complexity (ECCC) 7(4): (2000) |
| 155 | | Eli Ben-Sasson,
Russell Impagliazzo,
Avi Wigderson:
Near-Optimal Separation of Treelike and General Resolution
Electronic Colloquium on Computational Complexity (ECCC) 7(5): (2000) |
| 154 | | Oded Goldreich,
Avi Wigderson:
On Pseudorandomness with respect to Deterministic Observers.
Electronic Colloquium on Computational Complexity (ECCC) 7(56): (2000) |
| 153 | | Omer Reingold,
Ronen Shaltiel,
Avi Wigderson:
Extracting Randomness via Repeated Condensing
Electronic Colloquium on Computational Complexity (ECCC) 7(59): (2000) |
| 152 | | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Extractors and pseudo-random generators with optimal seed length
Electronic Colloquium on Computational Complexity (ECCC) 7(9): (2000) |
| 151 | | Roy Armoni,
Amnon Ta-Shma,
Avi Wigderson,
Shiyu Zhou:
An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs.
J. ACM 47(2): 294-311 (2000) |
| 1999 |
|---|
| 150 | | Russell Impagliazzo,
Ronen Shaltiel,
Avi Wigderson:
Near-Optimal Conversion of Hardness into Pseudo-Randomness.
FOCS 1999: 181-190 |
| 149 | | Ziv Bar-Yossef,
Oded Goldreich,
Avi Wigderson:
Deterministic Amplification of Space-Bounded Probabilistic Algorithms.
IEEE Conference on Computational Complexity 1999: 188- |
| 148 | | Eli Ben-Sasson,
Avi Wigderson:
Short Proofs Are Narrow - Resolution Made Simple (Abstract).
IEEE Conference on Computational Complexity 1999: 2 |
| 147 | | Avi Wigderson:
De-Randomizing BPP: The State of the Art.
IEEE Conference on Computational Complexity 1999: 76- |
| 146 | | Amir Shpilka,
Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.
IEEE Conference on Computational Complexity 1999: 87- |
| 145 | | Avi Wigderson:
Probabilistic and Deterministic Approximations of the Permanent (abstract).
RANDOM-APPROX 1999: 130 |
| 144 | | Oded Goldreich,
Avi Wigderson:
Improved Derandomization of BPP Using a Hitting Set Generator.
RANDOM-APPROX 1999: 131-137 |
| 143 | | Eli Ben-Sasson,
Avi Wigderson:
Short Proofs are Narrow - Resolution Made Simple.
STOC 1999: 517-526 |
| 142 | | Avi Wigderson,
David Zuckerman:
Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications.
Combinatorica 19(1): 125-138 (1999) |
| 141 | | László Babai,
Anna Gál,
Avi Wigderson:
Superpolynomial Lower Bounds for Monotone Span Programs.
Combinatorica 19(3): 301-319 (1999) |
| 140 | | Eli Ben-Sasson,
Avi Wigderson:
Short Proofs are Narrow - Resolution made Simple
Electronic Colloquium on Computational Complexity (ECCC) 6(22): (1999) |
| 139 | | Amir Shpilka,
Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Electronic Colloquium on Computational Complexity (ECCC) 6(23): (1999) |
| 138 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Space Complexity in Propositional Calculus
Electronic Colloquium on Computational Complexity (ECCC)(40): (1999) |
| 137 | | Yuri Rabinovich,
Avi Wigderson:
Techniques for bounding the convergence rate of genetic algorithms.
Random Struct. Algorithms 14(2): 111-138 (1999) |
| 1998 |
|---|
| 136 | | Andris Ambainis,
Leonard J. Schulman,
Amnon Ta-Shma,
Umesh V. Vazirani,
Avi Wigderson:
The Quantum Communication Complexity of Sampling.
FOCS 1998: 342-351 |
| 135 | | Russell Impagliazzo,
Avi Wigderson:
Randomness vs. Time: De-Randomization under a Uniform Assumption.
FOCS 1998: 734-743 |
| 134 | | Avi Wigderson:
Do Probabilistic Algorithms Outperform Deterministic Ones?
ICALP 1998: 212-214 |
| 133 | | Harry Buhrman,
Richard Cleve,
Avi Wigderson:
Quantum vs. Classical Communication and Computation.
STOC 1998: 63-68 |
| 132 | | Nathan Linial,
Alex Samorodnitsky,
Avi Wigderson:
A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
STOC 1998: 644-652 |
| 131 | | Ziv Bar-Yossef,
Oded Goldreich,
Avi Wigderson:
Deterministic Amplification of Space Bounded Probabilistic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC) 5(72): (1998) |
| 130 | | Peter Bro Miltersen,
Noam Nisan,
Shmuel Safra,
Avi Wigderson:
On Data Structures and Asymmetric Communication Complexity.
J. Comput. Syst. Sci. 57(1): 37-49 (1998) |
| 129 | | Anne Condon,
Lisa Hellerstein,
Samuel Pottle,
Avi Wigderson:
On the Power of Finite Automata with Both Nondeterministic and Probabilistic States.
SIAM J. Comput. 27(3): 739-762 (1998) |
| 1997 |
|---|
| 128 | | Russell Impagliazzo,
Avi Wigderson:
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.
STOC 1997: 220-229 |
| 127 | | Roy Armoni,
Amnon Ta-Shma,
Avi Wigderson,
Shiyu Zhou:
SL <= L4/3.
STOC 1997: 230-239 |
| 126 | | Itzhak Parnafes,
Ran Raz,
Avi Wigderson:
Direct Product Results and the GCD Problem, in Old and New Communication Models.
STOC 1997: 363-372 |
| 125 | | Alexander A. Razborov,
Avi Wigderson,
Andrew Chi-Chih Yao:
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
STOC 1997: 739-748 |
| 124 | | Noam Nisan,
Avi Wigderson:
Lower Bounds on Arithmetic Circuits Via Partial Derivatives.
Computational Complexity 6(3): 217-234 (1997) |
| 123 | | Oded Goldreich,
Avi Wigderson:
Tiny families of functions with random properties: A quality-size trade-off for hashing.
Random Struct. Algorithms 11(4): 315-343 (1997) |
| 1996 |
|---|
| 122 | | Roy Armoni,
Michael E. Saks,
Avi Wigderson,
Shiyu Zhou:
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles.
FOCS 1996: 412-421 |
| 121 | | Roded Sharan,
Avi Wigderson:
A New NCAlgorithm for Perfect Matching in Bipartite Cubic Graphs.
ISTCS 1996: 202-207 |
| 120 | | László Babai,
Anna Gál,
János Kollár,
Lajos Rónyai,
Tibor Szabó,
Avi Wigderson:
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.
STOC 1996: 603-611 |
| 119 | | Oded Goldreich,
Avi Wigderson:
Theory of Computing: A Scientific Perspective.
ACM Comput. Surv. 28(4es): 218 (1996) |
| 118 | | Helmut Alt,
Leonidas J. Guibas,
Kurt Mehlhorn,
Richard M. Karp,
Avi Wigderson:
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.
Algorithmica 16(4/5): 543-547 (1996) |
| 117 | | Oded Goldreich,
Avi Wigderson:
On the Circuit Complexity of Perfect Hashing
Electronic Colloquium on Computational Complexity (ECCC) 3(41): (1996) |
| 116 | | Anna Gál,
Avi Wigderson:
Boolean complexity classes vs. their arithmetic analogs.
Random Struct. Algorithms 9(1-2): 99-111 (1996) |
| 115 | | Joseph Gil,
Friedhelm Meyer auf der Heide,
Avi Wigderson:
The Tree Model for Hashing: Lower and Upper Bounds.
SIAM J. Comput. 25(5): 936-955 (1996) |
| 1995 |
|---|
| 114 | | Ivan Damgård,
Oded Goldreich,
Tatsuaki Okamoto,
Avi Wigderson:
Honest Verifier vs Dishonest Verifier in Public Cain Zero-Knowledge Proofs.
CRYPTO 1995: 325-338 |
| 113 | | Noam Nisan,
Avi Wigderson:
Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version).
FOCS 1995: 16-25 |
| 112 | | Avi Wigderson:
Computational Pseudo-Randomness.
ISTCS 1995: 218-219 |
| 111 | | Peter Bro Miltersen,
Noam Nisan,
Shmuel Safra,
Avi Wigderson:
On data structures and asymmetric communication complexity.
STOC 1995: 103-111 |
| 110 | | Noam Nisan,
Avi Wigderson:
On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern.
STOC 1995: 723-732 |
| 109 | | Joel Friedman,
Avi Wigderson:
On the Second Eigenvalue of Hypergraphs.
Combinatorica 15(1): 43-65 (1995) |
| 108 | | Noam Nisan,
Avi Wigderson:
On Rank vs. Communication Complexity.
Combinatorica 15(4): 557-565 (1995) |
| 107 | | Noga Alon,
Uriel Feige,
Avi Wigderson,
David Zuckerman:
Derandomized Graph Products.
Computational Complexity 5(1): 60-75 (1995) |
| 106 | | Mauricio Karchmer,
Ran Raz,
Avi Wigderson:
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity.
Computational Complexity 5(3/4): 191-204 (1995) |
| 105 | | Anna Gál,
Avi Wigderson:
Boolean Complexity Classes vs. Their Arithmetic Analogs
Electronic Colloquium on Computational Complexity (ECCC) 2(49): (1995) |
| 104 | | Oded Goldreich,
Noam Nisan,
Avi Wigderson:
On Yao's XOR-Lemma
Electronic Colloquium on Computational Complexity (ECCC) 2(50): (1995) |
| 103 | | László Lovász,
Moni Naor,
Ilan Newman,
Avi Wigderson:
Search Problems in the Decision Tree Model.
SIAM J. Discrete Math. 8(1): 119-132 (1995) |
| 102 | | Ilan Newman,
Avi Wigderson:
Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy.
SIAM J. Discrete Math. 8(4): 536-542 (1995) |
| 1994 |
|---|
| 101 | | Noam Nisan,
Avi Wigderson:
On Rank vs. Communication Complexity
FOCS 1994: 831-836 |
| 100 | | Avi Wigderson:
The Wonders of the Digital Envelope - A Crash Course in Modern Cryptography.
IFIP Congress (1) 1994: 235-238 |
| 99 | | Russell Impagliazzo,
Noam Nisan,
Avi Wigderson:
Pseudorandomness for network algorithms.
STOC 1994: 356-364 |
| 98 | | Oded Goldreich,
Avi Wigderson:
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing.
STOC 1994: 574-584 |
| 97 | | Avi Wigderson:
The amazing power of pairwise independence (abstract).
STOC 1994: 645-647 |
| 96 | | Anne Condon,
Lisa Hellerstein,
Samuel Pottle,
Avi Wigderson:
On the power of finite automata with both nondeterministic and probabilistic states (preliminary version).
STOC 1994: 676-685 |
| 95 | | Avi Wigderson:
NL/poly <= +/poly (Preliminary Version).
Structure in Complexity Theory Conference 1994: 59-62 |
| 94 | | Russell Impagliazzo,
Ran Raz,
Avi Wigderson:
A Direct Product Theorem.
Structure in Complexity Theory Conference 1994: 88-96 |
| 93 | | Shai Ben-David,
Allan Borodin,
Richard M. Karp,
Gábor Tardos,
Avi Wigderson:
On the Power of Randomization in On-Line Algorithms.
Algorithmica 11(1): 2-14 (1994) |
| 92 | | Noam Nisan,
Avi Wigderson:
On Rank vs. Communication Complexity
Electronic Colloquium on Computational Complexity (ECCC) 1(1): (1994) |
| 91 | | Oded Goldreich,
Avi Wigderson:
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing
Electronic Colloquium on Computational Complexity (ECCC) 1(2): (1994) |
| 90 | | Noam Nisan,
Avi Wigderson:
Hardness vs Randomness.
J. Comput. Syst. Sci. 49(2): 149-167 (1994) |
| 89 | | Mauricio Karchmer,
Ilan Newman,
Michael E. Saks,
Avi Wigderson:
Non-Deterministic Communication Complexity with Few Witnesses.
J. Comput. Syst. Sci. 49(2): 247-257 (1994) |
| 1993 |
|---|
| 88 | | Michael Luby,
Boban Velickovic,
Avi Wigderson:
Deterministic Approximate Counting of Depth-2 Circuits.
ISTCS 1993: 18-24 |
| 87 | | Rafail Ostrovsky,
Avi Wigderson:
One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge.
ISTCS 1993: 3-17 |
| 86 | | Avi Wigderson,
David Zuckerman:
Expanders that beat the eigenvalue bound: explicit construction and applications.
STOC 1993: 245-251 |
| 85 | | Mauricio Karchmer,
Avi Wigderson:
Characterizing non-deterministic circuit size.
STOC 1993: 532-540 |
| 84 | | Mauricio Karchmer,
Avi Wigderson:
On Span Programs.
Structure in Complexity Theory Conference 1993: 102-111 |
| 83 | | Alexander A. Razborov,
Endre Szemerédi,
Avi Wigderson:
Constructing Small Sets that are Uniform in Arithmetic Progressions.
Combinatorics, Probability & Computing 2: 513-518 (1993) |
| 82 | | László Babai,
Lance Fortnow,
Noam Nisan,
Avi Wigderson:
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
Computational Complexity 3: 307-318 (1993) |
| 81 | | Mauricio Karchmer,
Nathan Linial,
Ilan Newman,
Michael E. Saks,
Avi Wigderson:
Combinatorial characterization of read-once formulae.
Discrete Mathematics 114(1-3): 275-282 (1993) |
| 80 | | Alexander A. Razborov,
Avi Wigderson:
n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom.
Inf. Process. Lett. 45(6): 303-307 (1993) |
| 79 | | Shlomo Hoory,
Avi Wigderson:
Universal Traversal Sequences for Expander Graphs.
Inf. Process. Lett. 46(2): 67-69 (1993) |
| 78 | | Noam Nisan,
Avi Wigderson:
Rounds in Communication Complexity Revisited.
SIAM J. Comput. 22(1): 211-219 (1993) |
| 77 | | Rafi Heiman,
Ilan Newman,
Avi Wigderson:
On Read-Once Threshold Formulae and Their Randomized Decision in Tree Complexity.
Theor. Comput. Sci. 107(1): 63-76 (1993) |
| 1992 |
|---|
| 76 | | Noam Nisan,
Endre Szemerédi,
Avi Wigderson:
Undirected Connectivity in O(log ^1.5 n) Space
FOCS 1992: 24-29 |
| 75 | | Yuri Rabinovich,
Alistair Sinclair,
Avi Wigderson:
Quadratic Dynamical Systems (Preliminary Version)
FOCS 1992: 304-313 |
| 74 | | Avi Wigderson:
The Complexity of Graph Connectivity.
MFCS 1992: 112-132 |
| 73 | | Mauricio Karchmer,
Ilan Newman,
Michael E. Saks,
Avi Wigderson:
Non-deterministic Communication Complexity with Few Witness.
Structure in Complexity Theory Conference 1992: 275-281 |
| 72 | | Joseph Gil,
William L. Steiger,
Avi Wigderson:
Geometric medians.
Discrete Mathematics 108(1-3): 37-51 (1992) |
| 71 | | Ran Raz,
Avi Wigderson:
Monotone Circuits for Matching Require Linear Depth.
J. ACM 39(3): 736-744 (1992) |
| 1991 |
|---|
| 70 | | László Lovász,
Moni Naor,
Ilan Newman,
Avi Wigderson:
Search Problems in the Decision Tree Model (Preliminary Version)
FOCS 1991: 576-585 |
| 69 | | Yuri Rabinovich,
Avi Wigderson:
An Analysis of a Simple Genetic Algorithm.
ICGA 1991: 215-221 |
| 68 | | Peter Gemmell,
Richard J. Lipton,
Ronitt Rubinfeld,
Madhu Sudan,
Avi Wigderson:
Self-Testing/Correcting for Polynomials and for Approximate Functions
STOC 1991: 32-42 |
| 67 | | Noam Nisan,
Avi Wigderson:
Rounds in Communication Complexity Revisited
STOC 1991: 419-429 |
| 66 | | Rafi Heiman,
Avi Wigderson:
Randomized vs.Deterministic Decision Tree Complexity for Read-Once Boolean Functions.
Structure in Complexity Theory Conference 1991: 172-179 |
| 65 | | Mauricio Karchmer,
Ran Raz,
Avi Wigderson:
Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity.
Structure in Complexity Theory Conference 1991: 299-304 |
| 64 | | Alok Aggarwal,
Maria M. Klawe,
David Lichtenstein,
Nathan Linial,
Avi Wigderson:
A Lower Bound on the Area of Permutation Layouts.
Algorithmica 6(2): 241-255 (1991) |
| 63 | | Rafi Heiman,
Avi Wigderson:
Randomized VS. Deterministic Decision Tree Complexity for Read-Once Boolean Functions.
Computational Complexity 1: 311-329 (1991) |
| 62 | | Prabhakar Ragde,
Avi Wigderson:
Linear-Size Constant-Depth Polylog-Treshold Circuits.
Inf. Process. Lett. 39(3): 143-146 (1991) |
| 61 | | Oded Goldreich,
Silvio Micali,
Avi Wigderson:
Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.
J. ACM 38(3): 691-729 (1991) |
| 1990 |
|---|
| 60 | | Joseph Gil,
Friedhelm Meyer auf der Heide,
Avi Wigderson:
Not All Keys Can Be Hashed in Constant Time (Preliminary Version)
STOC 1990: 244-253 |
| 59 | | Ran Raz,
Avi Wigderson:
Monotone Circuits for Matching Require Linear Depth
STOC 1990: 287-292 |
| 58 | | Shai Ben-David,
Allan Borodin,
Richard M. Karp,
Gábor Tardos,
Avi Wigderson:
On the Power of Randomization in Online Algorithms (Extended Abstract)
STOC 1990: 379-386 |
| 57 | | Rafi Heiman,
Ilan Newman,
Avi Wigderson:
On Read-Once Threshold Formulae and Their Randomized Decision Tree Complexity.
Structure in Complexity Theory Conference 1990: 78-87 |
| 56 | | Ilan Newman,
Prabhakar Ragde,
Avi Wigderson:
Perfect Hashing, Graph Entropy, and Circuit Complexity.
Structure in Complexity Theory Conference 1990: 91-99 |
| 55 | | Faith E. Fich,
Avi Wigderson:
Toward Understanding Exclusive Read.
SIAM J. Comput. 19(4): 718-727 (1990) |
| 54 | | Noga Alon,
Mauricio Karchmer,
Avi Wigderson:
Linear Circuits over GF(2).
SIAM J. Comput. 19(6): 1064-1067 (1990) |
| 53 | | Mauricio Karchmer,
Avi Wigderson:
Monotone Circuits for Connectivity Require Super-Logarithmic Depth.
SIAM J. Discrete Math. 3(2): 255-265 (1990) |
| 1989 |
|---|
| 52 | | Michael Ben-Or,
Shafi Goldwasser,
Joe Kilian,
Avi Wigderson:
Efficient Identification Schemes Using Two Prover Interactive Proofs.
CRYPTO 1989: 498-506 |
| 51 | | Aviad Cohen,
Avi Wigderson:
Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)
FOCS 1989: 14-19 |
| 50 | | Ran Raz,
Avi Wigderson:
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)
FOCS 1989: 562-567 |
| 49 | | Faith E. Fich,
Avi Wigderson:
Towards Understanding Exclusive Read.
SPAA 1989: 76-82 |
| 48 | | Bettina Just,
Friedhelm Meyer auf der Heide,
Avi Wigderson:
On Computations with Integer Division.
ITA 23(1): 101-111 (1989) |
| 1988 |
|---|
| 47 | | Noam Nisan,
Avi Wigderson:
Hardness vs. Randomness (Extended Abstract)
FOCS 1988: 2-11 |
| 46 | | Bettina Just,
Friedhelm Meyer auf der Heide,
Avi Wigderson:
On Computations with Integer Division.
STACS 1988: 29-37 |
| 45 | | Michael Ben-Or,
Shafi Goldwasser,
Avi Wigderson:
Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)
STOC 1988: 1-10 |
| 44 | | Michael Ben-Or,
Shafi Goldwasser,
Joe Kilian,
Avi Wigderson:
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
STOC 1988: 113-131 |
| 43 | | Mauricio Karchmer,
Avi Wigderson:
Monotone Circuits for Connectivity Require Super-logarithmic Depth
STOC 1988: 539-550 |
| 42 | | Faith E. Fich,
Prabhakar Ragde,
Avi Wigderson:
Simulations Among Concurrent-Write PRAMs.
Algorithmica 3: 43-51 (1988) |
| 41 | | Nathan Linial,
László Lovász,
Avi Wigderson:
Rubber bands, convex embeddings and graph connectivity.
Combinatorica 8(1): 91-102 (1988) |
| 40 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
The Complexity of Parallel Search.
J. Comput. Syst. Sci. 36(2): 225-253 (1988) |
| 39 | | Douglas L. Long,
Avi Wigderson:
The Discrete Logarithm Hides O(log n) Bits.
SIAM J. Comput. 17(2): 363-372 (1988) |
| 38 | | Faith E. Fich,
Prabhakar Ragde,
Avi Wigderson:
Relations Between Concurrent-Write Models of Parallel Computation.
SIAM J. Comput. 17(3): 606-627 (1988) |
| 37 | | Prabhakar Ragde,
William L. Steiger,
Endre Szemerédi,
Avi Wigderson:
The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)).
SIAM J. Discrete Math. 1(3): 399-410 (1988) |
| 36 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Theor. Comput. Sci. 58: 57-68 (1988) |
| 1987 |
|---|
| 35 | | Oded Goldreich,
Silvio Micali,
Avi Wigderson:
How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority
STOC 1987: 218-229 |
| 34 | | Eli Upfal,
Avi Wigderson:
How to share memory in a distributed system.
J. ACM 34(1): 116-127 (1987) |
| 33 | | Friedhelm Meyer auf der Heide,
Avi Wigderson:
The Complexity of Parallel Sorting.
SIAM J. Comput. 16(1): 100-107 (1987) |
| 32 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput. 16(1): 97-99 (1987) |
| 1986 |
|---|
| 31 | | Oded Goldreich,
Silvio Micali,
Avi Wigderson:
How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design.
CRYPTO 1986: 171-185 |
| 30 | | Oded Goldreich,
Silvio Micali,
Avi Wigderson:
Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)
FOCS 1986: 174-187 |
| 29 | | Richard M. Karp,
Michael E. Saks,
Avi Wigderson:
On a Search Problem Related to Branch-and-Bound Procedures
FOCS 1986: 19-28 |
| 28 | | Michael E. Saks,
Avi Wigderson:
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
FOCS 1986: 29-38 |
| 27 | | Nathan Linial,
László Lovász,
Avi Wigderson:
A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications
FOCS 1986: 39-48 |
| 26 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
ICALP 1986: 50-59 |
| 25 | | Oded Goldreich,
Silvio Micali,
Avi Wigderson:
Proofs that Release Minimum Knowledge.
MFCS 1986: 639-650 |
| 24 | | Allan Borodin,
Faith E. Fich,
Friedhelm Meyer auf der Heide,
Eli Upfal,
Avi Wigderson:
A Time-Space Tradeoff for Element Distinctness.
STACS 1986: 353-358 |
| 23 | | Nimrod Megiddo,
Avi Wigderson:
On Play by Means of Computing Machines.
TARK 1986: 259-274 |
| 22 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
Constructing a perfect matching is in random NC.
Combinatorica 6(1): 35-48 (1986) |
| 1985 |
|---|
| 21 | | Miklós Ajtai,
Avi Wigderson:
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)
FOCS 1985: 11-19 |
| 20 | | Alok Aggarwal,
Maria M. Klawe,
David Lichtenstein,
Nathan Linial,
Avi Wigderson:
Multi-Layer Grid Embeddings
FOCS 1985: 186-196 |
| 19 | | Friedhelm Meyer auf der Heide,
Avi Wigderson:
The Complexity of Parallel Sorting
FOCS 1985: 532-540 |
| 18 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
The Complexity of Parallel Computation on Matroids
FOCS 1985: 541-550 |
| 17 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
Constructing a Perfect Matching is in Random NC
STOC 1985: 22-32 |
| 16 | | Richard M. Karp,
Eli Upfal,
Avi Wigderson:
Are Search and Decision Problems Computationally Equivalent?
STOC 1985: 464-475 |
| 15 | | Faith E. Fich,
Friedhelm Meyer auf der Heide,
Prabhakar Ragde,
Avi Wigderson:
One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation
STOC 1985: 48-58 |
| 14 | | Richard M. Karp,
Avi Wigderson:
A Fast Parallel Algorithm for the Maximal Independent Set Problem
J. ACM 32(4): 762-773 (1985) |
| 13 | | Uzi Vishkin,
Avi Wigderson:
Trade-Offs Between Depth and Width in Parallel Computation.
SIAM J. Comput. 14(2): 303-314 (1985) |
| 12 | | Gopalakrishnan Vijayan,
Avi Wigderson:
Rectilinear Graphs and their Embeddings.
SIAM J. Comput. 14(2): 355-372 (1985) |
| 1984 |
|---|
| 11 | | Eli Upfal,
Avi Wigderson:
How to Share Memory in a Distributed System (A Preliminary Version)
FOCS 1984: 171-180 |
| 10 | | Faith E. Fich,
Prabhakar Ragde,
Avi Wigderson:
Relations Between Concurrent-Write Models of Parallel Computation.
PODC 1984: 179-189 |
| 9 | | Richard M. Karp,
Avi Wigderson:
A Fast Parallel Algorithm for the Maximal Independent Set Problem
STOC 1984: 266-272 |
| 1983 |
|---|
| 8 | | Uzi Vishkin,
Avi Wigderson:
Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version)
FOCS 1983: 146-153 |
| 7 | | Douglas L. Long,
Avi Wigderson:
How Discreet is the Discrete Log?
STOC 1983: 413-420 |
| 6 | | Danny Dolev,
Cynthia Dwork,
Nicholas Pippenger,
Avi Wigderson:
Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
STOC 1983: 42-51 |
| 5 | | Uzi Vishkin,
Avi Wigderson:
Dynamic Parallel Memories
Information and Control 56(3): 174-182 (1983) |
| 4 | | Hana Galperin,
Avi Wigderson:
Succinct Representations of Graphs
Information and Control 56(3): 183-198 (1983) |
| 3 | | Avi Wigderson:
Improving the Performance Guarantee for Approximate Graph Coloring
J. ACM 30(4): 729-735 (1983) |
| 1982 |
|---|
| 2 | | Danny Dolev,
Avi Wigderson:
On the Security of Multi-Party Protocols in Distributed Systems.
CRYPTO 1982: 167-175 |
| 1 | | Avi Wigderson:
A New Approximate Graph Coloring Algorithm
STOC 1982: 325-329 |
