default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRussell Impagliazzo
Person information
- affiliation: University of California, San Diego, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i58]Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye:
Replicability in High Dimensional Statistics. CoRR abs/2406.02628 (2024)- [i57]Shreya Gupta, Boyang Huang, Russell Impagliazzo, Stanley Woo, Christopher Ye:
The Computational Complexity of Factored Graphs. CoRR abs/2407.19102 (2024) - 2023
- [j52]Russell Impagliazzo
, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. Comput. Complex. 32(2): 6 (2023) - [c119]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM 2023: 31:1-31:21 - [c118]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC 2023: 7:1-7:24 - [c117]Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. ITCS 2023: 30:1-30:40 - [c116]Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell:
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. STOC 2023: 520-527 - [i56]Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell:
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. CoRR abs/2303.12921 (2023) - [i55]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j51]Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina:
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. Algorithmica 84(11): 3156-3191 (2022) - [c115]Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in learning. STOC 2022: 818-831 - [i54]Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in Learning. CoRR abs/2201.08430 (2022) - [i53]Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. Electron. Colloquium Comput. Complex. TR22 (2022) - [i52]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower bounds for Polynomial Calculus with extension variables over finite fields. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c114]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. CCC 2021: 6:1-6:30 - [c113]Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam:
On the Pseudo-Deterministic Query Complexity of NP Search Problems. CCC 2021: 36:1-36:22 - [c112]Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos:
Boosting in the Presence of Massart Noise. COLT 2021: 1585-1644 - [c111]Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Lifting for Constant-Depth Circuits and Applications to MCSP. ICALP 2021: 44:1-44:20 - [c110]Russell Impagliazzo, Sam McGuire:
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). ITCS 2021: 2:1-2:20 - [c109]Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina:
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. IPEC 2021: 3:1-3:15 - [i51]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. CoRR abs/2102.05019 (2021) - [i50]Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica Sorrell, Christos Tzamos:
Boosting in the Presence of Massart Noise. CoRR abs/2106.07779 (2021) - [i49]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c108]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. LICS 2020: 591-603 - [i48]Russell Impagliazzo, Sam McGuire:
Comparing computational entropies below majority (or: When is the dense model theorem false?). CoRR abs/2011.06166 (2020) - [i47]Russell Impagliazzo, Sam McGuire:
Comparing computational entropies below majority (or: When is the dense model theorem false?). Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j50]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. J. ACM 66(2): 11:1-11:16 (2019) - [j49]Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams:
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms 15(2): 23:1-23:35 (2019) - [c107]Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds Against MCSP via the Coin Problem. ICALP 2019: 66:1-66:15 - [i46]Anant Dhayal, Russell Impagliazzo:
UTIME Easy-witness Lemma & Some Consequences. Electron. Colloquium Comput. Complex. TR19 (2019) - [i45]Jiawei Gao, Russell Impagliazzo:
The Fine-Grained Complexity of Strengthenings of First-Order Logic. Electron. Colloquium Comput. Complex. TR19 (2019) - [i44]Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds against MCSP via the Coin Problem. Electron. Colloquium Comput. Complex. TR19 (2019) - [i43]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c106]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. CCC 2018: 7:1-7:20 - [c105]Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. CCC 2018: 12:1-12:16 - [c104]Marco L. Carmosino, Russell Impagliazzo, Manuel Sabin:
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. ICALP 2018: 27:1-27:16 - [c103]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. ITCS 2018: 10:1-10:20 - [c102]Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander V. Smal:
Half-Duplex Communication Complexity. ISAAC 2018: 10:1-10:12 - [i42]Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin:
Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - [i41]Marco Carmosino, Russell Impagliazzo, Manuel Sabin:
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity. Electron. Colloquium Comput. Complex. TR18 (2018) - [i40]Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal:
Half-duplex communication complexity. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j48]Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. Comput. Complex. 26(1): 275-321 (2017) - [c101]Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM 2017: 35:1-35:19 - [c100]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help?. MFCS 2017: 1:1-1:13 - [c99]Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams:
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. SODA 2017: 2162-2181 - [i39]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. CoRR abs/1710.03219 (2017) - [i38]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. Electron. Colloquium Comput. Complex. TR17 (2017) - [i37]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. TR17 (2017) - [i36]Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j47]Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. SIAM J. Comput. 45(4): 1612-1645 (2016) - [c98]Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness When the Odds are Against You. CCC 2016: 9:1-9:35 - [c97]Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Learning Algorithms from Natural Proofs. CCC 2016: 10:1-10:24 - [c96]Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider:
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. ITCS 2016: 261-270 - [c95]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro:
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. TCC (B1) 2016: 235-261 - [i35]Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness when the odds are against you. Electron. Colloquium Comput. Complex. TR16 (2016) - [i34]Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Algorithms from Natural Lower Bounds. Electron. Colloquium Comput. Complex. TR16 (2016) - [i33]Jiawei Gao, Russell Impagliazzo:
Orthogonal Vectors is hard for first-order properties on sparse graphs. Electron. Colloquium Comput. Complex. TR16 (2016) - [i32]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro:
Simultaneous Secrecy and Reliability Amplification for a General Channel Model. IACR Cryptol. ePrint Arch. 2016: 760 (2016) - 2015
- [c94]Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Tighter Connections between Derandomization and Circuit Lower Bounds. APPROX-RANDOM 2015: 645-658 - [i31]Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider:
Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j46]Russell Impagliazzo, Cristopher Moore, Alexander Russell:
An Entropic Proof of Chang's Inequality. SIAM J. Discret. Math. 28(1): 173-176 (2014) - [c93]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CCC 2014: 44-55 - [c92]Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. CCC 2014: 321-332 - [i30]Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. CoRR abs/1401.5512 (2014) - [i29]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CoRR abs/1401.6848 (2014) - [i28]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. TR14 (2014) - [i27]Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j45]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
On the Exact Complexity of Evaluating Quantified k -CNF. Algorithmica 65(4): 817-827 (2013) - [c91]Lucia Batman, Russell Impagliazzo, Cody Murray, Ramamohan Paturi:
Finding Heavy Hitters from Lossy or Noisy Data. APPROX-RANDOM 2013: 347-362 - [c90]Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider:
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. FOCS 2013: 479-488 - [c89]Russell Impagliazzo, Ramamohan Paturi:
Exact Complexity and Satisfiability - (Invited Talk). IPEC 2013: 1-3 - [c88]Christopher Beck, Russell Impagliazzo:
Strong ETH holds for regular resolution. STOC 2013: 487-494 - [i26]Russell Impagliazzo, Valentine Kabanets:
Fourier Concentration from Shrinkage. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j44]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (im)possibility of obfuscating programs. J. ACM 59(2): 6:1-6:48 (2012) - [j43]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput. 41(6): 1722-1768 (2012) - [c87]Paul Beame, Russell Impagliazzo, Srikanth Srinivasan:
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. CCC 2012: 117-125 - [c86]Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. FOCS 2012: 101-110 - [c85]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. FOCS 2012: 111-119 - [c84]Russell Impagliazzo, William Matthews, Ramamohan Paturi:
A satisfiability algorithm for AC0. SODA 2012: 961-972 - [c83]Paul Beame, Christopher Beck, Russell Impagliazzo:
Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. STOC 2012: 213-232 - [i25]Russell Impagliazzo, Cristopher Moore, Alexander Russell:
An Entropic Proof of Chang's Inequality. CoRR abs/1205.0263 (2012) - [i24]Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider:
A Satisfiability Algorithm for Sparse Depth-2 Threshold Circuits. CoRR abs/1212.4548 (2012) - [i23]Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Electron. Colloquium Comput. Complex. TR12 (2012) - [i22]Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j42]Joshua Buresh-Oppenheim, Sashka Davis, Russell Impagliazzo:
A Stronger Model of Dynamic Programming Algorithms. Algorithmica 60(4): 938-968 (2011) - [j41]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20(4): 679-740 (2011) - [c82]Russell Impagliazzo:
Relativized Separations of Worst-Case and Average-Case Complexities for NP. CCC 2011: 104-114 - [i21]Russell Impagliazzo, William Matthews, Ramamohan Paturi:
A Satisfiability Algorithm for AC$^0$. CoRR abs/1107.3127 (2011) - [i20]Paul Beame, Chris Beck, Russell Impagliazzo:
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j40]Eli Ben-Sasson, Russell Impagliazzo:
Random Cnf's are Hard for the Polynomial Calculus. Comput. Complex. 19(4): 501-519 (2010) - [j39]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637-1665 (2010) - [j38]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. ACM Trans. Comput. Theory 1(3): 9:1-9:33 (2010) - [c81]Russell Impagliazzo, Valentine Kabanets:
Constructive Proofs of Concentration Bounds. APPROX-RANDOM 2010: 617-631 - [c80]Russell Impagliazzo, Ryan Williams:
Communication Complexity with Synchronized Clocks. CCC 2010: 259-269 - [c79]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
On the Exact Complexity of Evaluating Quantified k-CNF. IPEC 2010: 50-59 - [i19]Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer:
Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex. TR10 (2010) - [i18]Russell Impagliazzo, Valentine Kabanets:
Constructive Proofs of Concentration Bounds. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j37]Sashka Davis, Russell Impagliazzo:
Models of Greedy Algorithms for Graph Problems. Algorithmica 54(3): 269-317 (2009) - [j36]Russell Impagliazzo, Philippe Moser:
A zero-one law for RP and derandomization of AM if NP is not small. Inf. Comput. 207(7): 787-792 (2009) - [j35]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Chernoff-Type Direct Product Theorems. J. Cryptol. 22(1): 75-92 (2009) - [j34]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. SIAM J. Comput. 39(2): 564-605 (2009) - [c78]Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
The Complexity of Satisfiability of Small Depth Circuits. IWPEC 2009: 75-85 - [c77]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New direct-product testers and 2-query PCPs. STOC 2009: 131-140 - [c76]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
An axiomatic approach to algebrization. STOC 2009: 695-704 - [c75]Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Security Amplification for InteractiveCryptographic Primitives. TCC 2009: 128-145 - [i17]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
An Axiomatic Approach to Algebrization. Algebraic Methods in Computational Complexity 2009 - [i16]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen:
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. TR09 (2009) - [i15]Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New Direct-Product Testers and 2-Query PCPs. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j33]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17(3): 353-376 (2008) - [j32]Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi:
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. J. Comput. Syst. Sci. 74(3): 386-393 (2008) - [c74]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform direct product theorems: simplified, optimized, and derandomized. STOC 2008: 579-588 - [i14]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j31]Paul Beame, Russell Impagliazzo, Ashish Sabharwal:
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Comput. Complex. 16(3): 245-297 (2007) - [c73]Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
Chernoff-Type Direct Product Theorems. CRYPTO 2007: 500-516 - 2006
- [j30]Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
Reducing The Seed Length In The Nisan-Wigderson Generator. Comb. 26(6): 647-681 (2006) - [j29]Russell Impagliazzo, Bruce M. Kapron:
Logics for reasoning about cryptographic constructions. J. Comput. Syst. Sci. 72(2): 286-320 (2006) - [j28]Boaz Barak, Russell Impagliazzo, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. SIAM J. Comput. 36(4): 1095-1118 (2006) - [j27]Russell Impagliazzo, Nathan Segerlind:
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. ACM Trans. Comput. Log. 7(2): 199-218 (2006) - [c72]Sashka Davis, Jeff Edmonds, Russell Impagliazzo:
Online Algorithms to Minimize Resource Reallocations and Network Communication. APPROX-RANDOM 2006: 104-115 - [c71]