2011
55Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson. STOC 2011, 519-528. Web SearchBibTeXDownload
2010
54Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff. CoRR (abs/1009.4375) (2010). Web SearchBibTeXDownload
53Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson. Electronic Colloquium on Computational Complexity (ECCC) (17): 37 (2010). Web SearchBibTeXDownload
52Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson. J. ACM (57) (2010). Web SearchBibTeXDownload
51Public-key cryptography from different assumptions. Benny Applebaum, Boaz Barak, Avi Wigderson. STOC 2010, 171-180. Web SearchBibTeXDownload
2008
50Public Key Cryptography from Different Assumptions. Boaz Barak, Avi Wigderson. IACR Cryptology ePrint Archive (2008): 335 (2008). Web SearchBibTeXDownload
2006
49Robust Local Testability of Tensor Products of LDPC Codes. Irit Dinur, Madhu Sudan, Avi Wigderson. APPROX-RANDOM 2006, 304-315. Web SearchBibTeXDownload
48Extracting Randomness Using Few Independent Sources. Boaz Barak, Russell Impagliazzo, Avi Wigderson. SIAM J. Comput. (36): 1095-1118 (2006). Web SearchBibTeXDownload
472-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson. STOC 2006, 671-680. Web SearchBibTeXDownload
2005
46Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson. STOC 2005, 1-10. Web SearchBibTeXDownload
2004
45Extracting Randomness Using Few Independent Sources. Boaz Barak, Russell Impagliazzo, Avi Wigderson. FOCS 2004, 384-393. Web SearchBibTeXDownload
2003
44Computational Analogues of Entropy. Boaz Barak, Ronen Shaltiel, Avi Wigderson. RANDOM-APPROX 2003, 200-215. Web SearchBibTeXDownload
2001
43Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. Noga Alon, Alexander Lubotzky, Avi Wigderson. FOCS 2001, 630-637. Web SearchBibTeXDownload
1999
42Deterministic Amplification of Space-Bounded Probabilistic Algorithms. Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson. IEEE Conference on Computational Complexity 1999, 188. Web SearchBibTeXDownload
1998
41Deterministic Amplification of Space Bounded Probabilistic Algorithms. Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson. Electronic Colloquium on Computational Complexity (ECCC) (5) (1998). Web SearchBibTeXDownload
40On the Power of Finite Automata with Both Nondeterministic and Probabilistic States. Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson. SIAM J. Comput. (27): 739-762 (1998). Web SearchBibTeXDownload
1996
39A Method for Obtaining Randomized Algorithms with Small Tail Probabilities. Helmut Alt, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, Avi Wigderson. Algorithmica (16): 543-547 (1996). Web SearchBibTeXDownload
38The Tree Model for Hashing: Lower and Upper Bounds. Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson. SIAM J. Comput. (25): 936-955 (1996). Web SearchBibTeXDownload
37The future of computational complexity theory: part I. Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser. SIGACT News (27): 6-12 (1996). Web SearchBibTeXDownload
36Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson. STOC 1996, 603-611. Cited by 27Web SearchBibTeXDownload
1995
35Derandomized Graph Products. Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman. Computational Complexity (5): 60-75 (1995). Web SearchBibTeXDownload
34Search Problems in the Decision Tree Model. László Lovász, Moni Naor, Ilan Newman, Avi Wigderson. SIAM J. Discrete Math. (8): 119-132 (1995). Web SearchBibTeXDownload
1994
33On the Power of Randomization in On-Line Algorithms. Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson. Algorithmica (11): 2-14 (1994). Web SearchBibTeXDownload
32On the power of finite automata with both nondeterministic and probabilistic states (preliminary version). Anne Condon, Lisa Hellerstein, Samuel Pottle, Avi Wigderson. STOC 1994, 676-685. Web SearchBibTeXDownload
1993
31One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. Rafail Ostrovsky, Avi Wigderson. ISTCS 1993, 3-17. Web SearchBibTeX
1992
30Geometric medians. Joseph Gil, William L. Steiger, Avi Wigderson. Discrete Mathematics (108): 37-51 (1992). Web SearchBibTeXDownload
1991
29Search Problems in the Decision Tree Model (Preliminary Version). László Lovász, Moni Naor, Ilan Newman, Avi Wigderson. FOCS 1991, 576-585. Web SearchBibTeXDownload
28Linear-Size Constant-Depth Polylog-Treshold Circuits. Prabhakar Ragde, Avi Wigderson. Inf. Process. Lett. (39): 143-146 (1991). Web SearchBibTeXDownload
27Self-Testing/Correcting for Polynomials and for Approximate Functions. Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson. STOC 1991, 32-42. Web SearchBibTeXDownload
1990
26Linear Circuits over GF(2). Noga Alon, Mauricio Karchmer, Avi Wigderson. SIAM J. Comput. (19): 1064-1067 (1990). Web SearchBibTeXDownload
25On the Power of Randomization in Online Algorithms (Extended Abstract). Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson. STOC 1990, 379-386. Web SearchBibTeXDownload
24Not All Keys Can Be Hashed in Constant Time (Preliminary Version). Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson. STOC 1990, 244-253. Web SearchBibTeXDownload
23Perfect Hashing, Graph Entropy, and Circuit Complexity. Ilan Newman, Prabhakar Ragde, Avi Wigderson. Structure in Complexity Theory Conference 1990, 91-99. Web SearchBibTeXDownload
1988
22Simulations Among Concurrent-Write PRAMs. Faith E. Fich, Prabhakar Ragde, Avi Wigderson. Algorithmica (3): 43-51 (1988). Web SearchBibTeXDownload
21The Complexity of Parallel Search. Richard M. Karp, Eli Upfal, Avi Wigderson. J. Comput. Syst. Sci. (36): 225-253 (1988). Web SearchBibTeXDownload
20Relations Between Concurrent-Write Models of Parallel Computation. Faith E. Fich, Prabhakar Ragde, Avi Wigderson. SIAM J. Comput. (17): 606-627 (1988). Web SearchBibTeXDownload
19The Parallel Complexity of Element Distinctness is Omega (sqrt(log n)). Prabhakar Ragde, William L. Steiger, Endre Szemerédi, Avi Wigderson. SIAM J. Discrete Math. (1): 399-410 (1988). Web SearchBibTeXDownload
18A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson. Theor. Comput. Sci. (58): 57-68 (1988). Web SearchBibTeXDownload
1987
17How to share memory in a distributed system. Eli Upfal, Avi Wigderson. J. ACM (34): 116-127 (1987). Web SearchBibTeXDownload
16A Time-Space Tradeoff for Element Distinctness. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson. SIAM J. Comput. (16): 97-99 (1987). Web SearchBibTeXDownload
1986
15Constructing a perfect matching is in random NC. Richard M. Karp, Eli Upfal, Avi Wigderson. Combinatorica (6): 35-48 (1986). Web SearchBibTeXDownload
14On a Search Problem Related to Branch-and-Bound Procedures. Richard M. Karp, Michael E. Saks, Avi Wigderson. FOCS 1986, 19-28. Web SearchBibTeXDownload
13A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson. ICALP 1986, 50-59. Web SearchBibTeXDownload
12A Time-Space Tradeoff for Element Distinctness. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson. STACS 1986, 353-358. Web SearchBibTeXDownload
11On Play by Means of Computing Machines. Nimrod Megiddo, Avi Wigderson. TARK 1986, 259-274. Web SearchBibTeX
1985
10The Complexity of Parallel Computation on Matroids. Richard M. Karp, Eli Upfal, Avi Wigderson. FOCS 1985, 541-550. Web SearchBibTeXDownload
9A Fast Parallel Algorithm for the Maximal Independent Set Problem. Richard M. Karp, Avi Wigderson. J. ACM (32): 762-773 (1985). Web SearchBibTeXDownload
8Are Search and Decision Problems Computationally Equivalent?. Richard M. Karp, Eli Upfal, Avi Wigderson. STOC 1985, 464-475. Web SearchBibTeXDownload
7One, Two, Three \\dots Infinity: Lower Bounds for Parallel Computation. Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde, Avi Wigderson. STOC 1985, 48-58. Web SearchBibTeXDownload
6Constructing a Perfect Matching is in Random NC. Richard M. Karp, Eli Upfal, Avi Wigderson. STOC 1985, 22-32. Web SearchBibTeXDownload
1984
5How to Share Memory in a Distributed System (A Preliminary Version). Eli Upfal, Avi Wigderson. FOCS 1984, 171-180. Web SearchBibTeXDownload
4Relations Between Concurrent-Write Models of Parallel Computation. Faith E. Fich, Prabhakar Ragde, Avi Wigderson. PODC 1984, 179-189. Web SearchBibTeXDownload
3A Fast Parallel Algorithm for the Maximal Independent Set Problem. Richard M. Karp, Avi Wigderson. STOC 1984, 266-272. Web SearchBibTeXDownload
1983
2Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson. STOC 1983, 42-51. Web SearchBibTeXDownload
1982
1On the Security of Multi-Party Protocols in Distributed Systems. Danny Dolev, Avi Wigderson. CRYPTO 1982, 167-175. Web SearchBibTeX
from DBLP and Google Scholar
Developed by the Database Group at the University of Wisconsin and Yahoo! Research