Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

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.


Course web pages for Spring, 2009:

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