Avi Wigderson's Home Page

Avi Wigderson's Publication List

(Last updated on July 23, 2008)
  1. S. Aaronson, A. Wigderson.
    Algebrization: A New Barrier in Complexity Theory
    Proceedings of STOC 08, pp. 731-740, 2008.
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [bibTeX entry]
     
  2. Z. Dvir, A. Wigderson.
    Kakeya sets, new mergers and old extractors
    FOCS08
    (Abstract)
    [ Draft of final version (pdf) ] [ Draft of final version (ps) ] [ Proceedings version (pdf) ]
     
  3. R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson.
    Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
    Proceedings of STOC 08, pp. 579-588, 2008.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  4. G. Kindler, A. Rao, Ryan O'Donnell, A. Wigderson.
    Spherical Cubes and Rounding in High Dimensions
    FOCS08
     
  5. 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.
    (Abstract)
    [ Full version (pdf) ] [ Full version (ps) ] [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  6. A. Wigderson.
    P, NP and Mathematics - a computational complexity perspective
    Proceedings of the ICM 06 (Madrid), Vol. I, EMS Publishing House, Zurich, pp. 665-712, 2007.
    (Abstract)
    [ Proceedings version(ps) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  7. Z. Dvir, A. Gabizon, A. Wigderson.
    Extractors and rank extractors for polynomial sources
    Proceedings of the FOCS 07 conference, pp. 52-62, 2007.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [ Full version (pdf) ] [ Full version (ps) ] [bibTeX entry]
     
  8. 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.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (ps) ] [bibTeX entry]
     
  9. G. Kalai, A. Wigderson.
    Neighborly Embedded Manifolds
    Discrete and Computational Geometry, 2008.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  10. 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(ps) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  11. A. Wigderson, D. Xiao.
    Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
    Electronic Colloquium on Computational Complexity, Report TR06-105, ISSN 1433-8092, 13th Year, 105th Report.
    (Abstract)
    [ Report version (ps) ] [ Report 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 (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  13. R. Impagliazzo, R. Shaltiel, A. Wigderson.
    Reducing the seed length in the Nisan-Wigderson generator
    Combinatorica, 26(6), pp. 647-681, 2006.
    (Abstract)
    [ Full version (pdf) ] [ Full version (ps) ] [bibTeX entry]
     
  14. 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) ] [bibTeX entry]
     
  15. E. Rozenman, A. Shalev, A. Wigderson.
    Iterative construction of Cayley expander graphs
    Theory of Computing, 2/5, pp 91-120, 2006. A shorter version appeared in STOC 04.
    (Abstract)
    [ Final version (ps) ] [ Final version (pdf) ] [bibTeX entry]
     
  16. O. Reingold, R. Shaltiel, A. Wigderson.
    Extracting Randomness via Repeated Condensing
    Proc. of the 41st FOCS, pp. 22-31, 2000
    SIAM Journal on Computing, Vol 35, Number 5, pp. 1185-1209, 2006.
    (Abstract)
    [ Final Version (ps) ] [ Final version ] [bibTeX entry]
     
  17. J. Hastad, A. Wigderson.
    Simple Analysis of Graph Tests
    Conference on Computational Complexity, pp. 244-255, 2001. (see also ECCC)
    (Abstract)
    [ Draft of full version May 11, 2001 (postscript) ] [ Draft of full version May 11, 2001 (pdf) ] [bibTeX entry]
     
  18. 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 (ps) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  19. 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 (ps) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  20. E. Ben-Sasson, R. Impagliazzo, A. Wigderson.
    Near Optimal Separation of Tree-like and General Resolution
    Combinatorica, Vol 24, Issue 4, pp 585-604, 2004.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  21. R. Meshulam, A. Wigderson.
    Expanders in Group Algebras
    Combinatorica, Vol 24, Issue 4, pp 659-680, 2004.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  22. B. Barak, R. Impagliazzo, A. Wigderson.
    Extracting randomness using few independent sources
    Proc of the 45th FOCS 2004, pp 384-393, 2004.
    SICOMP, Vol 36, No 4, pp 1095-1118, 2006.
    (Abstract)
    [ Final journal version (ps) ] [ Final journal version (pdf) ] [bibTeX entry]
     
  23. 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)
    [ prelimnary full version (ps) ] [ preliminary full version (pdf) ] [bibTeX entry]
     
  24. 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 (postscript) ] [bibTeX entry]
     
  25. M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson.
    Pseudorandom Generators in Propositional Proof Complexity
    SIAM Journal on Computing, Vol 34, Number 1, pp. 67-88, 2004. Preliminary version appeared in STOC2000.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  26. 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 (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  27. 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 (postscript) ] [bibTeX entry]
     
  28. 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 (postscript) ] [bibTeX entry]
     
  29. 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 (postscript) ] [bibTeX entry]
     
  30. B. Barak, R. Shaltiel, A. Wigderson.
    Computational Analogues of Entropy
    11th International Conference on Random Structures and Algorithms August 2003, pp 200-215, 2003.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  31. 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, pgs 612-621, 2003.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  32. C-J Lu, O. Reingold, S. Vadhan, A. Wigderson.
    Extractors: Optimal up to Constant Factors
    35th Annual ACM Symposium, STOC 2003, pgs 602-611, 2003.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  33. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  34. M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson.
    Randomness Conductors and Constant-Degree Expansion Beyond the Degree /2 Barrier
    Proc. of the 34th STOC, pp. 659-668, 2002
    (Abstract)
    [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  35. A. Wigderson.
    On the Work of Madhu Sudan
    Notices of the AMS, 50, no 1, pp. 45-50, 2003
    [ Draft of final version (postscript) ] [bibTeX entry]
     
  36. 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 (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  37. 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]
     
  38. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  39. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  40. O. Goldreich, S. Vadhan, A. Wigderson.
    On Interactive Proofs with a Laconic Power
    Proc. of the 28th ICALP, pp. 334-345, 2001.
    (Abstract)
    [ Draft of full version September 5, 2001 (pdf) ] [ Draft of full version September 5, 2001 (ps) ] [bibTeX entry]
     
  41. M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson.
    Space Complexity in Propositional Calculus
    SIAM Journal of Computing, 31, No. 4, pp. 1184-1211, 2001.Preliminary version appeared in STOC2000.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  42. N. Alon, A. Lubotzky, A. Wigderson.
    Semi-direct product in groups and Zig-zag product in graphs: Connections and applications
    Proc. of the 42nd FOCS, pp. 630-637, 2001.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  43. 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 Proc. of the 29th STOC pp. 230-239, 1997.
    J. ACM Vol. 47, No. 2, 294-311, 2000.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  44. 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 (postscript) ] [bibTeX entry]
     
  45. R. Impagliazzo, R. Shaltiel, A. Wigderson.
    Extractors and Pseudo-random Generators with Optimal Seed Length
    Proc. of the 32nd STOC, pp. 1-10, 2000.
    (Abstract)
    [ Journal version (ps) ] [ Journal version (pdf) ] [bibTeX entry]
     
  46. O. Reingold, S. Vadhan, A. Wigderson.
    Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
    Proc. of the 41st FOCS, pp. 3-13, 2000.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  47. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  48. E. Ben-Sasson, A. Wigderson.
    Short Proofs are Narrow - Resolution made Simple
    Proc. of the 31th STOC, pp. 517-526, 1999.
    Journal of the ACM, Vol. 48, No. 2, 2001.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  49. 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 Proc. of the 14th Conference on Computational Complexity, pp. 87-97, 1999.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  50. Z. Bar-Yossef, O. Goldreich, A. Wigderson.
    Deterministic Amplification of Space-Bounded Probabilistic Algorithms
    Proc. of the 14th Conference on Computational Complexity, pp. 188-199, 1999.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  51. 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 Proc. of the 25th STOC, pp. 245-251, 1993.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  52. O. Goldreich, A. Wigderson.
    Improved derandomization of BPP using a hitting set generator
    Proc. of the RAMDOM 99 Conference, pp. 131-137, 1999.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  53. R. Impagliazzo, R. Shaltiel, A. Wigderson.
    Near-optimal Conversion of Hardness into Pseudo-randomness
    Proc. of the 40th FOCS, pp. 181-190, 1999.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  54. L . Babai, A. Gal, A. Wigderson.
    Superpolynomial lower bounds for monotone span programs.
    Combinatorica Vol. 19, No. 3, 301-319, 1999.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  55. R. Impagliazzo, A. Wigderson.
    Randomness vs. Time: De-randomization under a uniform assumption
    Proc. of the 39th FOCS, pp.734-743, 1998.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  56. N. Linial, A. Samorodnitsky, A. Wigderson.
    A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
    Proc. of 30th STOC, pp. 644-652, 1998.
    Combinatorica, 20, 4, 2000.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  57. 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.
    Proc. of the 26th STOC, pp. 676-685, 1994.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  58. 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 Proc. of the 27th STOC, pp. 103-111, 1995.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  59. A. Ambainis, L. Schulman, A. Ta-Shma, UVazirani, A. Wigderson.
    The Quantum Communication Complexity of Sampling
    Proc. of the 39th FOCS, pp. 342-351, 1998.
    Siam Journal on Computing, 32, pp. 1570-1585, 2003.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [ Journal version (pdf) ] [ Journal version (ps) ] [bibTeX entry]
     
  60. H. Buhrman, R. CLeve, A. Wigderson.
    Quantum vs. Classical Communication and Computation
    Proc. of 30th STOC, pp. 63-68, 1998.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  61. A. Razborov, A. Wigderson, A. Yao.
    Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and Transversal Calculus
    Proc. of the 29th STOC, pp. 739-748, 1997.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  62. I. Parnafes, R. Raz, A. Wigderson.
    Direct Product Results and the GCD Problem, in Old and New Communication Models
    Proc. of the 29th STOC, pp. 363-372, 1997.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  63. R. Impagliazzo, A. Wigderson.
    P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
    Proc. of the 29th STOC, pp. 220-229, 1997.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  64. 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 (postscript) ] [bibTeX entry]
     
  65. N. Nisan, A. Wigderson.
    Lower Bounds on Arithmetic Circuits via Partial Derivatives
    Preliminary version in Proc. of the 36th FOCS, pp. 16-25, 1995.
    Computational Complexity, Vol. 6, pp. 217-234, 1996.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  66. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  67. R. Sharan, A. Wigderson.
    A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
    Proc. of ISTCS 96, pp. 56-65, 1996.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  68. A. Gal, A. Wigderson.
    Boolean Complexity Classes vs. Their Arithmetic Analogs
    Random Structures and Algorithms, Vol. 9, pp. 1-13, 1996.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  69. R. Armoni, M. Saks, A. Wigderson, S. Zhou.
    Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
    Proc. of the 37th FOCS, pp. 412-421, 1996.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  70. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  71. 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 Proc. of the 22nd STOC, pp 244-253, May 1990.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  72. L . Babai, A. Gal, J. Kollar, L. Ronyai, T. Szabo, A. Wigderson.
    Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
    Proc of 28th STOC, pp. 603-611, 1996.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  73. 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 (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  74. 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 (postscript) ]
     
  75. N. Nisan, A. Wigderson.
    On the Complexity of Bilinear Forms
    Proc. of the 27th STOC, pp. 723-732, 1995.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  76. N. Nisan, A. Wigderson.
    A note on Rank vs. Communication Complexity
    Combinatorica, Vol. 15, No 4, pp. 557-566, 1995.
    Also appeared in Proc. of the 35th FOCS, pp. 831-836, 1994.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  77. 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 Proc. of the 6th Structures in Complexity Theory conference, pp. 299-304, July 1991.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  78. N. Alon, U. Feige, A. Wigderson, D. Zuckerman.
    Derandomized Graph Products
    Computational Complexity, pp. 60-75, 1995.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  79. 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 Proc of the 32nd FOCS conference, pp. 576-585, 1991.)
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  80. N. Nisan, A. Wigderson.
    Hardness vs. Randomness
    Journal of Computer Systems and Sciences, Vol. 49, No. 2, pp. 149-167, 1994.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  81. 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.
    Proc. of the 22nd STOC, pp. 379-388, May 1990.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  82. A. Wigderson.
    NL/poly L/poly
    Proc. of the 9th Structures in Complexity conference, pp. 59-62, July 1994.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  83. R. Impagliazzo, N. Nisan, A. Wigderson.
    Pseudorandomness for Network Algorithms
    Proc. of the 26th STOC, pp. 356-364, 1994.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  84. O. Goldreich, A. Wigderson.
    Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
    Proc. of the 26th STOC, pp. 574-583, 1994.
    (Abstract)
    [ Proceedings version (ps) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  85. 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 (postscript) ] [bibTeX entry]
     
  86. M. Karchmer, A. Wigderson.
    On Span Programs
    Proc. of the 8th Structures in Complexity conference, pp. 102-111, 1993.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  87. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  88. 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 (postscript) ] [bibTeX entry]
     
  89. 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 (postscript) ] [bibTeX entry]
     
  90. R. Ostrovsky, A. Wigderson.
    Nontrivial Zero-Knowledge implies One-Way Functions
    Proc. of the 2nd ISTCS, pp. 3-17, 1993.
    (Abstract)
    [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  91. 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 (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  92. 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 (postscript) ] [bibTeX entry]
     
  93. 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.
    Proc. of the 6th Structures in Complexity Theory comference, pp. 213-219, July 1991.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  94. S. Hoory, A. Wigderson.
    Universal Sequences for Expander Graphs
    Information Processing Letters, Vol. 46, No. 2, pp. 67-69, 1993.
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  95. M. Luby, B. Velickovic, A. Wigderson.
    Deterministic Approximate Counting of Depth-2 Circuits
    Proc. of the 2nd ISTCS (Israeli Symposium on Theoretical Computer Science), pp. 18-24, 1993.
    (Abstract)
    [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  96. M. Karchmer, A. Wigderson.
    On Characterizing Nondeterministic Circuit Size
    Proc. of the 25th STOC, pp. 532-545, 1993.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  97. Y. Rabinovich, A. Sinclair, A. Wigderson.
    Quadratic Dynamical Systems
    Proc. of the 33rd FOCS conference, pp. 304-313, 1992.
    (Abstract)
    [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  98. A. Wigderson.
    The Complexity of Graph Connectivity
    Proc. 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 (postscript) ] [bibTeX entry]
     
  99. R. Raz, A. Wigderson.
    Monotone Circuits for Matching require Linear Depth
    Journal of the ACM, Vol. 39, pp. 736-744, 1992.
    Preliminary version in Proc. of the 22nd STOC, pp. 287-292, May 1990.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  100. Y. Gil, W. Steiger, A. Wigderson.
    Geometric Medians
    Discrete Math, Vol. 108, No. 1, pp. 37-51, 1992.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  101. P. Gemmell, R. Lipton, R. Rubinfeld, Sudan , A. Wigderson.
    Self Testing / Correcting for Polynomials and for Approximate Functions
    Proc. of the 23rd STOC, pp. 32-42, May 1991.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  102. Y. Rabinovich, A. Wigderson.
    An Analysis of a Simple Genetic Algorithm
    Proc. of the 4th International Conference on Genetic Algorithms, pp. 215-221, July 1991.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  103. R. Heiman , A. Wigderson.
    Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions
    Proc. of the 6th Structures in Complexity Theory Conference, pp. 172-179, July 1991.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  104. L. Lovasz, I. Newman, M. Naor, A. Wigderson.
    Search Problems in the Decision Tree Model
    Proc of the 32nd FOCS conference, pp. 576-585, 1991.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  105. 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 (postscript) ] [bibTeX entry]
     
  106. P. Ragde, A. Wigderson.
    Linear-Size Constant-Depth Polylog- Threshold Circuits,
    Information Processing Letters, Vol. 39, No. 3, pp. 143-146, 1991.
    (Abstract)
    [ Journal version (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  107. N. Nisan, A. Wigderson.
    Rounds in Communication Complexity Revisited
    Proc. of the 23rd STOC, pp. 419-429, May 1991.
    (Abstract)
    [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]
     
  108. O. Goldreich, S. Micali, A. Wigderson.
    Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems
    Journal of the ACM, Vol. 38, No. 1, pp. 691-729, 1991.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  109. 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 (postscript) ] [bibTeX entry]
     
  110. I. Newman, P. Ragde, A. Wigderson.
    Perfect Hashing, Graph Entropy and Circuit Complexity
    Proc. of the 5th Structures in Complexity Theory conference, pp. 91-99, July 1990.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  111. F. Fich, A. Wigderson.
    Towards Understanding Exclusive Read
    Proc. of 1st Symposium on Parallel Algorithms and Architectures, pp. 718-727, August 1990.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  112. M. Karchmer, A. Wigderson.
    Monotone Circuits for Connectivity require Super-Logarithmic Depth
    SIAM Journal on Discrete Mathematics, Vol. 3, No. 2, pp. 255-265, 1990.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  113. 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 (postscript) ] [bibTeX entry]
     
  114. 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 (postscript) ] [bibTeX entry]
     
  115. Y. Gil, F. Meyer auf der Heide, A. Wigderson.
    Not All Keys can be Hashed in Constant Time
    Proc. of the 22nd STOC, pp 244-253, May 1990.
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  116. N. Alon, M. Karchmer, A. Wigderson.
    Linear Circuits over GF(2)
    SIAM Journal on Computing, Vol. 19, No. 6, pp. 1064-1067, 1990.
    (Abstract)
    [ Journal version (pdf) ] [ Journal Version (postscript) ] [bibTeX entry]
     
  117. 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 (postscript) ] [bibTeX entry]
     
  118. 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 (postscript) ] [ Journal version (pdf) ] [bibTeX entry]
     
  119. R. Raz, A. Wigderson.
    Probabilistic Communication Complexity of Boolean Relations
    Proc of the 30th FOCS, pp. 562-567, 1989.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  120. N. Nisan, E. Szemeredi, A. Wigderson.
    Undirected Connectivity in Space
    Proc. of the 30th FOCS conference, pp. 24-29, 1989.
    (Abstract)
    [ Draft of final version (postscript) ] [ Draft of final version (pdf) ] [bibTeX entry]
     
  121. 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 (postscript) ] [bibTeX entry]
     
  122. A. Cohen, A. Wigderson.
    Dispersers, Deterministic Amplification and Weak random Sources
    Proc. of the 30th FOCS, pp. 14-19, 1989.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  123. M. Ajtai, A. Wigderson.
    Deterministic Simulation of Probabilistic Constant-Depth Circuits
    Advances in Computing Research - Randomness and Computation, Ed. F. Preparata and S. Micali, Vol. 5, pp. 199-223, 1989
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  124. 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 (postscript) ] [bibTeX entry]
     
  125. F. Fich, P. Ragde, A. Wigderson.
    Simulations among Concurrent-Write PRAMs
    Algorithmica, Vol. 3, pp. 43-51, 1988.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  126. 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 (postscript) ] [bibTeX entry]
     
  127. 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 (postscript) ] [bibTeX entry]
     
  128. 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 (postscript) ] [bibTeX entry]
     
  129. 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 (postscript) ] [bibTeX entry]
     
  130. N. Nisan, A. Wigderson.
    Hardness vs. Randomness
    Proc. of the 29th FOCS, pp. 2-11, 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  131. A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
    A Time-Space Tradeoff for Element Distinctness
    Proc. of STACS Conference, Lecture Notes in Comp. Sci, Springer Verlag, Vol. 210, pp. 353-358, 1986.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  132. S. Goldwasser, J. Kilian, M. Ben-Or, A. Wigderson.
    Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
    Proc. of the 20th STOC, pp. 113-131, May 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  133. B. Yust, F. Meyer auf der Heide, A. Wigderson.
    On Computations with Integer Division
    Proc. of the STACS conference, pp. 29-37, 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  134. S. Goldwasser, M. Ben-Or, A. Wigderson.
    Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computing
    Proc. of the 20th STOC, pp. 1-10 May 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  135. M. Karchmer, A. Wigderson.
    Monotone Connectivity Circuits require Super-logarithmic Depth
    Proc. of the 20th STOC, pp. 539-550, May 1988.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [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 (postscript) ] [bibTeX entry]
     
  137. 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 (postscript) ] [bibTeX entry]
     
  138. 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 (postscript) ] [bibTeX entry]
     
  139. O. Goldreich, S. Micali, A. Wigderson.
    How to Play any Mental Game
    Proc. of the 19th STOC, pp. 218-229, May 1987.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ]
     
  140. 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-16, 1987.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  141. 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 (postscript) ] [bibTeX entry]
     
  142. 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 (postscript) ] [bibTeX entry]
     
  143. 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 (postscript) ] [bibTeX entry]
     
  144. R. Karp, M. Saks, A. Wigderson.
    A Search Problem Related to Branch-and-Bound Procedures
    Proc. of the 27th FOCS, pp. 19-28, October, 1986.
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  145. N. Linial, Lovasz , A. Wigderson.
    A Physical interpretation of graph connectivity and its algorithmic applications
    Proc of the 27 FOCS, pp.39-48, October 1986.
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  146. O. Goldreich, S. Micali, A. Wigderson.
    Proofs that Yield Nothing but their Validity, and a Methodology of Cryptographic Protocol Design
    Proc. of the 27th FOCS, pp. 174-187, October 1986.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  147. 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 (postscript) ] [bibTeX entry]
     
  148. 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
    Lecture Notes in Comp. Sci., Springer Verlag, Vol. 226, pp. 50-59, 1986.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  149. M. Saks, A. Wigderson.
    Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
    Proc. of the 27th FOCS, pp. 29-38, October 1986.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  150. R. Karp, E. Upfal, A. Wigderson.
    The Complexity of Parallel Computation on Matroids
    Proc. of the 26th FOCS, pp. 541-550, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  151. 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 Proc. of the 16th STOC, pp. 266-272, May 1984.
    (Abstract)
    [ Journal version (pdf) ] [ Journal version (postscript) ] [bibTeX entry]
     
  152. 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 (postscript) ] [bibTeX entry]
     
  153. A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, A. Wigderson.
    Multilayer Grid Embedding
    Proc of the 26th FOCS, pp. 186-196, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  154. F. Fich, F. Meyer auf der Heide, P. Ragde, A. Wigderson.
    One, Two, Three...Infinity: Lower Bounds for Parallel Computation
    Proc of the 17th STOC, pp. 48-58, May 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  155. R. Karp, E. Upfal, A. Wigderson.
    Constructing a Perfect matching is in Random NC
    Proc. of the 17th STOC, pp. 22-32, May 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  156. R. Karp, E. Upfal, A. Wigderson.
    Are Search and Decision Problems Computationally Equivalent?
    Proc. of the 17th STOC, pp. 464-475 May 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  157. G. 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 (postscript) ] [bibTeX entry]
     
  158. M. Ajtai, A. Wigderson.
    Deterministic Simulation of Probabilistic Constant- Depth Circuits
    Proc. of the 26th FOCS, pp. 11-19, October, 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  159. F. Meyer auf der Heide, A. Wigderson.
    The Complexity of Parallel Sorting
    Proc. of the 26th FOCS, pp. 532-540, October 1985.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  160. 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 (postscript) ] [bibTeX entry]
     
  161. 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 (postscript) ] [bibTeX entry]
     
  162. 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 (postscript) ] [bibTeX entry]
     
  163. E. Upfal, A. Wigderson.
    How to Share Memory in a Distributed System
    Proc. of the 25th FOCS, pp. 171-180, October 1984.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  164. D. Long, A. Wigderson.
    How Discreet is the Discrete Log?
    Proc. of the 15th STOC, pp. 413-420, May 1983.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  165. D. Dolev, C. Dwork, N. Pippenger, A. Wigderson.
    Superconcentrators, Generalizers, and Generalized Connectors with Limited Depth
    Proc. of the 15th STOC, pp. 42-51, May 1983.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  166. U. Vishkin, A. Wigderson.
    Depth-Width Trade-offs in Parallel Computation
    Proc. of the 24th FOCS, pp. 146-153, November 1983.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  167. D. Dolev, A. Wigderson.
    The Security of Multi-Party Protocols in Distributed Systems
    Proc. of the Crypto 82 Conference, pp. 167-176, August 1982.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  168. A. Wigderson.
    A New Approximate Graph Coloring Algorithm
    Proc. of the 14th STOC, pp. 325-329, May 1982.
    (Abstract)
    [ Proceedings version (pdf) ] [ Proceedings version (postscript) ] [bibTeX entry]
     
  169. 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 (postscript) ] [bibTeX entry]
     
  170. 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]
     
  171. 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 (postscript) ] [bibTeX entry]