Russell Impagliazzo

Office: 4248 Computer Science Building
Phone: (858) 534-1332; Fax: (858) 534-7029;
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.
Starting in Fall 2007, I will be at the Institute for Advanced Study in Princeton, New Jersey for Fall and Winter quarters, and back at UCSD for Spring quarters and most of each Summer. I will be at IAS for a total of five years, but they may not be entirely consecutive. Fall 2007, Winter 2008, Fall 2008 and Winter 2009 are confirmed. After that, I may spend a solid year back at UCSD before resuming at IAS the following year. I will be teaching a proportional course load each Spring (one or two courses), and will remain active in the UCSD department. While I am not looking for new, solely advised, Ph.D. students during this time, I could be a co-advisor with another faculty member. So I still encourage prospective theory students to do their graduate studies at UCSD.

• CSE 200: Computability and Complexity
• CSE 202: Algorithms and Data Structures

1. M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi, and S. Rudich
   Reducing the Complexity of Reductions
2. M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T.Pitassi, Toward a Model for Backtracking and Dynamic Programming
3. Boaz Barak, Oded Goldreich, R. Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang, On the (Im)possibility of obfuscating programs
4. Boaz Barak, R. Impagliazzo, and Avi Wigderson , Extracting randomness using few independent sources
5. Paul Beame S. Cook, Jeff Edmonds , R. Impagliazzo, and T. Pitassi,
   The Relative Complexity of NP Search Problems
6. Paul Beame R. Impagliazzo, J. Krajicek T. Pitassi, and P. Pudlak, Lower Bounds for Hilbert's Nullstellensatz and Propositional Proofs
7. Paul Beame R. Impagliazzo, and T. Pitassi,
   Improved depth lower bounds for small distance connectivity
8. Paul Beame R. Impagliazzo, T. Pitassi, and N. Segerlind ,
   DPLL and Memoization: Formula Caching Proof Systems
9. Paul Beame , R. Impagliazzo, J. Krajicek T. Pitassi, and P. Pudlak
   Lower bounds on Hilbert's Nullstellensatz and propositional proofs.
10. M. Bellare, and R. Impagliazzo,
    A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion
11. M. Bellare, R. Impagliazzo, and M. Naor
    Does parallel repetition decrease error probability in computationally sound proofs?
12. E. Ben-Sasson and R. Impagliazzo,
    Random CNF's are hard for the polynomial calculus
13. E. Ben-Sasson R. Impagliazzo, and A. Wigderson
    Near-optimal separation of tree-like and general resolution
14. J. Buresh-Oppenheim, M. Clegg, R. Impagliazzo, and T. Pitassi,
    Homogenization and the Polynomial Calculus
15. T. Carson and R. Impagliazzo, Hill-climbing finds random planted bisections
16. T. Carson and R. Impagliazzo, Experimentally Determining Regions of Related Solutions in Graph Bisection Problems
17. A. Clementi and R. Impagliazzo,
    The reachability problem for finite cellular automata
18. M. Clegg, Jeff Edmonds and R. Impagliazzo, Using the Groebner Basis Algorithm to find Proofs of Unsatisfiability
19. S. Davis and R. Impagliazzo, Models of Greedy Algorithms for Graph Problems
20. T. Dimitriou and R. Impagliazzo, Towards an Analysis of Local Optimization Heuristics
21. T. Dimitriou and R. Impagliazzo, Go-with-the-winners For Graph Bisections
22. Jeff Edmonds R. Impagliazzo, S. Rudich and Jiri Sgall
    Communication complexity towards lower bounds on circuit depth
23. L. Fortnow, R. Impagliazzo, V. Kabanets, and C. Umans, On the Complexity of Succinct Zero-Sum Games
24. A. Gupta and R. Impagliazzo, Computing Planar Intertwines
25. Johan Håstad R. Impagliazzo, L. Levin, and Michael Luby
    Construction of a pseudo-random generator from any one-way function.
26. R. Impagliazzo,
    A Personal View of Average-Case Complexity
27. R. Impagliazzo,
    Hardness as Randomness: A Survey of Universal Derandomization
28. R. Impagliazzo,
    Computational Complexity Since 1980 (Invited talk at FSTTCS 2005)
29. R. Impagliazzo, Hardcore Distributions for Somewhat Hard Problems
30. R. Impagliazzo, V. Kabanets and A. Wigderson, Searching for an easy witness: derandomization and circuit complexity
31. R. Impagliazzo and M. Naor ,
    Efficient cryptographic schemes provably as secure as subset sum.
32. R. Impagliazzo and N. Nisan
    The effects of random restiction on Boolean formulas.
33. R. Impagliazzo, R. Paturi
    Complexity of k-SAT
34. R. Impagliazzo, R. Paturi and M. Saks.
    Size-depth trade-offs for threshold Circuits.
35. R. Impagliazzo, R. Paturi, and F. Zane
    Which Problems Have Strongly Exponential Complexity?
36. R. Impagliazzo, T. Pitassi, and A. Urqhart.
    Upper and lower bounds on tree-like cutting planes proofs.
37. R. Impagliazzo, N. Nisan and A. Wigderson
    Pseudorandomness for network algorithms
38. R. Impagliazzo, P. Pudlak and Jiri Sgall
    Lower Bounds for the Polynomial Calculus and for the Groebner Basis Algorithm
39. R. Impagliazzo and S. Rudich ,
    Limits on the Provable Consequences of One-Way Permutations
40. R. Impagliazzo, R. Shaltiel and A. Wigderson
    Near-Optimal conversion of Hardness into Pseudo-Randomness
41. R. Impagliazzo and A. Wigderson
    P=BPP unless E has sub-exponential circuits: De-randomizing the XOR Lemma
42. R. Impagliazzo and A. Wigderson
    Randomness vs. Time: De-randomization under a uniform assumption
43. V. Kabanets and R. Impagliazzo, Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
44. T. Pitassi, Paul Beame , and R. Impagliazzo, Exponential lower bounds for constant depth Frege proofs of the pigeonhole principle.
45. P. Pudlak and R. Impagliazzo
    A lower bound for DLL algorithms for k-SAT
46. N. Segerlind , S. Buss and R. Impagliazzo, A switching lemma for small restrictions and k-DNF resolution