• go to Douglas Engelbart's profile page
  • go to Richard Karp's profile page
  • go to Juris Hartmanis's profile page
  • go to Alfred V Aho's profile page
  • go to Herbert A. Simon's profile page
  • go to Edward A Feigenbaum's profile page
  • go to John Cocke 's profile page
  • go to Kristen Nygaard 's profile page
  • go to Marvin Minsky 's profile page
  • go to Frances Allen's profile page
  • go to Frederick Brooks's profile page
  • go to Silvio Micali's profile page
  • go to Jim Gray 's profile page
  • go to Geoffrey E Hinton's profile page
  • go to John McCarthy's profile page
  • go to Ole-Johan Dahl 's profile page
  • go to Donald E. Knuth's profile page
  • go to Leonard M. Adleman's profile page
  • go to Leslie Barry Lamport's profile page
  • go to Prof. Martin Hellman's profile page
  • go to Edmund Clarke's profile page
  • go to Edsger W. Dijkstra's profile page
  • go to Richard W. Hamming's profile page
  • go to Niklaus E. Wirth's profile page
A.M. TURING AWARD WINNERS BY...

Avi Wigderson DL Author Profile link

United States – 2023
Short Annotated Bibliography

Technical

Karchmer, M., and Wigderson, A., Monotone Circuits for Connectivity Require Super-Logarithmic Depth, SIAM Journal on Discrete Mathematics, Vol. 3, No. 2 (May 1990), pp. 255-265.

This paper introduces the Karchmer-Wigderson game, a framework that establishes deep connections between circuit complexity and communication complexity. The work shows that monotone circuits for computing graph connectivity require super-logarithmic depth, providing key insights into circuit lower bounds.

Raz, R., and Wigderson, A., Probabilistic Communication Complexity of Boolean Relations, Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1993, pp. 129-138.

Raz and Wigderson study probabilistic communication complexity, presenting results that show significant separations between different complexity measures in communication models. Their work has implications for understanding randomized algorithms and complexity lower bounds.

Karp, R., Upfal, E., and Wigderson, A., Constructing a Perfect Matching is in Random NC, Combinatorica, Vol. 6, No. 1 (1986), pp. 35-48.

This paper demonstrates that the problem of finding a perfect matching in a graph can be solved in randomized parallelized polylogarithmic time, making a significant contribution to parallel computation. The result is one of the foundational achievements in randomized parallel algorithms.

Goldreich, O., Micali, S., and Wigderson, A., Proofs that Yield Nothing But Their Validity, Journal of the ACM, Vol. 38, No. 3 (July 1991), pp. 691-729.

This seminal paper introduces zero-knowledge proofs, a concept that revolutionized cryptography. The authors develop a proof system where a prover can convince a verifier of the validity of a statement without revealing any additional information, laying the groundwork for modern cryptographic protocols.

Goldreich, O., Micali, S., and Wigderson, A., How to Play any Mental Game – A Completeness Theorem for Protocols with Honest Majority, Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), 1987, pp. 218-229.

In this paper, the authors provide a completeness theorem for multi-party protocols with an honest majority, showing that any distributed computation can be securely performed. This result is fundamental to secure multi-party computation, influencing both theory and practical applications in cryptography.

Nisan, N., and Wigderson, A., Hardness vs. Randomness, Journal of Computer and System Sciences, Vol. 49, No. 2 (Oct. 1994), pp. 149-167.

Nisan and Wigderson show a profound connection between computational hardness and the ability to derandomize algorithms. Their work provides a foundation for understanding the trade-offs between deterministic and randomized complexity classes and has long-standing implications for the P vs. BPP question.

Impagliazzo, R., and Wigderson, A., P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma, Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 1997, pp. 220-229.

This influential paper addresses derandomization by showing that if certain exponential-time problems require exponential-size circuits, then BPP collapses to P. The result plays a key role in efforts to understand the power of randomness in algorithms and complexity theory.

Reingold, O., Vadhan, S., and Wigderson, A., Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders, Annals of Mathematics, Vol. 155, No. 1 (Jan. 2002), pp. 157-187.

This paper introduces the zig-zag graph product, a novel method for constructing constant-degree expander graphs. The construction provides new insights into randomness and expansion properties in graphs, with wide applications in coding theory, cryptography, and complexity theory.

Retrospective analysis

Wigderson, A., Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019.

In this seminal book, Wigderson presents an accessible introduction to computational complexity theory, its major questions, and its impact on science and technology. He outlines the deep connections between computation and various fields of study, offering a comprehensive overview of the field's current state and future directions.

Wigderson, A., Knowledge, Creativity and P versus NP, Institute of Advanced Study, 2009.

Wigderson brings the P versus NP problem to non-specialists connecting P versus NP to a variety of scientific, technological, social science and humanities disciplines, and to creativity in general.