Russell Impagliazzo

Department of Computer Science and Engineering Temp link
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. I am back from my leave at IAS, and am interested in advising students, so please come by and talk. Simons report


Courses for Fall, 2019
A web-site for a related class I taught at Berkeley as part of the Simons Institute program on Fine-Grained Complexity and Algorithms FGCA
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, R. Jaiswal, unpublished. abstract metropolis analysis
  32. R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Widgerson, Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized (SIAM Journal of Computing version)
  33. R. Impagliazzo, V. Kabanets, A. Kolokolova, An Axiomatic Approach to Algebrization
  34. R. Impagliazzo, V. Kabanets and A. Wigderson, Searching for an easy witness: derandomization and circuit complexity
  35. R. Impagliazzo and M. Naor ,
    Efficient cryptographic schemes provably as secure as subset sum.
  36. R. Impagliazzo and N. Nisan
    The effects of random restiction on Boolean formulas.
  37. R. Impagliazzo, R. Paturi
    Complexity of k-SAT
  38. R. Impagliazzo, R. Paturi and M. Saks.
    Size-depth trade-offs for threshold Circuits.
  39. R. Impagliazzo, R. Paturi, and F. Zane
    Which Problems Have Strongly Exponential Complexity?
  40. R. Impagliazzo, T. Pitassi, and A. Urqhart.
    Upper and lower bounds on tree-like cutting planes proofs.
  41. R. Impagliazzo, N. Nisan and A. Wigderson
    Pseudorandomness for network algorithms
  42. R. Impagliazzo, P. Pudlak and Jiri Sgall
    Lower Bounds for the Polynomial Calculus and for the Groebner Basis Algorithm
  43. R. Impagliazzo and S. Rudich ,
    Limits on the Provable Consequences of One-Way Permutations
  44. R. Impagliazzo, R. Shaltiel and A. Wigderson
    Near-Optimal conversion of Hardness into Pseudo-Randomness
  45. R. Impagliazzo and A. Wigderson
    P=BPP unless E has sub-exponential circuits: De-randomizing the XOR Lemma
  46. R. Impagliazzo and A. Wigderson
    Randomness vs. Time: De-randomization under a uniform assumption
  47. V. Kabanets and R. Impagliazzo, Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
  48. T. Pitassi, Paul Beame , and R. Impagliazzo, Exponential lower bounds for constant depth Frege proofs of the pigeonhole principle.
  49. P. Pudlak and R. Impagliazzo
    A lower bound for DLL algorithms for k-SAT
  50. N. Segerlind , S. Buss and R. Impagliazzo, A switching lemma for small restrictions and k-DNF resolution