Travelled to:1 × France
1 × Italy
1 × Spain
1 × Switzerland
12 × USA
3 × Canada
Collaborated with:A.Wigderson V.Kabanets T.Pitassi S.Rudich C.Beck P.Beame M.Clegg J.Edmonds ∅ N.Segerlind G.D.Crescenzo T.Dimitriou N.Nisan A.Kolokolova R.Shaltiel A.Urquhart R.Paturi M.E.Saks L.A.Levin M.Luby R.Jaiswal J.Buresh-Oppenheim S.R.Buss D.Grigoriev M.Agrawal E.Allender S.A.Cook J.Krajícek P.Pudlák A.R.Woods D.Feldman M.Naor A.Shamir
Talks about:bound (5) algorithm (4) derandom (4) random (4) lower (4) polynomi (3) generat (3) circuit (3) optim (3) way (3)
Person: Russell Impagliazzo
DBLP: Impagliazzo:Russell
Contributed to:
201320122009200820062003
2002200020001999199719961995
199419941993199219891989Wrote 24 papers:
- STOC-2013-BeckI
- Strong ETH holds for regular resolution (CB, RI), pp. 487–494.
- STOC-2012-BeameBI #bound #trade-off
- Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space (PB, CB, RI), pp. 213–232.
- STOC-2009-ImpagliazzoKK #approach #axiom
- An axiomatic approach to algebrization (RI, VK, AK), pp. 695–704.
- STOC-2009-ImpagliazzoKW
- New direct-product testers and 2-query PCPs (RI, VK, AW), pp. 131–140.
- STOC-2008-ImpagliazzoJKW #theorem
- Uniform direct product theorems: simplified, optimized, and derandomized (RI, RJ, VK, AW), pp. 579–588.
- STOC-2006-Impagliazzo #algorithm #question #random
- Can every randomized algorithm be derandomized? (RI), pp. 373–374.
- STOC-2003-KabanetsI #bound #polynomial #proving #testing
- Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.
- ICALP-2002-ImpagliazzoS #axiom #bound #simulation
- Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations (RI, NS), pp. 208–219.
- ICALP-2000-Buresh-OppenheimCIP #calculus
- Homogenization and the Polynominal Calculus (JBO, MC, RI, TP), pp. 926–937.
- STOC-2000-ImpagliazzoSW #generative #pseudo
- Extractors and pseudo-random generators with optimal seed length (RI, RS, AW), pp. 1–10.
- STOC-1999-BussGIP #calculus #linear #polynomial
- Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (SRB, DG, RI, TP), pp. 547–556.
- STOC-1999-CrescenzoI
- Security-Preserving Hardness-Amplification for Any Regular One-Way Function (GDC, RI), pp. 169–178.
- STOC-1997-AgrawalAIPR #complexity #reduction
- Reducing the Complexity of Reductions (MA, EA, RI, TP, SR), pp. 730–738.
- STOC-1997-ImpagliazzoW #exponential
- P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma (RI, AW), pp. 220–229.
- STOC-1996-CleggEI #algorithm #proving #satisfiability #using
- Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability (MC, JE, RI), pp. 174–183.
- STOC-1996-DimitriouI #algorithm #analysis #optimisation #towards
- Towards an Analysis of Local Optimization Algorithms (TD, RI), pp. 304–313.
- STOC-1995-BeameCEIP #complexity #problem
- The relative complexity of NP search problems (PB, SAC, JE, RI, TP), pp. 303–314.
- LICS-1994-ImpagliazzoPU #bound #proving
- Upper and Lower Bounds for Tree-Like Cutting Planes Proofs (RI, TP, AU), pp. 220–228.
- STOC-1994-ImpagliazzoNW #algorithm #network #pseudo
- Pseudorandomness for network algorithms (RI, NN, AW), pp. 356–364.
- STOC-1993-ImpagliazzoPS #trade-off
- Size-depth trade-offs for threshold circuits (RI, RP, MES), pp. 541–550.
- STOC-1992-BeameIKPPW #bound #exponential #principle
- Exponential Lower Bounds for the Pigeonhole Principle (PB, RI, JK, TP, PP, ARW), pp. 200–220.
- ICALP-1989-FeldmanINNRS #generative #modelling #on the #random
- On Dice and Coins: Models of Computation for Random Generation (DF, RI, MN, NN, SR, AS), pp. 319–340.
- STOC-1989-ImpagliazzoLL #generative #pseudo
- Pseudo-random Generation from one-way functions (RI, LAL, ML), pp. 12–24.
- STOC-1989-ImpagliazzoR #permutation
- Limits on the Provable Consequences of One-Way Permutations (RI, SR), pp. 44–61.