Avi Wigderson's Home Page

Avi Wigderson's Publication List

(Last updated on August 16, 2010)
  1. P. Hrubes, A. Wigderson, A. Yehudayoff.
    Non-commutative circuits and the sum-of-squares problem
    Proceedings of STOC 2010, pp. 667-676.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  2. R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson.
    Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
    Proceedings of STOC 2008, pp. 579-588.
    SIAM J. Comput., vol. 39, no. 4, pp. 1637-1665, 2010.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  3. B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson.
    Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
    J.ACM 57(4), 2010.
    (Abstract)
    [ Full version (pdf) ] [ Full version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ]
     
  4. P. Hrubes, A. Wigderson, A. Yehudayoff.
    Relationless completeness and separations
    Proceedings of IEEE Computational Complexity Conference 2010, pp. 280-290.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ]
     
  5. T. Kaufman, A. Wigderson.
    Symmetric LDPC codes and local testing
    Proceedings of ICS 2010
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ]
     
  6. S. Arora, D. Steurer, A. Wigderson.
    Towards a study of low-complexity graphs
    Proceedings of ICALP 2009, pp. 119-131.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  7. B. Applebaum, B. Barak, A. Wigderson.
    Public Key Cryptography from Different Assumptions
    Proceedings of STOC 2010, pp. 171-180.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ]
     
  8. R. Impagliazzo, V. Kabanets, A. Wigderson.
    New Direct-Product Testers and 2-Query PCPs
    Proceedings of STOC 09, pp. 131-140, 2009.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  9. Z. Dvir, A. Gabizon, A. Wigderson.
    Extractors and rank extractors for polynomial sources
    Proceedings of the FOCS 07 conference, pp. 52-62, 2007.
    Computational Complexity, vol. 18, no. 1, pp. 1-58, 2009.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  10. Z. Dvir, A. Wigderson.
    Monotone expanders - constructions and applications
    ECCC Report TR09-135, 2009
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ]
     
  11. A. Chattopadhyay, A. Wigderson.
    Linear systems over composite moduli
    Proceedings of FOCS 09, pp. 43-62, 2009.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  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. 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) ]
     
  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) ] [ Journal version (ps) ]
     
  17. 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]
     
  18. V. Guruswami, J. Lee, A. Wigderson.
    Euclidean sections of l1N with sublinear randomness and error-correction over the reals
    APPROX-RANDOM 2008, pp. 444-454.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ]
     
  19. 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]
     
  20. G. Kalai, A. Wigderson.
    Neighborly Embedded Manifolds
    Discrete and Computational Geometry, vo. 40, no. 3, pp. 319-324, 2008.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  21. 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]
     
  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. M. Cheraghchi, Shokrollahi, A. Wigderson.
    Computational Hardness and Explicit Constructions of Error Correcting Codes
    44th Allerton Conference on Communication, Control and Computing, September 27-29, 2006.
    (Abstract)
    [ Proceedings version (pdf) ]
     
  24. 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]
     
  25. 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]
     
  26. 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.
    (Abstract)
    [ Proceedings version(pdf) ] [ Proceedings 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. 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]
     
  29. 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]
     
  30. P. Beame, T. Pitassi, N. Segerlind, A. Wigderson.
    A Strong Direct Product Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
    Proceedings of Conference on Computational Complexity, vol. 15, no. 4, pp. 391-432, 2006.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  31. 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]
     
  32. 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]
     
  33. 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]
     
  34. 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]
     
  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. 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]
     
  37. 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]
     
  38. 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]
     
  39. 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]
     
  40. 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]
     
  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. 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]
     
  43. 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]
     
  44. 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]
     
  45. 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]
     
  46. 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]
     
  47. 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]
     
  48. 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]
     
  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)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  50. 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]
     
  51. 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]
     
  52. 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]
     
  53. 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]
     
  54. 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]
     
  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. 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]
     
  57. 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]
     
  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, pp. 149-169, 2001.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  59. 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]
     
  60. 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 (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  61. 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]
     
  62. 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]
     
  63. 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]
     
  64. A. Shpilka, A. Wigderson.
    Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
    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]
     
  65. 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, vol. 20, no. 4, 2000.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  66. 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]
     
  67. 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]
     
  68. 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]
     
  69. 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]
     
  70. 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]
     
  71. 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]
     
  72. 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]
     
  73. 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]
     
  74. 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]
     
  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, no. 3, pp. 217-234, 1996.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  76. 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]
     
  77. 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]
     
  78. 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]
     
  79. 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]
     
  80. O. Goldreich, A. Wigderson.
    On the Circuit Complexity of Perfect Hashing
    ECCC Report TR96-041
     
  81. 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]
     
  82. 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]
     
  83. 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]
     
  84. 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]
     
  85. 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]
     
  86. 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]
     
  87. 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]
     
  88. 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]
     
  89. 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]
     
  90. O. Goldreich, N. Nisan, A. Wigderson.
    On Yao's XOR-Lemma
    ECCC, TR95-05, 1995.
    (Abstract)
    [ manuscript (pdf) ] [ manuscript (ps) ]
     
  91. 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) ]
     
  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. 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]
     
  94. 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]
     
  95. 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]
     
  96. 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]
     
  97. 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]
     
  98. 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]
     
  99. 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]
     
  100. 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]
     
  101. 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]
     
  102. 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]
     
  103. 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]
     
  104. 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]
     
  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. 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]
     
  107. 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]
     
  108. 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]
     
  109. 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]
     
  110. 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]
     
  111. 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]
     
  112. 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]
     
  113. 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]
     
  114. 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]
     
  115. 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]
     
  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. 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]
     
  118. 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]
     
  119. 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]
     
  120. 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]
     
  121. 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]
     
  122. 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]
     
  123. 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]
     
  124. 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]
     
  125. 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]
     
  126. 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]
     
  127. 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]
     
  128. 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]
     
  129. 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]
     
  130. 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]
     
  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. 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]
     
  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. 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]
     
  135. 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]
     
  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. 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]
     
  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. 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]
     
  140. 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]
     
  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. 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]
     
  143. 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]
     
  144. 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]
     
  145. 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]
     
  146. 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]
     
  147. 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]
     
  148. 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]
     
  149. 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]
     
  150. 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]
     
  151. 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]
     
  152. 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) ]
     
  153. 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]
     
  154. 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]
     
  155. 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]
     
  156. 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]
     
  157. 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]
     
  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. 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]
     
  160. 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]
     
  161. 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]
     
  162. 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]
     
  163. 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]
     
  164. 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]
     
  165. 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]
     
  166. 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]
     
  167. 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]
     
  168. 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]
     
  169. 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]
     
  170. 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]
     
  171. 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]
     
  172. 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]
     
  173. 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]
     
  174. 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]
     
  175. 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]
     
  176. 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]
     
  177. 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]
     
  178. 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]
     
  179. G. 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]
     
  180. 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]
     
  181. 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]
     
  182. 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]
     
  183. 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]