Publication List
An Asymptotic Bound on the Composition Number of Integer Sums of Squares Formulas
Canadian Mathematical Society, vol. 56, no. 1, pp. 70-79, 2013.
Restriction Access
Proceedings of ITCS (Innovations in Theoretical Computer Science) 2012, pp. 19-33, 2012.
Population Recovery and Partial Identification
Foundations of Computer Science (FOCS) 2012, pp. 390-399, 2012.
(Abstract)
Fractional Sylvester-Gallai theorems
Proceedings of the National Academy of Sciences of the United States of America 2012.
5. Z. Dvir, S. Saraf, A. Wigderson
Improved rank bounds for design matrices and a new proof of Kelly's theorem
Electronic Colloquium on Computational Complexity (ECCC) Report TR12-138, 2012.
(Abstract)
Spherical Cubes: Optimal Foams from Computational Hardness Amplification
Communications of the ACM, vol. 55, no. 10, pp. 90-97, 2012.
7. X. Chen, N. Kayal, A. Wigderson
Partial Derivatives in Arithmetic Complexity and Beyond
Foundations and Trends in Theoretical Computer Science (FTTCS), vol. 6, no. 1-2, pp. 1-138, 2011.
(Abstract)
Non-commutative circuits and the sum-of-squares problem
Electronic Colloquium on Computational Complexity (ECCC) Report TR10-021, 2010.
Proceedings of the 42nd ACM symposium on Theory of computing 2010 (STOC), pp. 667-676 , 2010.
(Abstract)
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
Journal of the ACM (JACM), vol. 57, no. 4, pp. 20:1 - 20:52, 2010.
Relationless completeness and separations
Electronic Colloquium on Computational Complexity (ECCC) Report TR10-040, 2010.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), 2010.
(Abstract)
11. T. Kaufman, A. Wigderson
Symmetric LDPC codes and local testing
Proceedings of Innovations in Computer Science (ICS) 2010, pp. 406-421, 2010.
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Proceedings of STOC 2008, pp. 579-588, 2008.
Society for Industrial and Applied Mathematics (SIAM) J. Comput., vol. 39, no. 4, pp. 1637-1665, 2010.
(Abstract)
[ Journal version (pdf) ] [ bibTeX ]
13. B. Applebaum, B. Barak, A. Wigderson
Public Key Cryptography from Different Assumptions
Proceedings of Symposium on Theory of Computing (STOC) 2010, pp. 1-57, 2010.
(Abstract)
14. Z. Dvir, A. Gabizon, A. Wigderson
Extractors and rank extractors for polynomial sources
Proceedings of the Foundations of Computer Science (FOCS) 2007 conference, pp. 52-62, 2007.
Electronic Colloquium on Computational Complexity (ECCC) Report TR07-056, 2007.
Computational Complexity (CC), vol. 18, no. 1, pp. 1-58, 2009.
(Abstract)
New Direct-Product Testers and 2-Query PCPs
Proceedings of Symposium on Theory of Computing (STOC) 2009, pp. 131-140, 2009.
Electronic Colloquium on Computational Complexity (ECCC) Report TR09-090, 2009.
(Abstract)
16. S. Arora, D. Steurer, A. Wigderson
Towards a study of low-complexity graphs
Proceedings of International Colloquium on Automata, Languages and Programming (ICALP) 2009, pp. 119-131.
(Abstract)
Linear systems over composite moduli
Proceedings of Foundations of Computer Science (FOCS) 2009, pp. 43-62, 2009.
(Abstract)
18. Z. Dvir, A. Wigderson
Monotone expanders - constructions and applications
Electronic Colloquium on Computational Complexity (ECCC) Report TR09-135, 2009.
(Abstract)
19. A. Wigderson
Randomness extractors - applications and constructions
Foundations of Software Technology and Theoretical Computer Science FSTTCS), pp. 471-473, 2009.
20. A. Wigderson
The Work of Leslie Valiant
Proceedings of Symposium on Theory of Computing (STOC), pp. 1-2, 2009.
21. E. Viola, A. Wigderson
Norms, XOR lemmas, and lower bounds for \(GF(2)\) polynomials and multiparty protocols
Proceedings of the Conference on Computational Complexity (CCC) 2007, pp. 141-154, 2007.
Theory of Computing, vol. 4, Article 7, pp. 137-168, 2008.
(Abstract)
22. S. Aaronson, A. Wigderson
Algebrization: A New Barrier in Complexity Theory
Proceedings of STOC 2008, pp. 731-740, 2008.
(Abstract)
23. G. Kalai, A. Wigderson
Neighborly Embedded Manifolds
Discrete and Computational Geometry, vol. 40, no. 3, pp. 319-324, 2008.
(Abstract)
24. Z. Dvir, A. Wigderson
Kakeya sets, new mergers and old extractors
Proceedings of the 49th Annual Foundations of Computer Science (FOCS) 2008, vol. 15, pp. 625-633, 2008.
(Abstract)
Spherical Cubes and Rounding in High Dimensions
Proceedings of the 49th Annual Foundations of Computer Science (FOCS) 2008, vol pp. 189-198, 2008.
(Abstract)
26. 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)
27. A. Wigderson, D. Xiao
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
Theory of Computing, vol. 4, no. 1, pp. 53-76, 2008.
28. A. Wigderson
Randomness - A Computational Complexity Perspective
Computer Science – Theory and Applications, vol. 5010, pp. 1-2, 2008.
29. 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)
30. E. Viola, A. Wigderson
One-way multi-party communication lower bound for pointer jumping with applications
Proceedings of the Foundations of Computer Science (FOCS) 2007 Conference, pp. 427-437, 2007.
ECCC Report TR07-079, 2007.
(Abstract)
31. J. Hastad, A. Wigderson
The Randomized Communication Complexity of Set Disjointness
Theory of Computing, vol. 3, no. 1, pp. 211-219, 2007.
Extracting Randomness via Repeated Condensing
Proceedings of the 41st Foundations of Computer Science (FOCS), pp. 22-31, 2000.
SIAM Journal on Computing, vol. 35, no. 5, pp. 1185-1209, 2006.
(Abstract)
33. 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
CCC 2005, pp. 52-66, 2005.
Computational Complexity, vol. 15, no. 4, pp. 391-432, 2006.
(Abstract)
35. E. Rozenman, A. Shalev, A. Wigderson
Iterative construction of Cayley expander graphs
Theory of Computing, vol. 2, no. 1, pp. 91-120, 2006. A shorter version appeared in STOC 2004.
(Abstract)
36. 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 2006, pp. 671-680, 2006.
(Abstract)
37. 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)
38. 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)
39. 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)
41. A. Wigderson
Applications of the Sum-Product Theorem in Finite Fields
IEEE Conference on Computational Complexity, p. 111, 2006.
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
Proceedings of the 46th Symposium on Theory of Computing (STOC) 2005, pp. 1-10, 2005.
(Abstract)
[ Full version (pdf) ] [ Full version (ps) ]
44. A. Wigderson, D. Xiao
A randomness-efficient sampler for matrix-valued functions and applications
46th Annual Symposium of Foundations of Computer Science (FOCS) 2005, pp. 397-406, 2005.
(Abstract)
45. M. Luby, A. Wigderson
Pairwise Independence and Derandomization
Foundations and Trends in Theoretical Computer Science (FTTCS), vol. 1, no. 4, pp. 239-301, 2005.
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Proceedings of IEEE Conference on Computational Complexity, pp. 52-66, 2005.
Pseudorandom Generators in Propositional Proof Complexity
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 34, no. 1, pp. 67-88, 2004. Preliminary version appeared in Symposium on Theory of Computing (STOC) 2000.
(Abstract)
48. 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)
50. E. Rozenman, A. Shalev, A. Wigderson
A new family of Cayley expanders (?)
36th Annual ACM Symposium on Theory of Computing (STOC), 2004, pp. 445-454, 2004.
(Abstract)
51. A. Wigderson
Depth Through Breadth, or Why Should We Attend Talks in Other Areas?
Proceedings of Symposium on Theory of Computing (STOC) 2004, p. 579.
The Quantum Communication Complexity of Sampling
Society for Industrial and Applied Mathematics (Siam) Journal on Computing, vol. 32, pp. 1570-1585, 2003.
(Abstract)
53. 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.
Conference on Computational Complexity, pp. 244-255, 2001. (see also ECCC)
(Abstract)
54. 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)
56. 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, Symposium on Theory of Computing (STOC) 2003, pp. 612-621, 2003.
(Abstract)
58. C-J Lu, O. Reingold, S. Vadhan, A. Wigderson
Extractors: Optimal up to Constant Factors
35th Annual ACM Symposium, Symposium on Theory of Computing (STOC) 2003, pp. 602-611, 2003.
(Abstract)
59. A. Wigderson
Zigzag Products, Expander Constructions, Connections, and Applications
Foundations of Software Technology and Theoretical Computer Science (FTTCS), p. 443, 2003.
On Interactive Proofs With a Laconic Power
Journal of Computational Complexity, vol. 2076, p. 334, 2003.
(Abstract)
61. 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)
62. E. Friedgut, J. Kahn, 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)
63. 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 Symposium on Theory of Computing (STOC), pp. 659-668, 2002.
(Abstract)
65. R. Meshulam, A. Wigderson
Expanders from Symmetric Codes
IEEE Conference on Computational Complexity, p. 0016, 2002.
66. N. Alon, A. Lubotzky, A. Wigderson
Semi-direct product in groups and Zig-zag product in graphs: Connections and applications
Proceedings of the 42nd Foundations of Computer Science (FOCS), pp. 630-637, 2001.
(Abstract)
[ Proceedings version (pdf) ] [ bibTeX ]
On Interactive Proofs with a Laconic Power
Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), pp. 334-345, 2001.
(Abstract)
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time
Journal of Computer Systems and Sciences (JCSS), vol. 65, no. 4, pp. 672-694, 2002.
Conference on Computational Complexity, pp. 2-12, 2001.
(Abstract)
Space Complexity in Propositional Calculus
Society for Industrial and Applied Mathematics (SIAM) Journal of Computing, vol. 31, no. 4, pp. 1184-1211, 2001. Preliminary version appeared in Symposium on Theory of Computing (STOC) 2000.
(Abstract)
70. R. Armoni, A. Ta-Shma, A. Wigderson, S. Zhou
A \((\log n )^{4/3}\) space algorithm for (s,t) connectivity in undirected graphs
Preliminary version in Proceedings of the 29th Symposium on the Theory of Computing (STOC), pp. 230-239, 1997.
Journal of the ACM, vol. 47, no. 2, 294-311, 2000.
(Abstract)
Extractors and Pseudo-random Generators with Optimal Seed Length
Proceedings of the 32nd Symposium on the Theory of Computing (STOC), pp. 1-10, 2000.
(Abstract)
72. O. Goldreich, A. Wigderson
On Pseudorandomness with respect to Deterministic Observers
Proceedings of the satellite workshops of the 27th International Colloquium on Automata, Languages and Programming (ICALP), Carleton Scientific (Proc. in Informatics 8), pp. 77-84, 2000.
(Abstract)
73. O. Reingold, S. Vadhan, A. Wigderson
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Proceedings of the 41st Foundations of Computer Science (FOCS), pp. 3-13, 2000.
(Abstract)
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Proceedings of 30th Symposium on the Theory of Computing (STOC), pp. 644-652, 1998.
Combinatorica, 20, 4, 2000.
(Abstract)
75. 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)
77. 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)
79. 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 Foundations of Computer Science (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)
82. A. Wigderson
De-randomizing BPP: The State of the Art
IEEE Conference on Computational Complexity, pp. 76-77, 1999.
83. A. Wigderson
Probabilistic and Deterministic Approximations of the Permanent
RANDOM / APPROX 1999.
84. H. Buhrman, R. CLeve, A. Wigderson
Quantum vs. Classical Communication and Computation
Proceedings of 30th Symposium on Theory of Computing (STOC), pp. 63-68, 1998.
(Abstract)
Randomness vs. Time: De-randomization under a uniform assumption
Proceedings of the 39th Foundations of Computer Science (FOCS), pp.734-743, 1998.
(Abstract)
86. A. Wigderson
Do probabilistic algorithms outperform deterministic ones?
International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 1443, pp. 212-214, 1998.
87. 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)
88. A. Razborov, A. Wigderson, A. Yao
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and Transversal Calculus
Proceedings of the 29th Symposium on Theory of Computing (STOC), pp. 739-748, 1997.
(Abstract)
89. I. Parnafes, R. Raz, A. Wigderson
Direct Product Results and the GCD Problem, in Old and New Communication Models
Proceedings of the 29th Symposium on Theory of Computing (STOC), pp. 363-372, 1997.
(Abstract)
P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
Proceedings of the 29th Symposium on Theory of Computing (STOC), pp. 220-229, 1997.
(Abstract)
91. O. Goldreich, A. Wigderson
Theory of Computing: A Scientific Perspective
SIGACT News, vol 28, no. 3, pp 100-102, 1997.
92. I. Newman, A. Wigderson
Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy
Society for Industrial and Applied Mathematics (SIAM) Journal on Discrete Mathematics, vol. 8 no. 4, pp. 78-87, 1996.
(Abstract)
93. H. Alt, L. Guibas, K. Mehlhorn, R. Karp, A. Wigderson
A Method for Obtaining Probabilistic Algorithms with Small Tail Probabilities
Algorithmica, vol. 16, no. 4-5, pp. 543-547, 1996.
(Abstract)
94. N. Nisan, A. Wigderson
Lower Bounds on Arithmetic Circuits via Partial Derivatives
Preliminary version in Proceedings of the 36th Foundations of Computer Science ( 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 Symposium on the Theory of Computing (STOC), pp. 603-611, 1996.
(Abstract)
96. R. Sharan, A. Wigderson
A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
Proceedings of Israel Symposium on Theory of Computing and Systems (ISTCS) 1996, pp. 56-65, 1996.
(Abstract)
97. R. Armoni, M. Saks, A. Wigderson, S. Zhou
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
Proceedings of the 37th Foundations of Computer Science (FOCS), pp. 412-421, 1996.
(Abstract)
98. O. Goldreich, A. Wigderson
On the Circuit Complexity of Perfect Hashing
Electronic Colloquium on Computational Complexit (ECCC) Report TR96-041, pp. 26-29, 1996.
The Future of Computational Complexity Theory: Part I
SIGACT News, vol. 27, no. 3, pp. 6-12, 1996.
(Abstract)
100. N. Alon, U. Feige, A. Wigderson, D. Zuckerman
Derandomized Graph Products
Computational Complexity, pp. 60-75, 1995.
(Abstract)
101. L. Lovasz, I. Newman, M. Naor, A. Wigderson
Search Problems in the Decision Tree Model
Society for Industrial and Applied Mathematics (SIAM) Journal on Discrete Math., vol. 8, pp. 119-132, 1995. (Preliminary version appeared at Proceedings of the 32nd Foundations of Computer Science (FOCS) conference, pp. 576-585, 1991.)
(Abstract)
102. 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)
103. P. Miltersen, N. Nisan, S. Safra, A. Wigderson
On Data Structures and Asymmetric Communication Complexity
Journal of Computer Systems and Sciences, (JCSS), vol. 57, no. 1, pp. 37-49, 1998.
Preliminary version appeared in Proceedings of the 27th Symposium on the Theory of Computing (STOC), pp. 103-111, 1995.
(Abstract)
104. N. Nisan, A. Wigderson
On the Complexity of Bilinear Forms
Proceedings of the 27th Symposium on the Theory of Computing (STOC), pp. 723-732, 1995.
(Abstract)
105. I. Damgard, O. Goldreich, A. Wigderson
Honest Verifier vs. Dishonest Verifier in Public Coin Zero-Knowledge Proofs
Advances in Cryptology -- Crypto 1995 (Proceedings), Lecture Note in Computer Science (963), Springer-Verlag, pp. 325-338, 1995.
(Abstract)
106. M. Karchmer, R. Raz, A. Wigderson
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity
Computational Complexity, vol. 5, no. 3-4, pp. 191-204, 1995.
107. A. Wigderson
Computational Pseudo-Randomness
Israel Symposium on Theory of Computing and Systems (ISTCS), pp. 218-219, 1995.
108. O. Goldreich, N. Nisan, A. Wigderson
On Yao's XOR-Lemma
ECCC, TR95-05, 1995.
(Abstract)
[ manuscript (pdf) ] [ manuscript (ps) ]
109. N. Nisan, A. Wigderson
Hardness vs. Randomness
Journal of Computer Systems and Sciences (JCSS), vol. 49, no. 2, pp. 149-167, 1994.
(Abstract)
110. A. Condon, L. Hellerstein, S. Pottle, A. Wigderson
On the Power of Finite State Automata with both Nondeterministic and Probabilistic States
Society for Industrial and Applied Mathematics(SIAM) Journal on Computing, vol. 27, no. 3, pp. 739-762, June 1998.
Proceedings of the 26th Symposium on the Theory of Computing (STOC), pp. 676-685, 1994.
(Abstract)
111. N. Nisan, A. Wigderson
On Rank vs. Communication Complexity
Combinatorica, vol. 15, no. 4, pp. 557-566, 1995.
Also appeared in Proceedings of the 35th Foundations of Computer Science (FOCS), pp. 831-836, 1994.
(Abstract)
112. O. Goldreich, A. Wigderson
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Proceedings of the 26th Symposium on the Theory of Computing (STOC), pp. 574-583, 1994.
(Abstract)
113. R. Impagliazzo, N. Nisan, A. Wigderson
Pseudorandomness for Network Algorithms
Proceedings of the 26th Symposium on the Theory of Computing (STOC), pp. 356-364, 1994.
(Abstract)
114. A. Wigderson
NL/poly \(\subseteq \oplus\) L/poly
Proceedings of the 9th Structures in Complexity Conference, pp. 59-62, July 1994.
(Abstract)
115. M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson
Combinatorial Characterization of Read-Once Formulae
Journal of Discrete Math. vol. 114, pp. 275-282, 1993.
(Abstract)
116. N. Nisan, A. Wigderson
Rounds in Communication Complexity Revisited
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 22, no. 1, pp. 211-219, 1993.
(Abstract)
117. 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)
118. A. Razborov, A. Wigderson
\(n^{\Omega(\log n)}\) Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom
Information Processing Letters (IPL), vol. 45, no. 6, pp. 303-307, 1993.
(Abstract)
119. 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 Symposium on the Theory of Computing (STOC), pp. 245-251, 1993.
(Abstract)
120. 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)
121. M. Karchmer, A. Wigderson
On Span Programs
Proceedings of the 8th Structures in Complexity conference, pp. 102-111, 1993.
(Abstract)
122. M. Karchmer, A. Wigderson
On Characterizing Nondeterministic Circuit Size
Proceedings of the 25th Symposium on the Theory of Computing (STOC), pp. 532-545, 1993.
(Abstract)
123. 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)
124. R. Ostrovsky, A. Wigderson
Nontrivial Zero-Knowledge Implies One--Way Functions
Proceedings of the 2nd ISTCS, pp. 3-17, 1993.
(Abstract)
125. Y. Gil, W. Steiger, A. Wigderson
Geometric Medians
Discrete Math, vol. 108, no. 1, pp. 37-51, 1992.
(Abstract)
126. M. Karchmer, 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)
127. 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)
128. Y. Rabinovich, A. Sinclair, A. Wigderson
Quadratic Dynamical Systems
Proceedings of the 33rd FOCS conference, pp. 304-313, 1992.
(Abstract)
129. 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)
130. P. Ragde, A. Wigderson
Linear--Size Constant--Depth Polylog-- Threshold Circuits,
Information Processing Letters, vol. 39, no. 3, pp. 143-46, 1991.
(Abstract)
131. 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)
132. R. Heiman, A. Wigderson
Randomized vs. Deterministic Decision Tree Complexity for Read--Once Boolean Functions
Complexity Theory, vol. 1, pp. 311-329, 1991.
(Abstract)
133. M. Karchmer, 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)
134. P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, A. Wigderson
Self Testing / Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd STOC, pp. 33-42, May 1991.
(Abstract)
135. N. Nisan, A. Wigderson
Rounds in Communication Complexity Revisited
Proceedings of the 23rd STOC, pp. 419-429, May 1991.
Siam Journal on Computing, vol. 22, no. 1, pp. 211-219
(Abstract)
136. R. Heiman, 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)
137. 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.
Siam Journal on Computing, vol. 8, pp. 119-132, 1995
(Abstract)
138. 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)
139. N. Alon, M. Karchmer, A. Wigderson
Linear Circuits over GF(2)
SIAM Journal on Computing, vol. 19, no. 6 pp. 1064-067, 1990.
(Abstract)
140. F. Fich, A. Wigderson
Towards Understanding Exclusive Reads
SIAM Journal on Computing, vol. 19, no. 4, pp. 718-727, 1990.
(Abstract)
141. M. Karchmer, A. Wigderson
Monotone Circuits for Connectivity require Super-Logarithmic Depth
SIAM Journal on Discrete Mathematics, vol. 3, no. 2, pp. 255-65, 1990.
(Abstract)
142. R. Heiman, 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)
143. R. Raz, A. Wigderson
Monotone Circuits for Matching require Linear Depth
Journal of the ACM, vol. 39, no. 3, pp. 736-744, July 1992.
Preliminary version in Proceedings of the 22nd STOC, pp. 287-292, May 1990.
(Abstract)
144. 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. 25, no. 5, pp. 936-955, October 1996.
Preliminary version in Proceedings of the 22nd STOC, pp. 244-253, May 1990.
(Abstract)
[ Journal version (pdf) ] [ bibTeX ]
146. F. Fich, A. Wigderson
Towards Understanding Exclusive Read
Proceedings of 1st Symposium on Parallel Algorithms and Architectures, pp. 718-727, August 1990.
(Abstract)
147. R. Heiman, 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.
Elsevier, Theoretical Computer Science, 107, pp. 63-76, 1993.
(Abstract)
148. 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)
149. 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.
Proceedings of the 26th FOCS pp. 11-19, October 1985.
(Abstract)
On Computations with Integer Division
Theoretical Informatics and Applications, vol. 23, no. 1, pp. 101-111, 1989.
(Abstract)
151. R. Raz, A. Wigderson
Probabilistic Communication Complexity of Boolean Relations
Proceedings of the 30th FOCS, pp. 562-567, 1989.
(Abstract)
152. A. Cohen, A. Wigderson
Dispersers, Deterministic Amplification and Weak Random Sources
Proceedings of the 30th FOCS, pp. 14-19, 1989.
(Abstract)
153. 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)
154. N. Nisan, E. Szemeredi, A. Wigderson
Undirected Connectivity in $O(log^1.5 n)$ Space
Proceedings of the 30th FOCS conference, pp. 24-29, 1989.
(Abstract)
155. D. Long, A. Wigderson
The Discrete Logarithm Hides O(log n) Bits
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 17, no. 2, pp. 363-372, 1988.
(Abstract)
156. F. Fich, P. Ragde, A. Wigderson
Simulations among Concurrent-Write PRAMs
Algorithmica, vol. 3, pp. 43-51, 1988.
(Abstract)
157. F. Fich, P. Ragde, A. Wigderson
Relations between Concurrent-Write Models of Parallel Computation
Society for Industrial and Applied Mathematics (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)
159. 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)
160. A. Wigderson
Monotone Connectivity Circuits require Super-logarithmic Depth
Proceedings of the 20th Symposium on the Theory of Computing (STOC), pp. 539-550, May 1988.
(Abstract)
161. S. Goldwasser, M. Ben-Or, A. Wigderson
Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computing
Proceedings of the 20th Symposium on the Theory of Computing (STOC), pp. 1-10, May 1988.
(Abstract)
162. S. Goldwasser, J. Kilian, M. Ben-Or, A. Wigderson
Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Proceedings of the 20th Symposium on the Theory of Computing (STOC), pp. 113-131, May 1988.
(Abstract)
On Computations with Integer Division
Proceedings of the STACS conference, pp. 29-37, 1988.
(Abstract)
164. N. Nisan, A. Wigderson
Hardness vs. Randomness
Proceedings of the 29th Foundations of Computer Science (FOCS), pp. 2-11, 1988.
(Abstract)
A Time-Space Tradeoff for Element Distinctness
Society for Industrial and Applied Mathematics (SIAM) Journal on Computing, vol. 16, no. 1, pp. 97-99, February 1987.
(Abstract)
The Complexity of Parallel Sorting
Society for Industrial and Applied Mathematics (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)
168. O. Goldreich, S. Micali, A. Wigderson
How to Play any Mental Game
Proceedings of the 19th Symposium on the Theory of Computing (STOC), pp. 218-229, May 1987.
(Abstract)
169. R. Karp, E. Upfal, A. Wigderson
Constructing a Perfect Matching is in Random NC
Combinatorica, vol. 6, no. 1, pp. 35-48, 1986.
(Abstract)
170. M. Perry, A. Wigderson
Search in a Known Pattern
Journal of Political Economy, vol. 94, no. 1, pp. 225-230, 1986.
(Abstract)
171. E. Upfal, A. Wigderson
How to Share Memory in a Distributed System
Journal of the ACM, vol. 34, no. 1, pp.116-127, 1987.
(Abstract)
172. M. Saks, A. Wigderson
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Proceedings of the 27th Foundations of Computer Science, pp. 29-38, October 1986.
(Abstract)
173. 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)
[ Proceedings version (pdf) ] [ bibTeX ]
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.
Elsevier, vol. 58, issues 1-3, pp. 57-68, June 1988
(Abstract)
175. 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)
177. 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)
178. 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)
180. R. Karp, E. Upfal, A. Wigderson
Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th STOC, pp. 464-475, May 1985.
(Abstract)
181. 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)
183. R. Karp, E. Upfal, A. Wigderson
The Complexity of Parallel Computation on Matroids
Proceedings of the 26th FOCS, pp. 541-550, October 1985.
(Abstract)
185. H. Galperin, A. Wigderson
Succinct Representation of Graphs
Information and Control, vol. 56, no. 3, pp. 183-198, March 1983.
(Abstract)
186. U. Vishkin, A. Wigderson
Dynamic Parallel Memories
Information and Control, vol. 56, no. 3, pp. 174-182, March 1983.
(Abstract)
187. 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)
188. 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)
189. E. Upfal, A. Wigderson
How to Share Memory in a Distributed System
Proceedings of the 25th FOCS, pp. 171-180, October 1984.
(Abstract)
190. 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)
191. D. Long, A. Wigderson
How Discreet is the Discrete Log?
Proceedings of the 15th STOC, pp. 413-420, May 1983.
(Abstract)
192. U. Vishkin, A. Wigderson
Depth-Width Trade-offs in Parallel Computation
Proceedings of the 24th FOCS, pp. 146-153, November 1983.
Siam J. Comput., vol. 14, no. 2, pp. 303-314, May 1985
(Abstract)
193. G. Vijayan, A. Wigderson
Planarity of Edge Ordered Graphs
Technical Report #307, Department of EECS, Princeton University, December 1982.
(Abstract)
194. A. Wigderson
A New Approximate Graph Coloring Algorithm
Proceedings of the 14th STOC, pp. 325-329, May 1982.
(Abstract)
195. D. Dolev, A. Wigderson
The Security of Multi-Party Protocols in Distributed Systems
Proceedings of the Crypto 82 Conference, pp. 167-175, August 1982.
(Abstract)
196. 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)
197. G. Vijayan, A. Wigderson
Rectilinear Graphs and their Embedding
Siam J. Comput., vol. 14, no.2, pp. 355-372, May 1985
198. N. Linial, L. Lovasz, A. Wigderson
Rubber Bands, Convex Embeddings and Graph Connectivity
Combinatorica, vol. 8, no. 1, pp. 91-102, 1988
199. P. Ragde, W. Steiger, E. Szemeredi, A. Wigderson
The Parallel Complexity of Element Distinctness is \(\Omega\sqrt{\log n} \)
Siam J. Comput., vol. 1, no. 3, pp. 399-410, August 1988
(Abstract)
200. J. Friedman, A. Wigderson
On the Second Largest Eigenvalue of Hypergraphs
Combinatorica, vol. 15, no. 1, pp. 43-65, 1995.
201. S. Hoory, A. Wigderson
Universal Sequences for Expander Graphs
Information Processing Letters, vol. 46, no. 2, pp. 67-69, 1993.
202. A. Razborov, E. Szemeredi, A. Wigderson
Constructing Small Sets that are Uniform in Arithmetic Progressions
Probability, Combinatorics and Complexity, vol. 2, pp. 513-518, 1993.
203. A. Wigderson
Information Theoretic Reasons for Computational Difficulty
Proceedings of the International Congress of Mathematicians, pp. 1537-1548, August 1990.
204. A. Wigderson
The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
Technical Report #298, Department of EECS, Princeton University, February 1982.
205. 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.
206. N. Linial, L. Lovasz, 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.
Computational Hardness and Explicit Constructions of Error Correcting Codes
44th Allerton Conference on Communication, Control and Computing, September 27-29, 2006
210. A. Wigderson, V. Guruswami, J. Lee
Expander codes over reals, Euclidean sections, and compressed sensing
Proceedings of the 2009 Allerton Conference
211. R. Ostrovsky, A. Wigderson
One-Way Functions are Essential for Non-Trivial Zero-Knowledge
Proceedings of Israel Symposium on Theory of Computing and Systems (ISTCS) 1993, pp. 3-17, 1993.
212. O. Goldreich, S. Vadhan, A. Wigderson
Simplified Derandomization of BPP Using a Hitting Set Generator
Studies in Complexity and Cryptography, vol. 6650, pp. 59-67, 2011.
Electronic Colloquium on Computational Complexity, Volume 7, 2000.