BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
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 DBLP: Impagliazzo:Russell

Contributed to:

STOC 20132013
STOC 20122012
STOC 20092009
STOC 20082008
STOC 20062006
STOC 20032003
ICALP 20022002
ICALP 20002000
STOC 20002000
STOC 19991999
STOC 19971997
STOC 19961996
STOC 19951995
LICS 19941994
STOC 19941994
STOC 19931993
STOC 19921992
ICALP 19891989
STOC 19891989

Wrote 24 papers:

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.
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.
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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.