Avi Wigderson's Home Page

Avi Wigderson's Publication List

(Last updated on March 11, 2010)
  1. P. Hrubes, A. Wigderson, A. Yehudayoff.
    Non-commutative circuits and the sum-of-squares problem
    ECCC Report TR10-021, 2010
    Accepted for STOC 2010
     
  2. P. Hrubes, A. Wigderson, A. Yehudayoff.
    Relationless completeness and separations
    ECCC Report TR10-040, 2010
    Accepted for CCC 2010
    [ Journal version (pdf) ]
     
  3. B. Barak, G. Kindler, Shaltiel, B. Sudakov, A. Wigderson.
    Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
    Accepted JACM
     
  4. R. Impagliazzo, V. Kabanets, A. Wigderson.
    New Direct-Product Testers and 2-Query PCPs
    Proceedings of STOC 09
    ECCC Report TR09-090, 2009
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  5. S. Arora, D. Steurer, A. Wigderson.
    Towards a study of low-complexity graphs
    Proceedings of ICALP 2009
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  6. A. Chattopadhyay, A. Wigderson.
    Linear systems over composite moduli
    Proceedings of FOCS 09
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  7. Z. Dvir, A. Wigderson.
    Monotone expanders - constructions and applications
    ECCC Report TR09-135, 2009
    (Abstract)
     
  8. R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson.
    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)
    [ Journal version (pdf) ] [bibTeX entry]
     
  9. B. Applebaum, B. Barak, A. Wigderson.
    Public Key Cryptography from Different Assumptions
    Proceedings of STOC 2010
    [ Draft of final version (pdf) ]
     
  10. G. Kindler, A. Rao, Ryan O'Donnell, A. Wigderson.
    Spherical Cubes and Rounding in High Dimensions
    Proceedings of the 49th Annual FOCS08, pp. 189-198, 2008.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  11. V. Guruswami, J. Lee, A. Wigderson.
    Euclidean sections of l1N with sublinear randomness and error-correction over the reals
    RANDOM '08
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  12. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  13. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  14. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  15. S. Aaronson, A. Wigderson.
    Algebrization: A New Barrier in Complexity Theory
    Proceedings of STOC 08, pp. 731-740, 2008.
    (Abstract)
    [ Accepted to Theory of Computation (pdf) ] [ Accepted to Theory of Computation (ps) ] [bibTeX entry]
     
  16. Z. Dvir, A. Wigderson.
    Kakeya sets, new mergers and old extractors
    Proceedings of the 49th Annual FOCS08, pp. 625-633, 2008.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ]
     
  17. 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)
    [ Full version (pdf) ] [ Full version (ps) ] [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Final version (pdf) ] [ Final version (ps) ] [bibTeX entry]
     
  18. 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)
    [ Proceedings version(pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  19. G. Kalai, A. Wigderson.
    Neighborly Embedded Manifolds
    Discrete and Computational Geometry, 2008.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  20. 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
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Full version (pdf) ] [ Full version (ps) ] [bibTeX entry]
     
  21. R. Impagliazzo, R. Shaltiel, A. Wigderson.
    Reducing the seed length in the Nisan-Wigderson generator
    Combinatorica, vol. 26, no. 6, pp. 647-681, 2006.
    (Abstract)
    [ Full version (pdf) ] [ Full version (ps) ] [bibTeX entry]
     
  22. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  23. E. Rozenman, A. Shalev, 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)
    [ Final version (pdf) ] [ Final version (ps) ] [bibTeX entry]
     
  24. 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)
    [ Proceedings version(pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  25. J. Hastad, A. Wigderson.
    Simple Analysis of Graph Tests
    Conference on Computational Complexity, pp. 244-255, 2001. (see also ECCC)
    (Abstract)
    [ Draft of final version May 11, 2001 (pdf) ] [ Draft of final version May 11, 2001 (ps) ] [bibTeX entry]
     
  26. O. Reingold, R. Shaltiel, A. Wigderson.
    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)
    [ Final version (pdf) ] [ Final version (ps) ] [bibTeX entry]
     
  27. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  28. P. Beame, T. Pitassi, N. Segerlind, A. Wigderson.
    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)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  29. 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)
    [ Final journal version (pdf) ] [ Final journal version (ps) ] [bibTeX entry]
     
  30. R. Meshulam, A. Wigderson.
    Expanders in Group Algebras
    Combinatorica, vol. 24, no. 4, pp 659-680, 2004.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  31. E. Ben-Sasson, R. Impagliazzo, A. Wigderson.
    Near Optimal Separation of Tree-like and General Resolution
    Combinatorica, vol. 24, no. 4, pp. 585-604, 2004.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  32. E. Rozenman, A. Shalev, A. Wigderson.
    A new family of Cayley expanders (?)
    36th Annual ACM Symposium, STOC 2004, pp. 445-454, 2004.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  33. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson.
    Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
    Proceedings of the 46th STOC 05, pp. 1-10, 2005.
    (Abstract)
    [ Full version (pdf) ] [ Full version (ps) ] [bibTeX entry]
     
  34. M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson.
    Pseudorandom Generators in Propositional Proof Complexity
    SIAM Journal on Computing, vol. 34, no. 1, pp. 67-88, 2004. Preliminary version appeared in STOC2000.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  35. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  36. A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson.
    The Quantum Communication Complexity of Sampling
    SIAM Journal on Computing, vol. 32, no. 6, pp 1570-1585, 2003.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  37. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  38. B. Barak, R. Shaltiel, A. Wigderson.
    Computational Analogues of Entropy
    11th International Conference on Random Structures and Algorithms, pp. 200-215, August 2003.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  39. E. Ben-Sasson, M. Sudan, S. Vadhan, A. Wigderson.
    Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets
    35th Annual ACM Symposium, STOC 2003, pp. 612-621, 2003.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  40. O. Goldreich, S. Vadhan, A. Wigderson.
    On Interactive Proofs With a Laconic Power
    Journal of Computational Complexity, vol. 2076, p. 334, 2003.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  42. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  43. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  44. R. Impagliazzo, V. Kabanets, A. Wigderson.
    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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  45. 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)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  46. M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson.
    Randomness Conductors and Constant-Degree Expansion Beyond the Degree /2 Barrier
    Proceedings of the 34th STOC, pp. 659-668, 2002.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  47. 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)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  48. A. Wigderson.
    On the Work of Madhu Sudan.no 1, pp. 45-50, 2003.
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  49. M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson.
    Space Complexity in Propositional Calculus
    SIAM Journal of Computing, vol. 31, no. 4, pp. 1184-1211, 2001. Preliminary version appeared in STOC 2000.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  50. O. Goldreich, S. Vadhan, A. Wigderson.
    On Interactive Proofs with a Laconic Power
    Proceedings of the 28th ICALP, pp. 334-345, 2001.
    (Abstract)
    [ Draft of final version September 5, 2001 (pdf) ] [ Draft of final version September 5, 2001 (ps) ] [bibTeX entry]
     
  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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  52. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  53. 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 STOC, pp. 230-239, 1997.
    J. ACM, vol. 47, no. 2, 294-311, 2000.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  54. R. Impagliazzo, R. Shaltiel, A. Wigderson.
    Extractors and Pseudo-random Generators with Optimal Seed Length
    Proceedings of the 32nd STOC, pp. 1-10, 2000.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  55. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  56. Y. Rabinovich, A. Wigderson.
    Techniques for bounding the convergence rate of genetic algorithms.
    Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.
    (Abstract)
    [ Journal version (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  57. 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)
    [ Journal version (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  58. E. Ben-Sasson, A. Wigderson.
    Short Proofs are Narrow - Resolution made Simple
    Proceedings of the 31th STOC, pp. 517-526, 1999.
    Journal of the ACM, vol. 48, no. 2, 2001.
    ECCC Report TR99-022, 1999.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  59. R. Impagliazzo, R. Shaltiel, A. Wigderson.
    Near-optimal Conversion of Hardness into Pseudo-randomness
    Proceedings of the 40th FOCS, pp. 181-190, 1999.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  60. L . Babai, A. Gal, A. Wigderson.
    Superpolynomial lower bounds for monotone span programs.
    Combinatorica, vol. 19, no. 3, 301-319, 1999.
    (Abstract)
    [ Journal version (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  61. O. Goldreich, A. Wigderson.
    Improved derandomization of BPP using a hitting set generator
    Proceedings of the RAMDOM 99 Conference, pp. 131-137, 1999.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  62. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  63. Z. Bar-Yossef, O. Goldreich, A. Wigderson.
    Deterministic Amplification of Space-Bounded Probabilistic Algorithms
    Proceedings of the 14th Conference on Computational Complexity, pp. 188-199, 1999.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  64. R. Impagliazzo, A. Wigderson.
    Randomness vs. Time: De-randomization under a uniform assumption
    Proceedings of the 39th FOCS, pp.734-743, 1998.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  65. H. Buhrman, R. CLeve, A. Wigderson.
    Quantum vs. Classical Communication and Computation
    Proceedings of 30th STOC, pp. 63-68, 1998.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  66. A. Condon, L. Hellerstein, S. Pottle, A. Wigderson.
    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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  67. A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson.
    The Quantum Communication Complexity of Sampling
    Siam Journal on Computing, vol. 32, pp. 1570-1585, 2003.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  68. N. Linial, A. Samorodnitsky, A. Wigderson.
    A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
    Proceedings of 30th STOC, pp. 644-652, 1998.
    Combinatorica, 20, 4, 2000.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  69. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  70. R. Impagliazzo, A. Wigderson.
    P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
    Proceedings of the 29th STOC, pp. 220-229, 1997.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  72. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  73. I. Parnafes, 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  74. L . Babai, A. Gal, J. Kollar, L. Ronyai, T. Szabo, A. Wigderson.
    Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
    Proceedings of 28th STOC, pp. 603-611, 1996.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  75. 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, pp. 217-234, 1996.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  76. R. Sharan, A. Wigderson.
    A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
    Proceedings of ISTCS 96, pp. 56-65, 1996.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  77. R. Armoni, M. Saks, A. Wigderson, S. Zhou.
    Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
    Proceedings of the 37th FOCS, pp. 412-421, 1996.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  78. O. Goldreich, A. Wigderson.
    On the Circuit Complexity of Perfect Hashing
    ECCC Report TR96-041
     
  79. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  80. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  81. Y. Gil, F. Meyer auf der Heide, A. Wigderson.
    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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  82. H. Alt, 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  83. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  84. J. Friedman, A. Wigderson.
    On the Second Largest Eigenvalue of Hypergraphs
    Combinatorica, vol. 15, no. 1, pp. 43-65, 1995.
    [ Journal version (pdf) ] [ Journal version (ps) ]
     
  85. I. Damgard, O. Goldreich, Okamoto , A. Wigderson.
    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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  86. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  87. N. Nisan, A. Wigderson.
    On the Complexity of Bilinear Forms
    Proceedings of the 27th STOC, pp. 723-732, 1995.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  88. N. Alon, U. Feige, A. Wigderson, D. Zuckerman.
    Derandomized Graph Products
    Computational Complexity, pp. 60-75, 1995.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  89. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  90. O. Goldreich, N. Nisan, A. Wigderson.
    On Yao's XOR-Lemma
    (Abstract)
    [ manuscript (pdf) ] [ manuscript (ps) ]
     
  91. A. Wigderson.
    NL/poly L/poly
    Proceedings of the 9th Structures in Complexity Conference, pp. 59-62, July 1994.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  92. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  93. R. Impagliazzo, N. Nisan, A. Wigderson.
    Pseudorandomness for Network Algorithms
    Proceedings of the 26th STOC, pp. 356-364, 1994.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  94. N. Nisan, A. Wigderson.
    Hardness vs. Randomness
    Journal of Computer Systems and Sciences, vol. 49, no. 2, pp. 149-167, 1994.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  95. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  96. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  97. N. Nisan, A. Wigderson.
    Rounds in Communication Complexity Revisited
    SIAM Journal on Computing, vol. 22, no. 1, pp. 211-219, 1993.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  98. R. Ostrovsky, A. Wigderson.
    Nontrivial Zero-Knowledge Implies One-Way Functions
    Proceedings of the 2nd ISTCS, pp. 3-17, 1993.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  99. M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson.
    Combinatorial Characterization of Read-Once Formulae
    J. Discrete Math. vol. 114, pp. 275-282, 1993.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  100. M. Karchmer, A. Wigderson.
    On Span Programs
    Proceedings of the 8th Structures in Complexity conference, pp. 102-111, 1993.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  101. 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)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  102. 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)
    [ Journal version (pdf ] [ Journal version (ps ] [bibTeX entry]
     
  103. 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.
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  104. A. Razborov, A. Wigderson.
    Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom
    IPL, vol. 45, pp. 303-307, 1993.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  105. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  106. S. Hoory, A. Wigderson.
    Universal Sequences for Expander Graphs
    Information Processing Letters, vol. 46, no. 2, pp. 67-69, 1993.
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  107. M. Karchmer, A. Wigderson.
    On Characterizing Nondeterministic Circuit Size
    Proceedings of the 25th STOC, pp. 532-545, 1993.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  108. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  109. Y. Gil, W. Steiger, A. Wigderson.
    Geometric Medians
    Discrete Math, vol. 108, no. 1, pp. 37-51, 1992.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  110. Y. Rabinovich, A. Sinclair, A. Wigderson.
    Quadratic Dynamical Systems
    Proceedings of the 33rd FOCS conference, pp. 304-313, 1992.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  111. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  112. P. Ragde, A. Wigderson.
    Linear-Size Constant-Depth Polylog- Threshold Circuits,
    Information Processing Letters, vol. 39, no. 3, pp. 143-46, 1991.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  113. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  114. P. Gemmell, R. Lipton, R. Rubinfeld, Sudan , A. Wigderson.
    Self Testing / Correcting for Polynomials and for Approximate Functions
    Proceedings of the 23rd STOC, pp. 32-42, May 1991.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  115. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  116. N. Nisan, A. Wigderson.
    Rounds in Communication Complexity Revisited
    Proceedings of the 23rd STOC, pp. 419-429, May 1991.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  117. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  118. R. Heiman, A. Wigderson.
    Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions
    Complexity Theory, vol. 1, pp. 311-329, 1991.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  119. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  120. 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.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  121. F. Fich, A. Wigderson.
    Towards Understanding Exclusive Reads
    SIAM Journal on Computing, vol. 19, no. 4, pp. 718-727, 1990.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  122. F. Fich, A. Wigderson.
    Towards Understanding Exclusive Read
    Proceedings of 1st Symposium on Parallel Algorithms and Architectures, pp. 718-727, August 1990.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  123. A. Wigderson.
    Information Theoretic Reasons for Computational Difficulty
    Proceedings of the International Congress of Mathematicians, pp. 1537-1548, August 1990.
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  124. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  125. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  126. Y. Gil, F. Meyer auf der Heide, A. Wigderson.
    Not All Keys can be Hashed in Constant Time
    Proceedings of the 22nd STOC, pp 244-253, May 1990.
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  127. N. Alon, M. Karchmer, A. Wigderson.
    Linear Circuits over GF(2)
    SIAM Journal on Computing, vol. 19, no. 6 pp. 1064-067, 1990.
    (Abstract)
    [ Journal version (pdf) ] [ Journal Version (ps) ] [bibTeX entry]
     
  128. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  129. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  130. 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)
    [ Journal version (pdf) ] [ Journal version (ps ] [bibTeX entry]
     
  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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  132. A. Cohen, A. Wigderson.
    Dispersers, Deterministic Amplification and Weak Random Sources
    Proceedings of the 30th FOCS, pp. 14-19, 1989.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  133. R. Raz, A. Wigderson.
    Probabilistic Communication Complexity of Boolean Relations
    Proceedings of the 30th FOCS, pp. 562-567, 1989.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  134. N. Nisan, E. Szemeredi, A. Wigderson.
    Undirected Connectivity in Space
    Proceedings of the 30th FOCS conference, pp. 24-29, 1989.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  135. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  136. P. Ragde, W. Steiger, E. Szemeredi, A. Wigderson.
    The Parallel Complexity of Element Distinctness is
    SIAM Journal on Discrete Mathematics, vol. 1, no. 3, pp. 399-410, 1988.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  137. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  138. F. Fich, P. Ragde, A. Wigderson.
    Simulations among Concurrent-Write PRAMs
    Algorithmica, vol. 3, pp. 43-51, 1988.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  139. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  140. A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
    A tradeoff between Search and Update Time for the Implicit Dictionary Problem
    Theoretical Computer Science, vol. 58, pp. 57-68, 1988.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  141. N. Linial, L. Lovasz, A. Wigderson.
    Rubber Bands, Convex Embeddings and Graph Connectivity
    Combinatorica, vol. 8, pp.91-102, 1988.
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  142. A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
    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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  143. B. Yust, F. Meyer auf der Heide, A. Wigderson.
    On Computations with Integer Division
    Proceedings of the STACS conference, pp. 29-37, 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  144. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  145. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  146. M. Karchmer, A. Wigderson.
    Monotone Connectivity Circuits require Super-logarithmic Depth
    Proceedings of the 20th STOC, pp. 539-550, May 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  147. N. Nisan, A. Wigderson.
    Hardness vs. Randomness
    Proceedings of the 29th FOCS, pp. 2-11, 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  148. A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
    A Time-Space Tradeoff for Element Distinctness
    SIAM Journal on Computing, vol. 16, no. 1, pp. 97-99, February 1987.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  149. F. Fich, F. Meyer auf der Heide, A. Wigderson.
    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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  150. F. Meyer auf der Heide, A. Wigderson.
    The Complexity of Parallel Sorting
    SIAM Journal on Computing, vol. 16, no. 1, pp. 100-107, 1987.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  151. O. Goldreich, S. Micali, A. Wigderson.
    How to Play any Mental Game
    Proceedings of the 19th STOC, pp. 218-229, May 1987.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  152. 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) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  153. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  154. R. Karp, E. Upfal, A. Wigderson.
    Constructing a Perfect Matching is in Random NC
    Combinatorica, vol. 6, no. 1, pp. 35-48, 1986.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  155. 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.
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  156. 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.
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  157. A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
    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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  158. M. Perry, A. Wigderson.
    Search in a Known Pattern
    Journal of Political Economy, vol. 94, no. 1, pp. 225-230, 1986.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  159. 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)
    [ Proceedings Version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  160. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  161. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  162. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  163. 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)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  164. M. Ajtai, A. Wigderson.
    Deterministic Simulation of Probabilistic Constant- Depth Circuits
    Proceedings of the 26th FOCS, pp. 11-19, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  165. Vijayan, A. Wigderson.
    Rectilinear Graphs and their Embedding
    SIAM Journal on Computing, vol. 14, no. 2, pp. 355-372, May 1985.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  166. R. Karp, E. Upfal, A. Wigderson.
    The Complexity of Parallel Computation on Matroids
    Proceedings of the 26th FOCS, pp. 541-550, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  167. F. Fich, F. Meyer auf der Heide, P. Ragde, A. Wigderson.
    One, Two, Three...Infinity: Lower Bounds for Parallel Computation
    Proceedings of the 17th STOC, pp. 48-58, May 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  168. F. Meyer auf der Heide, A. Wigderson.
    The Complexity of Parallel Sorting
    Proceedings of the 26th FOCS, pp. 532-540, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  169. R. Karp, E. Upfal, A. Wigderson.
    Are Search and Decision Problems Computationally Equivalent?
    Proceedings of the 17th STOC, pp. 464-475, May 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  170. A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, A. Wigderson.
    Multilayer Grid Embedding
    Proceedings of the 26th FOCS, pp. 186-196, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  171. H. Galperin, A. Wigderson.
    Succinct Representation of Graphs
    Information and Control, vol. 56, no. 3, pp. 183-198, March 1984.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  172. U. Vishkin, A. Wigderson.
    Dynamic Parallel Memories
    Information and Control, vol. 56, no. 3, pp. 174-182, March 1984.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  173. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  174. E. Upfal, A. Wigderson.
    How to Share Memory in a Distributed System
    Proceedings of the 25th FOCS, pp. 171-180, October 1984.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  175. D. Long, A. Wigderson.
    How Discreet is the Discrete Log?
    Proceedings of the 15th STOC, pp. 413-420, May 1983.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  176. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  177. U. Vishkin, A. Wigderson.
    Depth-Width Trade-offs in Parallel Computation
    Proceedings of the 24th FOCS, pp. 146-153, November 1983.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  178. Vijayan, A. Wigderson.
    Planarity of Edge Ordered Graphs
    Technical Report #307, Department of EECS, Princeton University, December 1982.
    (Abstract)
    [ Technical report (pdf) ] [ Technical report (ps) ] [bibTeX entry]
     
  179. 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)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  180. A. Wigderson.
    A New Approximate Graph Coloring Algorithm
    Proceedings of the 14th STOC, pp. 325-329, May 1982.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  181. A. Wigderson.
    The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
    Technical Report #298, Department of EECS, Princeton University, February 1982.
    [ Technical Report 298 (pdf) ] [bibTeX entry]
     
  182. B. Yust, F. Meyer auf der Heide, A. Wigderson.
    On Computations with Integer Division
    Theoretical Informatics and Applications, vol. 23, no. 1, pp. 101-111, 1989.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]