People, Problems, and Proofs

Richard Lipton is the Storey Professor of Computer Science at Georgia Institute of Technology; previously he held faculty positions at Yale University, the University of California at Berkeley, and Princeton University. His research is focused primarily on the theory of computation, where he has made seminal contributions. He is a member of the National Academy of Engineering, an ACM Fellow, and a Guggenheim Fellow. Kenneth Regan is a professor of computer science at The State University of New York at Buffalo. His research interests include computational complexity. He is an international chess master and an expert on investigating cheating in chess.

• The Claimant, the Readers, and the Crowd.- Kenneth Iverson: Notation and Thinking.- Edmund Hillary: Proofs and Mountain Climbing.- Leonardo da Vinci: Proofs as Art.- Michael Atiyah: The Role of Proof.- Subhash Khot: Unique Games Conjecture.- Arno van den Essen: An Amazing Conjecture.- Richard Hamilton: Group Efforts.- Grigori Perelman: A New Clay Problem.- Eric Allender: Solvable Groups.- Enrico Bombieri: On Intuition.- Fred Hennie: Lower Bounds.- Volker Strassen: Amazing Results.- Adam Smith: Dumb Channels.- Georg Cantor: Diagonal Method.- Raymond Smullyan: The Reals Are Uncountable.- William Tutte: Flow Problems.- Basil Rathbone: Writing a Major Result.- Elwyn Berlekamp: Dots And Boxes.- David Johnson: Galactic Algorithms.- Warren Hirsch: Guessing The Truth.- Shimon Even: A Promise Problem.- Matei David: Improving Noam Nisan’s Generator.- Ryan Williams: A New Lower Bound.- Joel Seiferas: More on the New Lower Bound.- Victor Klee: Big Results.- George Dantzig: Equations, Equations, and Equations.- Srinivasa Ramanujan: The Role of Amateurs.- John Rhodes: Approaches to Problems.- John Nash: Connections.- Chee Yap: Computing Digits of π.- Henri Lebesgue: Projections Are Tricky.- Nina Balcan: A New Model of Complexity.- Sam Buss: Bounded Logic.- Anton Klyachko: Car Crashes.- Bernard Chazelle: Natural Algorithms.- Thomas Jech: The Axiom of Choice.- Alfonso Bedoya: Definitions, Definitions, and Definitions.- Hartley Rogers: Complexity Classes.- Ron Fagin: Second Order Logic.- Daniel Lokshtanov: Knapsack Problem.- Albert Einstein: Beyond Polynomial Equations.- Denis Thérien: Solvable Groups.- Andreas Björklund: Hamiltonian Cycles.- David Hilbert: The Nullstellensatz.- John Hopcroft: Thinking out of the Box.- Dick Karp: The Polynomial Hierarchy.- Nick Howgrave-Graham and Antoine Joux: Attacking the Knapsack Problem.- Hedy Lamarr: The Role of Amateurs.- Nicolas Courtois: The Linearization Method.- Neal Koblitz: Attacks on Crypto-systems.- Richard Feynman: Miracle Numbers.- Patrick Fischer: Programming Turing Machines.- Roger Apéry: Explaining Proofs.- Ron Rivest: Mathematical Gifts.- Frank Ryan: The Quarterback Teaches.- Leonard Schulman: Associativity.- Paul Seymour: Graph Minors.- Alfred Tarski: Lower Bounds on Theories.- Ken Thompson: Playing Chess.- Virginia Vassilevska: Fixing Tournaments.- Arkadev Chattopadhyay: Computing Modulo Composites.- Charles Bennett: Quantum Protocols.

"The book has 63 chapters, each one ... representing an edited version of a post in GLL. ... this book will appeal to readers seeking an insider view on how creative mathematical ideas emerge. And it will also appeal to experts for its insightful ruminations on current scientific and cultural problems in theoretical computer science." (Marius Zimand, Mathematical Reviews, June, 2015) "This book is one of those inspiring books that almost every computer scientist should read. Moreover, it is also very well suited to a wider audience, including those curious about the field and newcomers. Its authors, Lipton and Regan, did a wonderful job introducing and analyzing important problems in complexity theory with an easy-to-read text. ... It is therefore an invaluable source of inspiration and study." (Carlos Linares Lopez, Computing Reviews, August, 2014)