dblp.uni-trier.dewww.uni-trier.de

Avi Wigderson

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2008
232EEVenkatesan Guruswami, James R. Lee, Avi Wigderson: Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. APPROX-RANDOM 2008: 444-454
231EEAvi Wigderson: Randomness - A Computational Complexity Perspective. CSR 2008: 1-2
230EEGuy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson: Spherical Cubes and Rounding in High Dimensions. FOCS 2008: 189-198
229EEZeev Dvir, Avi Wigderson: Kakeya Sets, New Mergers and Old Extractors. FOCS 2008: 625-633
228EERussell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588
227EEScott Aaronson, Avi Wigderson: Algebrization: a new barrier in complexity theory. STOC 2008: 731-740
226EEGil Kalai, Avi Wigderson: Neighborly Embedded Manifolds. Discrete & Computational Geometry 40(3): 319-324 (2008)
225EEScott Aaronson, Avi Wigderson: Algebrization: A New Barrier in Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC) 15(005): (2008)
224EEZeev Dvir, Avi Wigderson: Kakeya sets, new mergers and old extractors. Electronic Colloquium on Computational Complexity (ECCC) 15(058): (2008)
223EERussell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electronic Colloquium on Computational Complexity (ECCC) 15(079): (2008)
222EEEmanuele Viola, Avi Wigderson: Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1): 137-168 (2008)
221EEAvi 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
220EEEmanuele Viola, Avi Wigderson: One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. FOCS 2007: 427-437
219EEZeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors and Rank Extractors for Polynomial Sources. FOCS 2007: 52-62
218EEEmanuele Viola, Avi Wigderson: Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. IEEE Conference on Computational Complexity 2007: 141-154
217EEZeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors and Rank Extractors for Polynomial Sources. Electronic Colloquium on Computational Complexity (ECCC) 14(056): (2007)
216EEEmanuele Viola, Avi Wigderson: One-way multi-party communication lower bound for pointer jumping with applications. Electronic Colloquium on Computational Complexity (ECCC) 14(079): (2007)
215EEJohan Håstad, Avi Wigderson: The Randomized Communication Complexity of Set Disjointness. Theory of Computing 3(1): 211-219 (2007)
2006
214EEIrit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM 2006: 304-315
213EEAvi Wigderson: Applications of the Sum-Product Theorem in Finite Fields. IEEE Conference on Computational Complexity 2006: 111
212EEAvi Wigderson: The Power and Weakness of Randomness in Computation. LATIN 2006: 28-29
211EEBoaz 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
210EERussell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Reducing The Seed Length In The Nisan-Wigderson Generator. Combinatorica 26(6): 647-681 (2006)
209EEPaul 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)
208EEAvi Wigderson, David Xiao: Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications. Electronic Colloquium on Computational Complexity (ECCC) 13(105): (2006)
207EEIrit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. Electronic Colloquium on Computational Complexity (ECCC) 13(118): (2006)
206EEOmer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing. SIAM J. Comput. 35(5): 1185-1209 (2006)
205EEBoaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006)
204EEAmir Shpilka, Avi Wigderson: Derandomizing Homomorphism Testing in General Groups. SIAM J. Comput. 36(4): 1215-1230 (2006)
203EEEyal Rozenman, Aner Shalev, Avi Wigderson: Iterative Construction of Cayley Expander Graphs. Theory of Computing 2(1): 91-120 (2006)
2005
202EEAvi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. FOCS 2005: 397-406
201EEPaul 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
200EEBoaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson: Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. STOC 2005: 1-10
199EEAvi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications Electronic Colloquium on Computational Complexity (ECCC)(107): (2005)
198EEMichael Luby, Avi Wigderson: Pairwise Independence and Derandomization. Foundations and Trends in Theoretical Computer Science 1(4): (2005)
2004
197EEBoaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393
196EEAmir Shpilka, Avi Wigderson: Derandomizing homomorphism testing in general groups. STOC 2004: 427-435
195EEEyal Rozenman, Aner Shalev, Avi Wigderson: A new family of Cayley expanders (?). STOC 2004: 445-454
194EEAvi Wigderson: Depth through breadth, or why should we attend talks in other areas? STOC 2004: 579
193EEEli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near Optimal Separation Of Tree-Like And General Resolution. Combinatorica 24(4): 585-603 (2004)
192EERoy Meshulam, Avi Wigderson: Expanders In Group Algebras. Combinatorica 24(4): 659-680 (2004)
191EEMichael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34(1): 67-88 (2004)
2003
190EEAvi Wigderson: Zigzag Products, Expander Constructions, Connections, and Applications. FSTTCS 2003: 443
189EEBoaz Barak, Ronen Shaltiel, Avi Wigderson: Computational Analogues of Entropy. RANDOM-APPROX 2003: 200-215
188EEChi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Extractors: optimal up to constant factors. STOC 2003: 602-611
187EEEli 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
186EEJohan Håstad, Avi Wigderson: Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22(2): 139-160 (2003)
185EEAndris 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
184EEMichael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness Conductors and Constant-Degree Lossless Expanders. IEEE Conference on Computational Complexity 2002: 15
183EERoy Meshulam, Avi Wigderson: Expanders from Symmetric Codes. IEEE Conference on Computational Complexity 2002: 16
182EEEhud Friedgut, Jeff Kahn, Avi Wigderson: Computing Graph Properties by Randomized Subcube Partitions. RANDOM 2002: 105-113
181EEOded Goldreich, Avi Wigderson: Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good. RANDOM 2002: 209-223
180EEMichael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness conductors and constant-degree lossless expanders. STOC 2002: 659-668
179EERoy Meshulam, Avi Wigderson: Expanders from symmetric codes. STOC 2002: 669-677
178EEAlexander 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)
177EEOded Goldreich, Salil P. Vadhan, Avi Wigderson: On interactive proofs with a laconic prover. Computational Complexity 11(1-2): 1-53 (2002)
176EEOded Goldreich, Avi Wigderson: Derandomization that is rarely wrong from short advice that is typically good Electronic Colloquium on Computational Complexity (ECCC)(039): (2002)
175EERussell 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)
174EEMichael 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
172EEOded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover. ICALP 2001: 334-345
171EERussell 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
170EEJohan Håstad, Avi Wigderson: Simple Analysis of Graph Tests for Linearity and PCP. IEEE Conference on Computational Complexity 2001: 244-254
169EEAmir Shpilka, Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1): 1-27 (2001)
168EEOmer 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)
167EEOded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover Electronic Colloquium on Computational Complexity (ECCC) 8(46): (2001)
166EEEli Ben-Sasson, Avi Wigderson: Short proofs are narrow - resolution made simple. J. ACM 48(2): 149-169 (2001)
165EERussell 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
160EERussell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. STOC 2000: 1-10
159EEMichael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367
158EENathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica 20(4): 545-568 (2000)
157EEMichael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity Electronic Colloquium on Computational Complexity (ECCC) 7(23): (2000)
156EEOded Goldreich, Salil P. Vadhan, Avi Wigderson: Simplified derandomization of BPP using a hitting set generator. Electronic Colloquium on Computational Complexity (ECCC) 7(4): (2000)
155EEEli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near-Optimal Separation of Treelike and General Resolution Electronic Colloquium on Computational Complexity (ECCC) 7(5): (2000)
154EEOded Goldreich, Avi Wigderson: On Pseudorandomness with respect to Deterministic Observers. Electronic Colloquium on Computational Complexity (ECCC) 7(56): (2000)
153EEOmer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing Electronic Colloquium on Computational Complexity (ECCC) 7(59): (2000)
152EERussell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length Electronic Colloquium on Computational Complexity (ECCC) 7(9): (2000)
151EERoy 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
150EERussell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS 1999: 181-190
149EEZiv Bar-Yossef, Oded Goldreich, Avi Wigderson: Deterministic Amplification of Space-Bounded Probabilistic Algorithms. IEEE Conference on Computational Complexity 1999: 188-
148EEEli Ben-Sasson, Avi Wigderson: Short Proofs Are Narrow - Resolution Made Simple (Abstract). IEEE Conference on Computational Complexity 1999: 2
147EEAvi Wigderson: De-Randomizing BPP: The State of the Art. IEEE Conference on Computational Complexity 1999: 76-
146EEAmir 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
143EEEli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution Made Simple. STOC 1999: 517-526
142EEAvi Wigderson, David Zuckerman: Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19(1): 125-138 (1999)
141EELászló Babai, Anna Gál, Avi Wigderson: Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica 19(3): 301-319 (1999)
140EEEli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution made Simple Electronic Colloquium on Computational Complexity (ECCC) 6(22): (1999)
139EEAmir Shpilka, Avi Wigderson: Depth-3 Arithmetic Formulae over Fields of Characteristic Zero Electronic Colloquium on Computational Complexity (ECCC) 6(23): (1999)
138EEMichael 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
136EEAndris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351
135EERussell Impagliazzo, Avi Wigderson: Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS 1998: 734-743
134EEAvi Wigderson: Do Probabilistic Algorithms Outperform Deterministic Ones? ICALP 1998: 212-214
133EEHarry Buhrman, Richard Cleve, Avi Wigderson: Quantum vs. Classical Communication and Computation. STOC 1998: 63-68
132EENathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC 1998: 644-652
131EEZiv 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
128EERussell Impagliazzo, Avi Wigderson: P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. STOC 1997: 220-229
127EERoy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou: SL <= L4/3. STOC 1997: 230-239
126EEItzhak Parnafes, Ran Raz, Avi Wigderson: Direct Product Results and the GCD Problem, in Old and New Communication Models. STOC 1997: 363-372
125EEAlexander 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
120EELá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)
117EEOded 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
114EEIvan 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
111EEPeter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On data structures and asymmetric communication complexity. STOC 1995: 103-111
110EENoam 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)
105EEAnna Gál, Avi Wigderson: Boolean Complexity Classes vs. Their Arithmetic Analogs Electronic Colloquium on Computational Complexity (ECCC) 2(49): (1995)
104EEOded Goldreich, Noam Nisan, Avi Wigderson: On Yao's XOR-Lemma Electronic Colloquium on Computational Complexity (ECCC) 2(50): (1995)
103EELá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)
102EEIlan 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
99EERussell Impagliazzo, Noam Nisan, Avi Wigderson: Pseudorandomness for network algorithms. STOC 1994: 356-364
98EEOded Goldreich, Avi Wigderson: Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. STOC 1994: 574-584
97EEAvi Wigderson: The amazing power of pairwise independence (abstract). STOC 1994: 645-647
96EEAnne 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)
92EENoam Nisan, Avi Wigderson: On Rank vs. Communication Complexity Electronic Colloquium on Computational Complexity (ECCC) 1(1): (1994)
91EEOded 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
86EEAvi Wigderson, David Zuckerman: Expanders that beat the eigenvalue bound: explicit construction and applications. STOC 1993: 245-251
85EEMauricio 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)
81EEMauricio 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
72EEJoseph Gil, William L. Steiger, Avi Wigderson: Geometric medians. Discrete Mathematics 108(1-3): 37-51 (1992)
71EERan 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)
61EEOded 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
52EEMichael 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
49EEFaith 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
34EEEli 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
31EEOded 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
14EERichard 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)
3EEAvi 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

