2015 Knuth Prize Citation for L´ aszl´ o Babai The 2015 Donald E. Knuth Prize is awarded to L´aszl´o Babai of the University of Chicago for his fundamental contributions to theoretical computer science, including alg

First Page		Document Content
Date: 2015-05-26 18:25:25 Probabilistic complexity theory Theoretical computer science Morphisms Computational complexity theory PCP theorem Mathematical optimization Probabilistically checkable proof Combinatorica IP Algorithm Russell Impagliazzo Graph isomorphism		2015 Knuth Prize Citation for L´ aszl´ o Babai The 2015 Donald E. Knuth Prize is awarded to L´aszl´o Babai of the University of Chicago for his fundamental contributions to theoretical computer science, including alg Add to Reading List Source URL: www.sigact.org Download Document from Source Website File Size: 47,80 KB Share Document on Facebook

	A Personal View of Average-Case Complexity Russell Impagliazzo Computer Science and Engineering UC, San Diego 9500 Gilman Drive La Jolla, CA DocID: 1xViX - View Document
	Randomness vs. Time: De-randomization under a uniform assumption Russell Impagliazzo∗ Department of Computer Science University of California San Diego, CA DocID: 1vs6Y - View Document
	P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma Russell Impagliazzo∗ Avi Wigderson† Department of Computer Science Institute of Computer Science University of California DocID: 1uymj - View Document
	Pseudorandomness for Network Algorithms Russell Impagliazzo ∗ Noam Nisan DocID: 1unPp - View Document
	EATCS-IPEC Nerode Prize 2013 On the Exact Complexity of Evaluating Quantified k-CNF Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, Algorithmica 2013 The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs DocID: 1m4oG - View Document