Russell Impagliazzo
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 920930114
Office: 4248 Computer Science Building
Phone: (858) 5341332; Fax: (858) 5347029;
Email: russell@cs.ucsd.edu
I am a professor specializing in computational complexity
theory.
My research is in proof complexity, the theory of cryptography, computational randomness,
structural complexity, and trying to analyze optimization heuristics
and other approaches to solving hard problems.
I am back from my leave at IAS, and am interested in advising
students, so please come by and talk.
Courses for Spring, 2015:
CSE 21: Mathematics for Algorithm and System Analysis ,
see Ted and Piazza sites for this class. Office hours: Tuesday, Thursday, 1112:30 in 4248 CSE (if overfull,
will move to 4258)
My Ph.D. thesis:
Pseudorandom generators for cryptography and for
randomized algorithms
Ted Carson's thesis:
Empirical and Analytic Approaches to Understanding
Local Search Heuristics
Some research papers:
 S. Arora, R. Impagliazzo, U. V. Vazirani, Relativizing versus Nonrelativizing
Techniques: the Role of Local Checkability. Note:
This paper is unpublished because it is controversial.
The first singleauthored version was written in 1988,
and a version with the current name and authors dates to
1991. However, the authors make updates every few years,
before putting it aside again.

M. Agrawal,
E. Allender,
R. Impagliazzo,
T. Pitassi,
and
S. Rudich
Reducing the Complexity of Reductions

M. Alekhnovich, A. Borodin, J. BureshOppenheim,
R. Impagliazzo, A. Magen,
and T.Pitassi,
Toward a Model for Backtracking and
Dynamic Programming

Boaz Barak,
Oded Goldreich, R. Impagliazzo, Steven Rudich, Amit Sahai,
Salil Vadhan, and Ke Yang, On the
(Im)possibility of obfuscating programs

Boaz Barak,
R.
Impagliazzo, and
Avi Wigderson ,
Extracting randomness using few
independent sources

Paul Beame
S. Cook,
Jeff Edmonds
, R. Impagliazzo, and
T. Pitassi,
The Relative Complexity of NP Search Problems

Paul Beame
R. Impagliazzo,
J. Krajicek
T. Pitassi,
and
P. Pudlak,
Lower Bounds for Hilbert's Nullstellensatz and
Propositional Proofs

Paul Beame
R. Impagliazzo, and
T. Pitassi,
Improved depth lower bounds for small distance
connectivity

Paul Beame
R. Impagliazzo,
T. Pitassi,
and N. Segerlind ,
DPLL and Memoization: Formula Caching Proof Systems

Paul Beame
, R. Impagliazzo,
J. Krajicek
T. Pitassi,
and
P. Pudlak
Lower bounds on Hilbert's Nullstellensatz and propositional
proofs.

M. Bellare,
and R. Impagliazzo,
A tool for obtaining tighter security analyses of
pseudorandom function based constructions, with applications to
PRP to PRF conversion

M. Bellare,
R. Impagliazzo, and
M. Naor
Does parallel repetition decrease error probability in
computationally sound proofs?

E. BenSasson
and R. Impagliazzo,
Random CNF's are hard for the polynomial calculus

E. BenSasson
R. Impagliazzo,
and
A. Wigderson
Nearoptimal separation of treelike and general resolution

J. BureshOppenheim,
M. Clegg,
R. Impagliazzo, and
T. Pitassi,
Homogenization and the Polynomial Calculus

T. Carson and R. Impagliazzo,
Hillclimbing finds random planted bisections

T. Carson and R. Impagliazzo,
Experimentally Determining Regions of Related Solutions in
Graph Bisection Problems

A. Clementi and R. Impagliazzo,
The reachability problem for
finite cellular automata

M. Clegg,
Jeff Edmonds
and R. Impagliazzo,
Using the Groebner Basis Algorithm to find Proofs of Unsatisfiability

S. Davis and R. Impagliazzo,
Models of Greedy Algorithms for Graph
Problems

T. Dimitriou and R. Impagliazzo,
Towards an Analysis of Local Optimization
Heuristics

T. Dimitriou and R. Impagliazzo,
Gowiththewinners For Graph Bisections

Jeff Edmonds
R. Impagliazzo,
S. Rudich
and
Jiri Sgall
Communication complexity towards lower bounds on circuit
depth

L. Fortnow, R. Impagliazzo, V. Kabanets, and C. Umans,
On the Complexity of Succinct ZeroSum
Games

A. Gupta and R. Impagliazzo,
Computing Planar Intertwines

Johan Håstad
R. Impagliazzo,
L.
Levin,
and
Michael Luby
Construction of a pseudorandom generator from any oneway
function.

R. Impagliazzo,
A Personal View of AverageCase Complexity

R. Impagliazzo,
Hardness as Randomness: A Survey of Universal Derandomization

R. Impagliazzo,
Computational Complexity Since 1980
(Invited talk at FSTTCS 2005)

R. Impagliazzo,
Hardcore Distributions for Somewhat Hard
Problems

R. Impagliazzo, R. Jaiswal, unpublished. abstract metropolis analysis

R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Widgerson,
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
(SIAM Journal of Computing version)

R. Impagliazzo, V. Kabanets, A. Kolokolova,
An Axiomatic Approach
to Algebrization

R. Impagliazzo,
V. Kabanets
and
A. Wigderson,
Searching for an easy witness: derandomization and circuit
complexity

R. Impagliazzo and
M. Naor
,
Efficient cryptographic schemes
provably as secure as subset sum.

R. Impagliazzo and
N. Nisan
The effects of random restiction
on Boolean formulas.

R. Impagliazzo,
R. Paturi
Complexity of kSAT

R. Impagliazzo,
R. Paturi
and M. Saks.
Sizedepth tradeoffs for threshold Circuits.

R. Impagliazzo,
R. Paturi, and F. Zane
Which Problems Have Strongly Exponential Complexity?

R. Impagliazzo,
T. Pitassi,
and A. Urqhart.
Upper and lower bounds on treelike cutting planes proofs.

R. Impagliazzo,
N. Nisan and
A. Wigderson
Pseudorandomness for network algorithms

R. Impagliazzo,
P. Pudlak
and
Jiri Sgall
Lower Bounds for the Polynomial Calculus and
for the Groebner Basis Algorithm

R. Impagliazzo and
S. Rudich
,
Limits on the Provable
Consequences of OneWay Permutations

R. Impagliazzo,
R. Shaltiel
and
A. Wigderson
NearOptimal conversion of Hardness into PseudoRandomness

R. Impagliazzo
and
A. Wigderson
P=BPP unless E has subexponential circuits: Derandomizing the XOR Lemma

R. Impagliazzo
and
A. Wigderson
Randomness vs. Time: Derandomization under a uniform assumption

V. Kabanets
and R. Impagliazzo,
Derandomizing Polynomial Identity Tests Means Proving Circuit
Lower Bounds

T. Pitassi,
Paul Beame
, and R. Impagliazzo,
Exponential lower bounds for constant depth Frege
proofs of the pigeonhole principle.

P. Pudlak
and R. Impagliazzo
A lower bound for DLL algorithms for kSAT

N. Segerlind ,
S. Buss
and R. Impagliazzo,
A switching lemma for small restrictions
and kDNF resolution