2008 | ||
---|---|---|
232 | EE | 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 | EE | Avi Wigderson: Randomness - A Computational Complexity Perspective. CSR 2008: 1-2 |
230 | EE | Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson: Spherical Cubes and Rounding in High Dimensions. FOCS 2008: 189-198 |
229 | EE | Zeev Dvir, Avi Wigderson: Kakeya Sets, New Mergers and Old Extractors. FOCS 2008: 625-633 |
228 | EE | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson: Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588 |
227 | EE | Scott Aaronson, Avi Wigderson: Algebrization: a new barrier in complexity theory. STOC 2008: 731-740 |
226 | EE | Gil Kalai, Avi Wigderson: Neighborly Embedded Manifolds. Discrete & Computational Geometry 40(3): 319-324 (2008) |
225 | EE | Scott Aaronson, Avi Wigderson: Algebrization: A New Barrier in Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC) 15(005): (2008) |
224 | EE | Zeev Dvir, Avi Wigderson: Kakeya sets, new mergers and old extractors. Electronic Colloquium on Computational Complexity (ECCC) 15(058): (2008) |
223 | EE | 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 | EE | Emanuele Viola, Avi Wigderson: Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1): 137-168 (2008) |
221 | EE | 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 | EE | Emanuele Viola, Avi Wigderson: One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. FOCS 2007: 427-437 |
219 | EE | Zeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors and Rank Extractors for Polynomial Sources. FOCS 2007: 52-62 |
218 | EE | 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 | EE | Zeev Dvir, Ariel Gabizon, Avi Wigderson: Extractors and Rank Extractors for Polynomial Sources. Electronic Colloquium on Computational Complexity (ECCC) 14(056): (2007) |
216 | EE | 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 | EE | Johan Håstad, Avi Wigderson: The Randomized Communication Complexity of Set Disjointness. Theory of Computing 3(1): 211-219 (2007) |
2006 | ||
214 | EE | Irit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM 2006: 304-315 |
213 | EE | Avi Wigderson: Applications of the Sum-Product Theorem in Finite Fields. IEEE Conference on Computational Complexity 2006: 111 |
212 | EE | Avi Wigderson: The Power and Weakness of Randomness in Computation. LATIN 2006: 28-29 |
211 | EE | 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 | EE | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Reducing The Seed Length In The Nisan-Wigderson Generator. Combinatorica 26(6): 647-681 (2006) |
209 | EE | 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 | EE | 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 | EE | 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 | EE | Omer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing. SIAM J. Comput. 35(5): 1185-1209 (2006) |
205 | EE | Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006) |
204 | EE | Amir Shpilka, Avi Wigderson: Derandomizing Homomorphism Testing in General Groups. SIAM J. Comput. 36(4): 1215-1230 (2006) |
203 | EE | Eyal Rozenman, Aner Shalev, Avi Wigderson: Iterative Construction of Cayley Expander Graphs. Theory of Computing 2(1): 91-120 (2006) |
2005 | ||
202 | EE | Avi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. FOCS 2005: 397-406 |
201 | EE | 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 | EE | 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 | EE | Avi Wigderson, David Xiao: A Randomness-Efficient Sampler for Matrix-valued Functions and Applications Electronic Colloquium on Computational Complexity (ECCC)(107): (2005) |
198 | EE | Michael Luby, Avi Wigderson: Pairwise Independence and Derandomization. Foundations and Trends in Theoretical Computer Science 1(4): (2005) |
2004 | ||
197 | EE | Boaz Barak, Russell Impagliazzo, Avi Wigderson: Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393 |
196 | EE | Amir Shpilka, Avi Wigderson: Derandomizing homomorphism testing in general groups. STOC 2004: 427-435 |
195 | EE | Eyal Rozenman, Aner Shalev, Avi Wigderson: A new family of Cayley expanders (?). STOC 2004: 445-454 |
194 | EE | Avi Wigderson: Depth through breadth, or why should we attend talks in other areas? STOC 2004: 579 |
193 | EE | Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near Optimal Separation Of Tree-Like And General Resolution. Combinatorica 24(4): 585-603 (2004) |
192 | EE | Roy Meshulam, Avi Wigderson: Expanders In Group Algebras. Combinatorica 24(4): 659-680 (2004) |
191 | EE | 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 | EE | Avi Wigderson: Zigzag Products, Expander Constructions, Connections, and Applications. FSTTCS 2003: 443 |
189 | EE | Boaz Barak, Ronen Shaltiel, Avi Wigderson: Computational Analogues of Entropy. RANDOM-APPROX 2003: 200-215 |
188 | EE | Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Extractors: optimal up to constant factors. STOC 2003: 602-611 |
187 | EE | 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 | EE | Johan Håstad, Avi Wigderson: Simple analysis of graph tests for linearity and PCP. Random Struct. Algorithms 22(2): 139-160 (2003) |
185 | EE | 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 | EE | 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 | EE | Roy Meshulam, Avi Wigderson: Expanders from Symmetric Codes. IEEE Conference on Computational Complexity 2002: 16 |
182 | EE | Ehud Friedgut, Jeff Kahn, Avi Wigderson: Computing Graph Properties by Randomized Subcube Partitions. RANDOM 2002: 105-113 |
181 | EE | Oded Goldreich, Avi Wigderson: Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good. RANDOM 2002: 209-223 |
180 | EE | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson: Randomness conductors and constant-degree lossless expanders. STOC 2002: 659-668 |
179 | EE | Roy Meshulam, Avi Wigderson: Expanders from symmetric codes. STOC 2002: 669-677 |
178 | EE | 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 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On interactive proofs with a laconic prover. Computational Complexity 11(1-2): 1-53 (2002) |
176 | EE | 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 | EE | 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 | EE | 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 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover. ICALP 2001: 334-345 |
171 | EE | 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 | EE | Johan Håstad, Avi Wigderson: Simple Analysis of Graph Tests for Linearity and PCP. IEEE Conference on Computational Complexity 2001: 244-254 |
169 | EE | Amir Shpilka, Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1): 1-27 (2001) |
168 | EE | 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 | EE | Oded Goldreich, Salil P. Vadhan, Avi Wigderson: On Interactive Proofs with a Laconic Prover Electronic Colloquium on Computational Complexity (ECCC) 8(46): (2001) |
166 | EE | Eli Ben-Sasson, Avi Wigderson: Short proofs are narrow - resolution made simple. J. ACM 48(2): 149-169 (2001) |
165 | EE | 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 | EE | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Extractors and pseudo-random generators with optimal seed length. STOC 2000: 1-10 |
159 | EE | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367 |
158 | EE | Nathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica 20(4): 545-568 (2000) |
157 | EE | 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 | EE | 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 | EE | 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 | EE | Oded Goldreich, Avi Wigderson: On Pseudorandomness with respect to Deterministic Observers. Electronic Colloquium on Computational Complexity (ECCC) 7(56): (2000) |
153 | EE | Omer Reingold, Ronen Shaltiel, Avi Wigderson: Extracting Randomness via Repeated Condensing Electronic Colloquium on Computational Complexity (ECCC) 7(59): (2000) |
152 | EE | 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 | EE | 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 | EE | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson: Near-Optimal Conversion of Hardness into Pseudo-Randomness. FOCS 1999: 181-190 |
149 | EE | Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson: Deterministic Amplification of Space-Bounded Probabilistic Algorithms. IEEE Conference on Computational Complexity 1999: 188- |
148 | EE | Eli Ben-Sasson, Avi Wigderson: Short Proofs Are Narrow - Resolution Made Simple (Abstract). IEEE Conference on Computational Complexity 1999: 2 |
147 | EE | Avi Wigderson: De-Randomizing BPP: The State of the Art. IEEE Conference on Computational Complexity 1999: 76- |
146 | EE | 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 | EE | Eli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution Made Simple. STOC 1999: 517-526 |
142 | EE | Avi Wigderson, David Zuckerman: Expanders That Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19(1): 125-138 (1999) |
141 | EE | László Babai, Anna Gál, Avi Wigderson: Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica 19(3): 301-319 (1999) |
140 | EE | Eli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution made Simple Electronic Colloquium on Computational Complexity (ECCC) 6(22): (1999) |
139 | EE | Amir Shpilka, Avi Wigderson: Depth-3 Arithmetic Formulae over Fields of Characteristic Zero Electronic Colloquium on Computational Complexity (ECCC) 6(23): (1999) |
138 | EE | 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 | EE | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351 |
135 | EE | Russell Impagliazzo, Avi Wigderson: Randomness vs. Time: De-Randomization under a Uniform Assumption. FOCS 1998: 734-743 |
134 | EE | Avi Wigderson: Do Probabilistic Algorithms Outperform Deterministic Ones? ICALP 1998: 212-214 |
133 | EE | Harry Buhrman, Richard Cleve, Avi Wigderson: Quantum vs. Classical Communication and Computation. STOC 1998: 63-68 |
132 | EE | Nathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC 1998: 644-652 |
131 | EE | 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 | EE | Russell Impagliazzo, Avi Wigderson: P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. STOC 1997: 220-229 |
127 | EE | Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou: SL <= L4/3. STOC 1997: 230-239 |
126 | EE | Itzhak Parnafes, Ran Raz, Avi Wigderson: Direct Product Results and the GCD Problem, in Old and New Communication Models. STOC 1997: 363-372 |
125 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On data structures and asymmetric communication complexity. STOC 1995: 103-111 |
110 | EE | 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 | EE | Anna Gál, Avi Wigderson: Boolean Complexity Classes vs. Their Arithmetic Analogs Electronic Colloquium on Computational Complexity (ECCC) 2(49): (1995) |
104 | EE | Oded Goldreich, Noam Nisan, Avi Wigderson: On Yao's XOR-Lemma Electronic Colloquium on Computational Complexity (ECCC) 2(50): (1995) |
103 | EE | 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 | EE | 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 | EE | Russell Impagliazzo, Noam Nisan, Avi Wigderson: Pseudorandomness for network algorithms. STOC 1994: 356-364 |
98 | EE | 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 | EE | Avi Wigderson: The amazing power of pairwise independence (abstract). STOC 1994: 645-647 |
96 | EE | 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 | EE | Noam Nisan, Avi Wigderson: On Rank vs. Communication Complexity Electronic Colloquium on Computational Complexity (ECCC) 1(1): (1994) |
91 | EE | 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 | EE | Avi Wigderson, David Zuckerman: Expanders that beat the eigenvalue bound: explicit construction and applications. STOC 1993: 245-251 |
85 | EE | 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 | EE | 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 | EE | Joseph Gil, William L. Steiger, Avi Wigderson: Geometric medians. Discrete Mathematics 108(1-3): 37-51 (1992) |
71 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 |