| Year |
Citation |
Score |
| 2018 |
Impagliazzo R, Kabanets V, Volkovich I. The power of natural properties as oracles Electronic Colloquium On Computational Complexity. 24: 23. DOI: 10.4230/Lipics.Ccc.2018.7 |
0.423 |
|
| 2018 |
Carmosino ML, Impagliazzo R, Lovett S, Mihajlin I. Hardness amplification for non-commutative arithmetic circuits Electronic Colloquium On Computational Complexity. 25: 16. DOI: 10.4230/Lipics.Ccc.2018.12 |
0.39 |
|
| 2014 |
Aaronson S, Impagliazzo R, Moshkovitz D. AM with multiple merlins Proceedings of the Annual Ieee Conference On Computational Complexity. 44-55. DOI: 10.1109/CCC.2014.13 |
0.314 |
|
| 2013 |
Beck C, Impagliazzo R. Strong ETH holds for regular resolution Proceedings of the Annual Acm Symposium On Theory of Computing. 487-494. DOI: 10.1145/2488608.2488669 |
0.312 |
|
| 2012 |
Impagliazzo R, Meka R, Zuckerman D. Pseudorandomness from shrinkage Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 111-119. DOI: 10.1145/3230630 |
0.388 |
|
| 2012 |
Beame P, Beck C, Impagliazzo R. Time-space tradeoffs in resolution: Superpolynomial lower bounds for superlinear space Proceedings of the Annual Acm Symposium On Theory of Computing. 213-231. DOI: 10.1137/130914085 |
0.315 |
|
| 2012 |
Impagliazzo R, Kabanets V, Wigderson A. New direct-product testers and 2-query PCPs Siam Journal On Computing. 41: 1722-1768. DOI: 10.1137/09077299X |
0.403 |
|
| 2011 |
Buresh-Oppenheim J, Davis S, Impagliazzo R. A stronger model of dynamic programming algorithms Algorithmica (New York). 60: 938-968. DOI: 10.1007/S00453-009-9385-1 |
0.638 |
|
| 2011 |
Alekhnovich M, Borodin A, Buresh-Oppenheim J, Impagliazzo R, Magen A, Pitassi T. Toward a Model for Backtracking and Dynamic Programming Computational Complexity. 20: 679-740. DOI: 10.1007/S00037-011-0028-Y |
0.312 |
|
| 2010 |
Beame P, Impagliazzo R, Pitassi T, Segerlind N. Formula caching in DPLL Acm Transactions On Computation Theory. 1. DOI: 10.1145/1714450.1714452 |
0.717 |
|
| 2010 |
Calabro C, Impagliazzo R, Paturi R. On the exact complexity of evaluating quantified k-CNF Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6478: 50-59. DOI: 10.1007/S00453-012-9648-0 |
0.45 |
|
| 2010 |
Ben-Sasson E, Impagliazzo R. Random CNF'S are hard for the polynomial calculus Computational Complexity. 19: 501-519. DOI: 10.1007/S00037-010-0293-1 |
0.373 |
|
| 2009 |
Impagliazzo R, Jaiswal R, Kabanets V. Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification Siam Journal On Computing. 39: 564-605. DOI: 10.1137/070683994 |
0.621 |
|
| 2009 |
Impagliazzo R, Jaiswal R, Kabanets V. Chernoff-type direct product theorems Journal of Cryptology. 22: 75-92. DOI: 10.1007/S00145-008-9029-7 |
0.509 |
|
| 2008 |
Impagliazzo R, Jaiswal R, Kabanets V, Wigderson A. Uniform direct product theorems: Simplified, optimized, and derandomized Proceedings of the Annual Acm Symposium On Theory of Computing. 579-588. DOI: 10.1137/080734030 |
0.629 |
|
| 2008 |
Fortnow L, Impagliazzo R, Kabanets V, Umans C. On the complexity of succinct zero-sum games Computational Complexity. 17: 353-376. DOI: 10.1007/S00037-008-0252-2 |
0.371 |
|
| 2007 |
Beame P, Impagliazzo R, Sabharwal A. The resolution complexity of independent sets and vertex covers in random graphs Computational Complexity. 16: 245-297. DOI: 10.1007/S00037-007-0230-0 |
0.457 |
|
| 2006 |
Impagliazzo R, Segerlind N. Constant-depth frege systems with counting axioms polynomially simulate nullstellensatz refutations Acm Transactions On Computational Logic. 7: 199-218. DOI: 10.1145/1131313.1131314 |
0.704 |
|
| 2006 |
Impagliazzo R, Jaiswal R, Kabanets V. Approximately list-decoding direct product codes and uniform hardness amplification Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 187-196. DOI: 10.1109/FOCS.2006.13 |
0.571 |
|
| 2006 |
Impagliazzo R, Shaltiel R, Wigderson A. Reducing the seed length in the Nisan-Wigderson generator Combinatorica. 26: 647-681. DOI: 10.1007/S00493-006-0036-8 |
0.396 |
|
| 2004 |
Barak B, Impagliazzo R, Wigderson A. Extracting randomness using few independent sources Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 384-393. DOI: 10.1137/S0097539705447141 |
0.386 |
|
| 2004 |
Ben-Sasson E, Impagliazzo R, Wigderson A. Near optimal separation of tree-like and general resolution Combinatorica. 24: 585-603. DOI: 10.1007/S00493-004-0036-5 |
0.381 |
|
| 2003 |
Calabro C, Impagliazzo R, Kabanets V, Paturi R. The complexity of unique k-SAT: An isolation lemma for k-CNFs Proceedings of the Annual Ieee Conference On Computational Complexity. 135-141. DOI: 10.1016/J.Jcss.2007.06.015 |
0.415 |
|
| 2003 |
Impagliazzo R, Kapron BM. Logics for reasoning about cryptographic constructions Annual Symposium On Foundations of Computer Science - Proceedings. 372-383. DOI: 10.1016/J.Jcss.2005.06.008 |
0.355 |
|
| 2003 |
Beame P, Impagliazzo R, Pitassi T, Segerlind N. Memoization and DPLL: Formula caching proof systems Proceedings of the Annual Ieee Conference On Computational Complexity. 248-259. |
0.365 |
|
| 2002 |
Segerlind N, Buss S, Impagliazzo R. A switching lemma for small restrictions and lower bounds for k-DNF resolution Annual Symposium On Foundations of Computer Science - Proceedings. 604-613. DOI: 10.1137/S0097539703428555 |
0.702 |
|
| 2002 |
Buresh-Oppenheim J, Clegg M, Impagliazzo R, Pitassi T. Homogenization and the polynomial calculus Computational Complexity. 11: 91-108. DOI: 10.1007/S00037-002-0171-6 |
0.409 |
|
| 2002 |
Impagliazzo R, Segerlind N. Bounded-depth frege systems with counting axioms polynomially simulate Nullstellensatz refutations Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2380: 208-219. |
0.303 |
|
| 2001 |
Barak B, Goldreich O, Impagliazzo R, Rudich S, Sahai A, Vadhan S, Yang K. On the (Im)possibility of obfuscating programs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2139: 1-18. DOI: 10.1145/2160158.2160159 |
0.588 |
|
| 2001 |
Edmonds J, Impagliazzo R, Rudich S, Sgall J. Communication complexity towards lower bounds on circuit depth Computational Complexity. 10: 210-246. DOI: 10.1007/S00037-001-8195-X |
0.635 |
|
| 2001 |
Agrawal M, Allender E, Impagliazzo R, Pitassi T, Rudich S. Reducing the complexity of reductions Computational Complexity. 10: 117-138. DOI: 10.1007/S00037-001-8191-1 |
0.605 |
|
| 2001 |
Impagliazzo R, Wigderson A. Randomness vs time: Derandomization under a uniform assumption Journal of Computer and System Sciences. 63: 672-688. DOI: 10.1006/Jcss.2001.1780 |
0.427 |
|
| 2001 |
Impagliazzo R, Paturi R, Zane F. Which problems have strongly exponential complexity? Journal of Computer and System Sciences. 63: 512-530. DOI: 10.1006/Jcss.2001.1774 |
0.504 |
|
| 2001 |
Impagliazzo R, Paturi R. On the complexity of k-SAT Journal of Computer and System Sciences. 62: 367-375. DOI: 10.1006/jcss.2000.1727 |
0.301 |
|
| 2001 |
Beame P, Impagliazzo R, Sabharwal A. Resolution complexity of independent sets in random graphs Proceedings of the Annual Ieee Conference On Computational Complexity. 52-68. |
0.321 |
|
| 2001 |
Impagliazzo R, Segerlind N. Counting axioms do not polynomially simulate counting gates Annual Symposium On Foundations of Computer Science - Proceedings. 200-209. |
0.323 |
|
| 1999 |
Håstad J, Impagliazzo R, Levin LA, Luby M. Pseudorandom generator from any one-way function Siam Journal On Computing. 28: 1364-1396. DOI: 10.1137/S0097539793244708 |
0.309 |
|
| 1999 |
Impagliazzo R, Pudlák P, Sgall J. Lower bounds for the polynomial calculus and the Gröbner basis algorithm Computational Complexity. 8: 127-144. DOI: 10.1007/S000370050024 |
0.422 |
|
| 1998 |
Beame P, Impagliazzo R, Pitassi T. Improved depth lower bounds for small distance connectivity Computational Complexity. 7: 325-345. DOI: 10.1007/S000370050014 |
0.43 |
|
| 1998 |
Beame P, Cook S, Edmonds J, Impagliazzo R, Pitassi T. The Relative Complexity of NP Search Problems Journal of Computer and System Sciences. 57: 3-19. DOI: 10.1006/Jcss.1998.1575 |
0.325 |
|
| 1997 |
Gupta A, Impagliazzo R. Bounding the size of planar intertwines Siam Journal On Discrete Mathematics. 10: 337-358. DOI: 10.1137/S0895480192239931 |
0.316 |
|
| 1997 |
Impagliazzo R, Paturi R, Saks ME. Size-depth tradeoffs for threshold circuits Siam Journal On Computing. 26: 693-707. DOI: 10.1137/S0097539792282965 |
0.413 |
|
| 1997 |
Cook S, Impagliazzo R, Yamakami T. A Tight Relationship between Generic Oracles and Type-2 Complexity Theory Information and Computation. 137: 159-170. DOI: 10.1006/Inco.1997.2646 |
0.308 |
|
| 1996 |
Beame P, Impagliazzo R, Krajíček J, Pitassi T, Pudlák P. Lower bounds on Hilbert's Nullstellensatz and propositional proofs Proceedings of the London Mathematical Society. 73: 1-26. DOI: 10.1112/Plms/S3-73.1.1 |
0.405 |
|
| 1996 |
Buss SR, Krajíček J, Pudlák P, Sgall J, Impagliazzo R, Razborov AA. Proof complexity in algebraic systems and bounded depth frege systems with modular counting Computational Complexity. 6: 256-298. DOI: 10.1007/Bf01294258 |
0.451 |
|
| 1996 |
Impagliazzo R, Naor M. Efficient cryptographic schemes provably as secure as subset sum Journal of Cryptology. 9: 199-216. DOI: 10.1007/Bf00189260 |
0.566 |
|
| 1996 |
Fich FE, Impagliazzo R, Kapron B, King V, Kutyłowski M. Limits on the power of parallel random access machines with weak forms of write conflict resolution Journal of Computer and System Sciences. 53: 104-111. DOI: 10.1006/Jcss.1996.0052 |
0.388 |
|
| 1996 |
Jakobsson M, Sako K, Impagliazzo R. Designated verifier proofs and their applications Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1070: 143-154. |
0.451 |
|
| 1993 |
Pitassi T, Beame P, Impagliazzo R. Exponential lower bounds for the pigeonhole principle Computational Complexity. 3: 97-140. DOI: 10.1007/Bf01200117 |
0.441 |
|
| 1993 |
Feldman D, Impagliazzo R, Naor M, Nisan N, Rudich S, Shamir A. On Dice and Coins: Models of Computation for Random Generation Information and Computation. 104: 159-174. DOI: 10.1006/Inco.1993.1028 |
0.701 |
|
| 1993 |
Impagliazzo R, Nisan N. The effect of random restrictions on formula size Random Structures and Algorithms. 4: 121-133. DOI: 10.1002/Rsa.3240040202 |
0.395 |
|
| Show low-probability matches. |