Coauthor Index

1Scott Aaronson [225] [227]
2Alok Aggarwal [20] [64]
3Miklós Ajtai [21]
4Michael Alekhnovich [138] [157] [159] [162] [174] [191]
5Noga Alon [54] [107] [173]
6Helmut Alt [118]
7Andris Ambainis [136] [185]
8Roy Armoni [122] [127] [151]
9László Babai [82] [120] [141]
10Ziv Bar-Yossef [131] [149]
11Boaz Barak [189] [197] [200] [205] [211]
12Paul Beame [201] [209]
13Shai Ben-David [58] [93]
14Michael Ben-Or [44] [45] [52]
15Eli Ben-Sasson [138] [140] [143] [148] [155] [157] [159] [162] [166] [174] [187] [191] [193]
16Allan Borodin [24] [26] [32] [36] [58] [93]
17Harry Buhrman [133]
18Michael R. Capalbo [180] [184]
19Richard Cleve [133]
20Aviad Cohen [51]
21Anne Condon [96] [129]
22Ivan Damgård [114]
23Irit Dinur [207] [214]
24Danny Dolev [2] [6]
25Zeev Dvir [217] [219] [224] [229]
26Cynthia Dwork [6]
27Faith Ellen (Faith Ellen Fich, Faith E. Fich) [10] [15] [24] [26] [32] [36] [38] [42] [49] [55]
28Uriel Feige [107]
29Lance Fortnow [82]
30Ehud Friedgut [182]
31Joel Friedman [109]
32Ariel Gabizon [217] [219]
33Anna Gál [105] [116] [120] [141]
34Hana Galperin [4]
35Peter Gemmell [68]
36Joseph Gil (Yossi Gil) [60] [72] [115]
37Oded Goldreich [25] [30] [31] [35] [61] [91] [98] [104] [114] [117] [119] [123] [131] [144] [149] [154] [156] [161] [167] [172] [176] [177] [181]
38Shafi Goldwasser [44] [45] [52]
39Leonidas J. Guibas [118]
40Venkatesan Guruswami [232]
41Johan Håstad [170] [186] [215]
42Friedhelm Meyer auf der Heide [15] [19] [24] [26] [32] [33] [36] [46] [48] [60] [115]
43Rafi Heiman [57] [63] [66] [77]
44Lisa Hellerstein [96] [129]
45Shlomo Hoory [79]
46Russell Impagliazzo [94] [99] [128] [135] [150] [152] [155] [160] [165] [171] [175] [193] [197] [205] [210] [223] [228]
47Ragesh Jaiswal [223] [228]
48Bettina Just [46] [48]
49Valentine Kabanets [171] [175] [223] [228]
50Jeff Kahn [182]
51Gil Kalai [226]
52Mauricio Karchmer [43] [53] [54] [65] [73] [81] [84] [85] [89] [106]
53Richard M. Karp [9] [14] [16] [17] [18] [22] [29] [40] [58] [93] [118]
54Joe Kilian [44] [52]
55Guy Kindler [200] [230]
56Maria M. Klawe [20] [64]
57János Kollár [120]
58James R. Lee [232]
59David Lichtenstein [20] [64]
60Nathan Linial (Nati Linial) [20] [27] [41] [64] [81] [132] [158]
61Richard J. Lipton [68]
62Douglas L. Long [7] [39]
63László Lovász [27] [41] [70] [103]
64Chi-Jen Lu [188]
65Alexander Lubotzky [173]
66Michael Luby [88] [198]
67Nimrod Megiddo [23]
68Kurt Mehlhorn [118]
69Roy Meshulam [179] [183] [192]
70Silvio Micali [25] [30] [31] [35] [61]
71Peter Bro Miltersen [111] [130]
72Moni Naor [70] [103]
73Ilan Newman [56] [57] [70] [73] [77] [81] [89] [102] [103]
74Noam Nisan [47] [67] [76] [78] [82] [90] [92] [99] [101] [104] [108] [110] [111] [113] [124] [130]
75Ryan O'Donnell [230]
76Tatsuaki Okamoto [114]
77Rafail Ostrovsky [87]
78Itzhak Parnafes [126]
79Nicholas Pippenger [6]
80Toniann Pitassi [201] [209]
81Samuel Pottle [96] [129]
82Yuri Rabinovich [69] [75] [137]
83Prabhakar Ragde [10] [15] [37] [38] [42] [56] [62]
84Anup Rao [211] [230]
85Ran Raz [50] [59] [65] [71] [94] [106] [126]
86Alexander A. Razborov [80] [83] [125] [138] [157] [159] [162] [174] [178] [191]
87Omer Reingold [153] [163] [164] [168] [180] [184] [188] [206]
88Lajos Rónyai [120]
89Eyal Rozenman [195] [203]
90Ronitt Rubinfeld [68]
91Shmuel Safra [111] [130]
92Michael E. Saks [28] [29] [73] [81] [89] [122]
93Alex Samorodnitsky [132] [158]
94Leonard J. Schulman [136] [185]
95Nathan Segerlind [201] [209]
96Aner Shalev [195] [203]
97Ronen Shaltiel [150] [152] [153] [160] [164] [189] [200] [206] [210] [211]
98Roded Sharan [121]
99Amir Shpilka [139] [146] [169] [196] [204]
100Alistair Sinclair [75]
101William L. Steiger [37] [72]
102Benny Sudakov [200]
103Madhu Sudan [68] [187] [207] [214]
104Tibor Szabó [120]
105Endre Szemerédi [37] [76] [83]
106Amnon Ta-Shma [127] [136] [151] [185]
107Gábor Tardos [58] [93]
108Eli Upfal [11] [16] [17] [18] [22] [24] [26] [32] [34] [36] [40]
109Salil P. Vadhan [156] [163] [167] [168] [172] [177] [180] [184] [187] [188]
110Umesh V. Vazirani [136] [185]
111Boban Velickovic [88]
112Gopalakrishnan Vijayan [12]
113Emanuele Viola [216] [218] [220] [222]
114Uzi Vishkin [5] [8] [13]
115David Xiao [199] [202] [208] [221]
116Andrew Chi-Chih Yao [125] [178]
117Shiyu Zhou [122] [127] [151]
118David Zuckerman [86] [107] [142]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)