Publication List
Restriction Access
Proceedings of ITCS (Innovations in Theoretical Computer Science) 2012, pp. 19-33, 2012.
Population Recovery and Partial Identification
Non-commutative circuits and the sum-of-squares problem
ECCC Report TR10-021, 2010
Accepted for STOC 2010
(Abstract)
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
Accepted JACM 2010
Relationless completeness and separations
ECCC Report TR10-040, 2010
Accepted for CCC 2010
(Abstract)
Symmetric LDPC codes and local testing
Accepted ICS 2010
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Proceedings of STOC 08, pp. 579--588, 2008.
SIAM J. Comput., vol. 39, no. 4, pp. 1637-1665, 2010.
(Abstract)
Relationless completeness and separations
ECCC Report TR10-040, 2010
Accepted for CCC 2010
(Abstract)
10. Z. Dvir, A. Gabizon, A. Wigderson
Extractors and rank extractors for polynomial sources
Proceedings of the FOCS 07 conference, pp. 52--62, 2007.
ECCC Report TR07-056, 2007
Computational Complexity, vol. 18, no. 1, pp. 1-58, 2009.
(Abstract)
New Direct-Product Testers and 2-Query PCPs
Proceedings of STOC 09, pp. 131-140, 2009.
ECCC Report TR09-090, 2009
(Abstract)
12. S. Arora, D. Steurer, A. Wigderson
Towards a study of low-complexity graphs
Proceedings of ICALP 2009, pp. 119-131.
(Abstract)
14. Z. Dvir, A. Wigderson
Monotone expanders - constructions and applications
ECCC Report TR09-135, 2009
(Abstract)
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Proceedings of STOC 08, pp. 579-588, 2008.
SIAM J. Comput., vol. 39, no. 4, pp. 1637-1665, 2010.
16. E. Viola, A. Wigderson
Norms, XOR lemmas, and lower bounds for \(GF(2)\) polynomials and multiparty protocols
Proceedings of the CCC07, pp. 141--154, 2007.
Theory of Computing, vol. 4, Article 7, pp. 137--168, 2008.
(Abstract)
17. V. Guruswami, J. Lee, A. Wigderson
Euclidean sections of \(l_1^N\) with sublinear randomness and error-correction over the reals
APPROX-RANDOM 2008, pp. 444-454.
(Abstract)
18. S. Aaronson, A. Wigderson
Algebrization: A New Barrier in Complexity Theory
Proceedings of STOC 08, pp. 731--740, 2008.
(Abstract)
19. G. Kalai, A. Wigderson
Neighborly Embedded Manifolds
Discrete and Computational Geometry, vo. 40, no. 3, pp. 319-324, 2008.
(Abstract)
20. Z. Dvir, A. Wigderson
Kakeya sets, new mergers and old extractors
Proceedings of the 49th Annual FOCS08, pp. 625--633, 2008.
(Abstract)
Spherical Cubes and Rounding in High Dimensions
Proceedings of the 49th Annual FOCS08, pp. 189--198, 2008.
(Abstract)
22. A. Wigderson
P, NP and Mathematics - a computational complexity perspective
Proceedings of the ICM 06 (Madrid), vol. 1, EMS Publishing House, Zurich, pp. 665--712, 2007.
(Abstract)
23. E. Viola, A. Wigderson
One-way multi-party communication lower bound for pointer jumping with applications
Proceedings of the FOCS 07 conference, pp. 427--437, 2007.
ECCC Report TR07-079, 2007
(Abstract)
Extracting Randomness via Repeated Condensing
Proceedings of the 41st FOCS, pp. 22--31, 2000
SIAM Journal on Computing, vol. 35, no. 5, pp. 1185--1209, 2006.
(Abstract)
25. A. Shpilka, A. Wigderson
Derandomizing homomorphism testing in general groups
36th Annual ACM Symposium, STOC 2004, pp. 427--435, 2004.
SICOMP, vol. 36, no. 4, pp. 1215--1230, 2006.
(Abstract)
A Strong Direct Product Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
CCC05, pp 52--66, 2005.
Computational Complexity, vol. 15, no. 4, pp. 391--432, 2006.
(Abstract)
27. E. Rozenman, A. Wigderson
Iterative construction of Cayley expander graphs
Theory of Computing, vol. 2, no. 5, pp. 91--120, 2006. A shorter version appeared in STOC 04.
(Abstract)
28. B. Barak, A. Rao, R. Shaltiel, A. Wigderson
2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction
Proceedings of STOC 06, pp. 671--680, 2006.
(Abstract)
29. I. Dinur, M. Sudan, A. Wigderson
Robust local testability of tensor products of LDPC codes
Proceedings of the 2006 RANDOM conference, pp. 304--315, 2006.
ECCC Report TR06-118, 2006
(Abstract)
30. A. Wigderson, D. Xiao
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
Theory of Computing, vol. 4 (2008), article 3, pp. 53-76.
ECCC Report TR06-105, 2006
(Abstract)
31. S. Hoory, N. Linial, A. Wigderson
Expander graphs and their applications
Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439--561, 2006.
(Abstract)
Reducing the seed length in the Nisan-Wigderson generator
Combinatorica, vol. 26, no. 6, pp. 647--681, 2006.
(Abstract)
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
Proceedings of the 46th STOC 05, pp. 1--10, 2005.
(Abstract)
34. A. Wigderson, D. Xiao
A randomness-efficient sampler for matrix-valued functions and applications
46th Annual Symposium of FOCS 2005, pp. 397--406, 2005.
(Abstract)
Pseudorandom Generators in Propositional Proof Complexity
SIAM Journal on Computing, vol. 34, no. 1, pp. 67--88, 2004. Preliminary version appeared in STOC2000.
(Abstract)
36. R. Meshulam, A. Wigderson
Expanders in Group Algebras
Combinatorica, vol. 24, no. 4, pp. 659--680, 2004.
(Abstract)
Near Optimal Separation of Tree-like and General Resolution
Combinatorica, vol. 24, no. 4, pp. 585--604, 2004.
(Abstract)
38. E. Rozenman, A. Shalev, A. Wigderson
A new family of Cayley expanders (?)
36th Annual ACM Symposium, STOC 2004, pp. 445--454, 2004.
(Abstract)
The Quantum Communication Complexity of Sampling
Siam Journal on Computing, vol. 32, pp. 1570--1585, 2003.
(Abstract)
40. J. Hastad, A. Wigderson
Simple Analysis of Graph Tests for Linearity and PCP
Random Structures and Algorithms, vol. 22, no. 2, pp 139--160, 2003.
(Abstract)
41. A. Razborov, A. Wigderson, A. Yao
Read-once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
Combinatorica, vol. 22, no. 4, pp. 555--574, 2003.
(Abstract)
The Quantum Communication Complexity of Sampling
SIAM Journal on Computing, vol. 32, no. 6, pp 1570--1585, 2003.
(Abstract)
On Interactive Proofs With a Laconic Power
Journal of Computational Complexity, vol. 2076, p. 334, 2003.
(Abstract)
44. B. Barak, R. Shaltiel, A. Wigderson
Computational Analogues of Entropy
11th International Conference on Random Structures and Algorithms, pp. 200--215, August 2003.
(Abstract)
Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets
35th Annual ACM Symposium, STOC 2003, pp. 612--621, 2003.
(Abstract)
46. C-J Lu, O. Reingold, S. Vadhan, A. Wigderson
Extractors: Optimal up to Constant Factors
35th Annual ACM Symposium, STOC 2003, pp. 602--611, 2003.
(Abstract)
47. O. Reingold, S. Vadhan, A. Wigderson
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
Annals of Mathematics, vol. 155, no.1, pp. 157--187, 2002.
(Abstract)
48. E. Friedgut, A. Wigderson
Computing Graph Properties by Randomized Subcube Partitions
Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 105--113, 2002.
(Abstract)
49. O. Goldreich, A. Wigderson
Derandomization that is Rarely Wrong from Short Advice that is Typically Good
Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 209--223, 2002.
(Abstract)
Randomness Conductors and Constant-Degree Expansion Beyond the Degree /2 Barrier
Proceedings of the 34th STOC, pp. 659--668, 2002.
(Abstract)
51. N. Alon, A. Lubotzky, A. Wigderson
Semi-direct product in groups and Zig-zag product in graphs: Connections and applications
Proceedings of the 42nd FOCS, pp. 630-637, 2001.
(Abstract)
52. J. Hastad, A. Wigderson
Simple Analysis of Graph Tests
Conference on Computational Complexity, pp. 244--255, 2001. (see also ECCC)
(Abstract)
On Interactive Proofs with a Laconic Power
Proceedings of the 28th ICALP, pp. 334-345, 2001.
(Abstract)
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time
JCSS, vol. 65, no. 4, pp 672--694, 2002.
Conference on Computational Complexity, pp. 2--12, 2001.
(Abstract)
Space Complexity in Propositional Calculus
SIAM Journal of Computing, vol. 31, no. 4, pp. 1184--1211, 2001. Preliminary version appeared in STOC 2000.
(Abstract)
56. A. Ta-Shma, A. Wigderson
A \((\log n )^{4/3}\) space algorithm for (s,t) connectivity in undirected graphs
Preliminary version in Proceedings of the 29th STOC, pp. 230--239, 1997.
J. ACM, vol. 47, no. 2, 294--311, 2000.
(Abstract)
Extractors and Pseudo-random Generators with Optimal Seed Length
Proceedings of the 32nd STOC, pp. 1--10, 2000.
(Abstract)
58. O. Goldreich, A. Wigderson
On Pseudorandomness with respect to Deterministic Observers
Proceedings of the satellite workshops of the 27th ICALP, Carleton Scientific (Proc. in Informatics 8), pp. 77--84, 2000.
(Abstract)
59. O. Reingold, S. Vadhan, A. Wigderson
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Proceedings of the 41st FOCS, pp. 3--13, 2000.
(Abstract)
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Proceedings of 30th STOC, pp. 644--652, 1998.
Combinatorica, 20, 4, 2000.
(Abstract)
61. L . Babai, A. Gal, A. Wigderson
Superpolynomial lower bounds for monotone span programs.
Combinatorica, vol. 19, no. 3, 301--319, 1999.
(Abstract)
Techniques for bounding the convergence rate of genetic algorithms.
Random Structures Algorithms, vol. 14, no. 2, 111--138, 1999.
(Abstract)
63. A. Shpilka, A. Wigderson
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Accepted to Journal of Computational Complexity, vol. 10, no. 1, pp. 1-27, 2001.
Preliminary version in Proceedings of the 14th Conference on Computational Complexity, pp. 87--97, 1999.
(Abstract)
Deterministic Amplification of Space-Bounded Probabilistic Algorithms
Proceedings of the 14th Conference on Computational Complexity, pp. 188--199, 1999.
(Abstract)
65. O. Goldreich, A. Wigderson
Improved derandomization of BPP using a hitting set generator
Proceedings of the RAMDOM 99 Conference, pp. 131--137, 1999.
(Abstract)
Near-optimal Conversion of Hardness into Pseudo-randomness
Proceedings of the 40th FOCS, pp. 181--190, 1999.
(Abstract)
Short Proofs are Narrow -- Resolution made Simple
Proceedings of the 31th STOC, pp. 517--526, 1999.
Journal of the ACM, vol. 48, no. 2, pp. 149--169, 2001.
ECCC Report TR99-022, 1999.
(Abstract)
68. H. Buhrman, R. CLeve, A. Wigderson
Quantum vs. Classical Communication and Computation
Proceedings of 30th STOC, pp. 63--68, 1998.
(Abstract)
Randomness vs. Time: De-randomization under a uniform assumption
Proceedings of the 39th FOCS, pp.734--743, 1998.
(Abstract)
70. O. Goldreich, A. Wigderson
Tiny Families of Functions with Random Properties: A Quality--Size Trade--off
Random Structures and Algorithms, vol. 11, no. 4, pp. 315--343, 1997.
(Abstract)
71. A. Razborov, A. Wigderson, A. Yao
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and Transversal Calculus
Proceedings of the 29th STOC, pp. 739--748, 1997.
(Abstract)
72. R. Raz, A. Wigderson
Direct Product Results and the GCD Problem, in Old and New Communication Models
Proceedings of the 29th STOC, pp. 363--372, 1997.
(Abstract)
P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
Proceedings of the 29th STOC, pp. 220--229, 1997.
(Abstract)
75. I. Newman, A. Wigderson
Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy
SIAM Journal on Discrete Mathematics, vol. 8 no. 4, pp. 78--87, 1996.
(Abstract)
76. L. Guibas, R. Karp, K. Mehlhorn, A. Wigderson
A Method for Obtaining Probabilistic Algorithms with Small Tail Probabilities
Algorithmica, vol. 16, no. 4-5, pp. 543--547, 1996.
(Abstract)
77. N. Nisan, A. Wigderson
Lower Bounds on Arithmetic Circuits via Partial Derivatives
Preliminary version in Proceedings of the 36th FOCS, pp. 16--25, 1995.
Computational Complexity, vol. 6, no. 3, pp. 217--234, 1996.
(Abstract)
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
Proceedings of 28th STOC, pp. 603--611, 1996.
(Abstract)
79. R. Sharan, A. Wigderson
A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
Proceedings of ISTCS 96, pp. 56--65, 1996.
(Abstract)
80. M. Saks, A. Wigderson
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
Proceedings of the 37th FOCS, pp. 412--421, 1996.
(Abstract)
81. N. Alon, U. Feige, A. Wigderson, D. Zuckerman
Derandomized Graph Products
Computational Complexity, pp. 60--75, 1995.
(Abstract)
82. L. Lovasz, I. Newman, M. Naor, A. Wigderson
Search Problems in the Decision Tree Model
SIAM J. on Discrete Math., vol. 8, pp. 119--132, 1995. (Preliminary version appeared at Proceedings of the 32nd FOCS conference, pp. 576--585, 1991.)
(Abstract)
83. A. Gal, A. Wigderson
Boolean Complexity Classes vs. Their Arithmetic Analogs
Random Structures and Algorithms, vol. 9, pp. 1--13, 1996.
ECCC Report TR05-049, 1995
(Abstract)
84. P. Miltersen, N. Nisan, S. Safra, A. Wigderson
On Data Structures and Asymmetric Communication Complexity
JCSS, vol. 57, no. 1, pp. 37--49, 1998.
Preliminary version appeared in Proceedings of the 27th STOC, pp. 103--111, 1995.
(Abstract)
85. N. Nisan, A. Wigderson
On the Complexity of Bilinear Forms
Proceedings of the 27th STOC, pp. 723--732, 1995.
(Abstract)
Honest Verifier vs. Dishonest Verifier in Public Coin Zero-Knowledge Proofs
Advances in Cryptology -- Crypto `95 (Proceedings), Lecture Note in Computer Science (963), Springer-Verlag, pp. 325--338, 1995.
(Abstract)
87. O. Goldreich, N. Nisan, A. Wigderson
On Yao's XOR-Lemma
ECCC, TR95-05, 1995.
(Abstract)
[ manuscript (pdf) ] [ manuscript (ps) ]
88. A. Wigderson
NL/poly \(\subseteq \oplus\) L/poly
Proceedings of the 9th Structures in Complexity Conference, pp. 59--62, July 1994.
(Abstract)
89. N. Nisan, A. Wigderson
Hardness vs. Randomness
Journal of Computer Systems and Sciences, vol. 49, no. 2, pp. 149--167, 1994.
(Abstract)
Finite State Automata with Nondeterministic and Probabilistic States
SIAM J. on Computing, vol. 27, no. 3, pp. 739-762, June 1998.
Proceedings of the 26th STOC, pp. 676--685, 1994.
(Abstract)
91. N. Nisan, A. Wigderson
A note on Rank vs. Communication Complexity
Combinatorica, vol. 15, no. 4, pp. 557--566, 1995.
Also appeared in Proceedings of the 35th FOCS, pp. 831--836, 1994.
(Abstract)
92. O. Goldreich, A. Wigderson
Tiny Families of Functions with Random Properties: A Quality--Size Trade--off
Proceedings of the 26th STOC, pp. 574--583, 1994.
(Abstract)
Pseudorandomness for Network Algorithms
Proceedings of the 26th STOC, pp. 356--364, 1994.
(Abstract)
94. A. Razborov, A. Wigderson
\(n^{\Omega(\log n)}\) Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom
IPL, vol. 45, pp. 303--307, 1993.
(Abstract)
95. N. Linial, I. Newman, M. Saks, A. Wigderson
Combinatorial Characterization of Read-Once Formulae
J. Discrete Math. vol. 114, pp. 275--282, 1993.
(Abstract)
96. N. Nisan, A. Wigderson
Rounds in Communication Complexity Revisited
SIAM Journal on Computing, vol. 22, no. 1, pp. 211--219, 1993.
(Abstract)
97. J. Hastad, A. Wigderson
Composition of the Universal Relation
Advances in Computational Complexity Theory, AMS-DIMACS book series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 119--134, 1993.
(Abstract)
98. A. Wigderson, D. Zuckerman
Expanders that beat the eigenvalue bound: explicit construction and applications
Combinatorica, vol. 19, no. 1, 125--138, 1999.
Preliminary version in Proceedings of the 25th STOC, pp. 245--251, 1993.
(Abstract)
99. A. Wigderson
The Fusion Method for Lower Bounds in Circuit Complexity
Combinatorics, Paul Erdos is Eighty (vol. 1), Miklos, Sos and Szonyi (Eds.), Bolyai Math. Society, pp. 453--468, 1993.
(Abstract)
100. A. Wigderson
On Span Programs
Proceedings of the 8th Structures in Complexity conference, pp. 102--111, 1993.
(Abstract)
101. A. Wigderson
On Characterizing Nondeterministic Circuit Size
Proceedings of the 25th STOC, pp. 532--545, 1993.
(Abstract)
102. M. Luby, B. Velickovic, A. Wigderson
Deterministic Approximate Counting of Depth--2 Circuits
Proceedings of the 2nd ISTCS (Israeli Symposium on Theoretical Computer Science), pp. 18--24, 1993.
(Abstract)
103. R. Ostrovsky, A. Wigderson
Nontrivial Zero-Knowledge Implies One--Way Functions
Proceedings of the 2nd ISTCS, pp. 3--17, 1993.
(Abstract)
104. Y. Gil, W. Steiger, A. Wigderson
Geometric Medians
Discrete Math, vol. 108, no. 1, pp. 37--51, 1992.
(Abstract)
105. I. Newman, M. Saks, A. Wigderson
Non--deterministic Communication Complexity with Few Witnesses
JCSS, vol. 49, no. 2, pp. 247-257, 1994.
Also appeared in 7th Structures in Complexity Theory Conference, pp. 275--281, 1992.
(Abstract)
106. A. Wigderson
The Complexity of Graph Connectivity
Proceedings of the 17th Mathematical Foundations of Computer Science conference, Havel and Koubek (eds.), Lecture Notes in Computer Science 629, Springer-Verlag, pp. 112--132, 1992.
(Abstract)
107. Y. Rabinovich, A. Sinclair, A. Wigderson
Quadratic Dynamical Systems
Proceedings of the 33rd FOCS conference, pp. 304--313, 1992.
(Abstract)
108. O. Goldreich, S. Micali, A. Wigderson
Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems
Journal of the ACM, vol. 38, no. 1, pp. 691--729, 1991.
(Abstract)
109. P. Ragde, A. Wigderson
Linear--Size Constant--Depth Polylog-- Threshold Circuits,
Information Processing Letters, vol. 39, no. 3, pp. 143--46, 1991.
(Abstract)
110. L . Babai, L. Fortnow, N. Nisan, A. Wigderson
BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs
Complexity Theory, vol. 3, pp. 307--318, 1993.
Proceedings of the 6th Structures in Complexity Theory Conference, pp. 213--19, July 1991.
(Abstract)
111. A. Wigderson
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Complexity Theory, vol. 1, pp. 311--329, 1991.
(Abstract)
112. R. Raz, A. Wigderson
Super--Logarithmic Depth Lower Bounds via Direct Sum in Communication Complexity
Computational Complexity, vol. 5, pp. 191--204, 1995.
Preliminary version Proceedings of the 6th Structures in Complexity Theory conference, pp. 299--304, July 1991.
(Abstract)
113. P. Gemmell, R. Lipton, R. Rubinfeld, A. Wigderson
Self Testing / Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd STOC, pp. 32--42, May 1991.
(Abstract)
114. N. Nisan, A. Wigderson
Rounds in Communication Complexity Revisited
Proceedings of the 23rd STOC, pp. 419--429, May 1991.
(Abstract)
115. A. Wigderson
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Proceedings of the 6th Structures in Complexity Theory Conference, pp. 172-179, July 1991.
(Abstract)
116. Y. Rabinovich, A. Wigderson
An Analysis of a Simple Genetic Algorithm
Proceedings of the 4th International Conference on Genetic Algorithms, pp. 215-221, July 1991.
(Abstract)
117. L. Lovasz, I. Newman, M. Naor, A. Wigderson
Search Problems in the Decision Tree Model
Proceedings of the 32nd FOCS conference, pp. 576--585, 1991.
(Abstract)
118. F. Fich, A. Wigderson
Towards Understanding Exclusive Reads
SIAM Journal on Computing, vol. 19, no. 4, pp. 718--727, 1990.
(Abstract)
119. A. Wigderson, M. Karchmer
Monotone Circuits for Connectivity require Super-Logarithmic Depth
SIAM Journal on Discrete Mathematics, vol. 3, no. 2, pp. 255--65, 1990.
(Abstract)
120. I. Newman, A. Wigderson
On Read--Once Threshold Formulae and their Randomized Decision Tree Complexity,
Theoretical Computer Science, vol. 107, no. 1, pp. 63--76, 1990.
(Abstract)
121. R. Raz, A. Wigderson
Monotone Circuits for Matching require Linear Depth
Journal of the ACM, vol. 39, pp. 736-744, 1992.
Preliminary version in Proceedings of the 22nd STOC, pp. 287--292, May 1990.
(Abstract)
122. S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson
On the Power of Randomization in On-line Algorithms
Algorithmica, vol. 11, no. 1, pp. 2--14, 1994.
Proceedings of the 22nd STOC, pp. 379--388, May 1990.
(Abstract)
The Tree Model for Hashing: Lower and Upper Bounds
SIAM J. on Computing, vol. 10, pp. 936--955, 1996.
Preliminary version in Proceedings of the 22nd STOC, pp. 244--253, May 1990.
(Abstract)
124. F. Fich, A. Wigderson
Towards Understanding Exclusive Read
Proceedings of 1st Symposium on Parallel Algorithms and Architectures, pp. 718--727, August 1990.
(Abstract)
125. I. Newman, A. Wigderson
On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity
5th Structures in Complexity Theory, pp. 78-89, July 1990.
(Abstract)
126. I. Newman, P. Ragde, A. Wigderson
Perfect Hashing, Graph Entropy and Circuit Complexity
Proceedings of the 5th Structures in Complexity Theory Conference, pp. 91-99, July 1990.
(Abstract)
127. M. Ajtai, A. Wigderson
Deterministic Simulation of Probabilistic Constant-Depth Circuits
Advances in Computing Research - Randomness and Computation, Eds F. Preparata and S. Micali, vol. 5, pp. 199--23, 1989.
(Abstract)
On Computations with Integer Division
Theoretical Informatics and Applications, vol. 23, no. 1, pp. 101--111, 1989.
(Abstract)
129. R. Raz, A. Wigderson
Probabilistic Communication Complexity of Boolean Relations
Proceedings of the 30th FOCS, pp. 562--567, 1989.
(Abstract)
130. A. Cohen, A. Wigderson
Dispersers, Deterministic Amplification and Weak Random Sources
Proceedings of the 30th FOCS, pp. 14--19, 1989.
(Abstract)
131. M. Ben-Or, S. Goldwasser, J. Kilian, A. Wigderson
Efficient Identification Schemes Using Two Prover Interactive Proofs
Advances in Cryptography, CRYPTO 89, LNCS 435, Springer-Verlag, pp. 498--506, 1989.
(Abstract)
132. N. Nisan, A. Wigderson
Undirected Connectivity in <img src="GIFS/log1_5n.gif
" align="absmiddle"> Space
Proceedings of the 30th FOCS conference, pp. 24--29, 1989.
(Abstract)
133. D. Long, A. Wigderson
The Discrete Logarithm Hides O(log n) Bits
SIAM Journal on Computing, vol. 17, no. 2, pp. 363--372, 1988.
(Abstract)
134. F. Fich, P. Ragde, A. Wigderson
Simulations among Concurrent-Write PRAMs
Algorithmica, vol. 3, pp. 43--51, 1988.
(Abstract)
135. F. Fich, P. Ragde, A. Wigderson
Relations between Concurrent-Write Models of Parallel Computation
SIAM Journal on Computing, vol. 17, no. 3, pp. 606--627, 1988.
(Abstract)
A tradeoff between Search and Update Time for the Implicit Dictionary Problem
Theoretical Computer Science, vol. 58, pp. 57--68, 1988.
(Abstract)
137. R. Karp, E. Upfal, A. Wigderson
The Complexity of Parallel Search
Journal of Computer and System Sciences, vol. 36, no. 2, pp. 225--253, 1988.
(Abstract)
138. A. Wigderson
Monotone Connectivity Circuits require Super-logarithmic Depth
Proceedings of the 20th STOC, pp. 539--550, May 1988.
(Abstract)
139. S. Goldwasser, M. Ben-Or, A. Wigderson
Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computing
Proceedings of the 20th STOC, pp. 1--10, May 1988.
(Abstract)
140. S. Goldwasser, J. Kilian, M. Ben-Or, A. Wigderson
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Proceedings of the 20th STOC, pp. 113-131, May 1988.
(Abstract)
On Computations with Integer Division
Proceedings of the STACS conference, pp. 29--37, 1988.
(Abstract)
142. N. Nisan, A. Wigderson
Hardness vs. Randomness
Proceedings of the 29th FOCS, pp. 2--11, 1988.
(Abstract)
A Time-Space Tradeoff for Element Distinctness
SIAM Journal on Computing, vol. 16, no. 1, pp. 97--99, February 1987.
(Abstract)
The Complexity of Parallel Sorting
SIAM Journal on Computing, vol. 16, no. 1, pp. 100--107, 1987.
(Abstract)
Lower Bounds for Parallel Random Access Machines with Unbounded Shared Memory
Advances in Computing Research - Parallel and Distributed Computing, Ed. F. Preparata, vol. 4, pp. 1--6, 1987.
(Abstract)
146. O. Goldreich, S. Micali, A. Wigderson
How to Play any Mental Game
Proceedings of the 19th STOC, pp. 218--229, May 1987.
(Abstract)
147. R. Karp, E. Upfal, A. Wigderson
Constructing a Perfect Matching is in Random NC
Combinatorica, vol. 6, no. 1, pp. 35--48, 1986.
(Abstract)
148. M. Perry, A. Wigderson
Search in a Known Pattern
Journal of Political Economy, vol. 94, no. 1, pp. 225--230, 1986.
(Abstract)
149. E. Upfal, A. Wigderson
How to Share Memory in a Distributed System
Journal of the ACM, vol. 34, no. 1, pp.116--127, 1986.
(Abstract)
150. M. Saks, A. Wigderson
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Proceedings of the 27th FOCS, pp. 29--38, October 1986.
(Abstract)
151. O. Goldreich, S. Micali, A. Wigderson
Proofs that Yield Nothing but their Validity, and a Methodology of Cryptographic Protocol Design
Proceedings of the 27th FOCS, pp. 174--187, October 1986.
(Abstract)
A Trade-off Between Search and Update Time for the Implicit Dictionary Problem
Lecture Notes in Comp. Sci., Springer-Verlag, vol. 226, pp. 50--59, 1986.
(Abstract)
153. N. Megiddo, A. Wigderson
On Play by Means of Computing Machines
Conference on Theoretical Aspects of Reasoning about Knowledge, pp. 259--274, March 1986.
(Abstract)
A Time-Space Tradeoff for Element Distinctness
Proceedings of STACS Conference, Lecture Notes in Comp. Sci., Springer Verlag, vol. 210, pp. 353--358, 1986.
(Abstract)
155. U. Vishkin, A. Wigderson
Depth-Width Trade-offs in Parallel Processing
SIAM Journal on Computing, vol. 14, no. 2, pp. 303--314, May 1985.
(Abstract)
156. R. Karp, E. Upfal, A. Wigderson
Constructing a Perfect Matching is in Random NC
Proceedings of the 17th STOC, pp. 22--32, May 1985.
(Abstract)
One, Two, Three...Infinity: Lower Bounds for Parallel Computation
Proceedings of the 17th STOC, pp. 48--58, May 1985.
(Abstract)
158. R. Karp, E. Upfal, A. Wigderson
Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th STOC, pp. 464--475, May 1985.
(Abstract)
159. M. Ajtai, A. Wigderson
Deterministic Simulation of Probabilistic Constant- Depth Circuits
Proceedings of the 26th FOCS, pp. 11--19, October 1985.
(Abstract)
The Complexity of Parallel Sorting
Proceedings of the 26th FOCS, pp. 532--540, October 1985.
(Abstract)
161. R. Karp, E. Upfal, A. Wigderson
The Complexity of Parallel Computation on Matroids
Proceedings of the 26th FOCS, pp. 541--550, October 1985.
(Abstract)
162. A. Aggarwal, M. Klawe, N. Linial, A. Wigderson
Multilayer Grid Embedding
Proceedings of the 26th FOCS, pp. 186--196, October 1985.
(Abstract)
163. H. Galperin, A. Wigderson
Succinct Representation of Graphs
Information and Control, vol. 56, no. 3, pp. 183--198, March 1984.
(Abstract)
164. U. Vishkin, A. Wigderson
Dynamic Parallel Memories
Information and Control, vol. 56, no. 3, pp. 174--182, March 1984.
(Abstract)
165. R. Karp, A. Wigderson
A Fast Parallel Algorithm for the Maximal Independent Set Problem
Journal of the ACM, vol. 32, no. 4, pp.762--773, October 1985.
Preliminary version in Proceedings of the 16th STOC, pp. 266--272, May 1984.
(Abstract)
166. F. Fich, P. Ragde, A. Wigderson
Relations Between Concurrent-Write Models of Parallel Computation
Conference on the 3rd ACM Symposium on Principles of Distributed Computation, pp. 75--88, 1984.
(Abstract)
167. E. Upfal, A. Wigderson
How to Share Memory in a Distributed System
Proceedings of the 25th FOCS, pp. 171--180, October 1984.
(Abstract)
168. D. Dolev, C. Dwork, N. Pippenger, A. Wigderson
Superconcentrators, Generalizers, and Generalized Connectors with Limited Depth
Proceedings of the 15th STOC, pp. 42--51, May 1983.
(Abstract)
169. D. Long, A. Wigderson
How Discreet is the Discrete Log?
Proceedings of the 15th STOC, pp. 413--420, May 1983.
(Abstract)
170. U. Vishkin, A. Wigderson
Depth-Width Trade-offs in Parallel Computation
Proceedings of the 24th FOCS, pp. 146--153, November 1983.
(Abstract)
171. A. Wigderson
Planarity of Edge Ordered Graphs
Technical Report #307, Department of EECS, Princeton University, December 1982.
(Abstract)
172. A. Wigderson
A New Approximate Graph Coloring Algorithm
Proceedings of the 14th STOC, pp. 325--329, May 1982.
(Abstract)
173. D. Dolev, A. Wigderson
The Security of Multi-Party Protocols in Distributed Systems
Proceedings of the Crypto 82 Conference, pp. 167--176, August 1982.
(Abstract)
174. B. Barak, R. Impagliazzo, A. Wigderson
Extracting randomness using few independent sources
Proceedings of the 45th FOCS 2004, pp. 384--393, 2004.
SICOMP, vol. 36, no. 4, pp. 1095-1118, 2006.
(Abstract)
175. N. Alon, A. Wigderson
Linear Circuits over GF(2)
SIAM Journal on Computing, vol. 19, no. 6 pp. 1064--067, 1990.
(Abstract)
178. P. Ragde, W. Steiger, E. Szemeredi, A. Wigderson
The Parallel Complexity of Element Distinctness is \(\Omega\sqrt{\log n} \)
(Abstract)
179. J. Friedman, A. Wigderson
On the Second Largest Eigenvalue of Hypergraphs
Combinatorica, vol. 15, no. 1, pp. 43--65, 1995.
180. S. Hoory, A. Wigderson
Universal Sequences for Expander Graphs
Information Processing Letters, vol. 46, no. 2, pp. 67--69, 1993.
181. A. Razborov, A. Wigderson
Constructing Small Sets that are Uniform in Arithmetic Progressions
Probability, Combinatorics and Complexity, vol. 2, pp. 513--518, 1993.
182. A. Wigderson
Information Theoretic Reasons for Computational Difficulty
Proceedings of the International Congress of Mathematicians, pp. 1537--1548, August 1990.
183. A. Wigderson
The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
Technical Report #298, Department of EECS, Princeton University, February 1982.
184. R. Karp, M. Saks, A. Wigderson
A Search Problem Related to Branch-and-Bound Procedures
Proceedings of the 27th FOCS, pp. 19--28, October, 1986.
185. N. Linial, A. Wigderson
A Physical interpretation of graph connectivity and its algorithmic applications
Proceedings of the 27th FOCS, pp.39--48, October 1986.
Not All Keys can be Hashed in Constant Time
Proceedings of the 22nd STOC, pp 244--253, May 1990.
188. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
Accepted JACM 2010
Computational Hardness and Explicit Constructions of Error Correcting Codes
44th Allerton Conference on Communication, Control and Computing, September 27-29, 2006