| Home Talks Publications Conferences |
| Author | Title | Year | Journal/Proceedings | Reftype | DOI/URL |
|---|---|---|---|---|---|
| Pervyshev, K. | On Heuristic Time Hierarchies | 2007 | Computational Complexity (To appear) | inproceedings | |
| Russell Impagliazzo | Can every randomized algorithm be derandomized? | 2006 | STOC | inproceedings | DOI |
| Chris Calabro, Russell Impagliazzo & Ramamohan Paturi | A Duality between Clause Width and Clause Density for SAT | 2006 | Computational Complexity | inproceedings | DOI |
| Yi-Kai Liu, Vadim Lyubashevsky & Daniele Micciancio | On Bounded Distance Decoding for General Lattices | 2006 | RANDOM | inproceedings | DOI |
| Russell Impagliazzo & Nathan Segerlind | Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations | 2006 | ACM Trans. Comput. Logic | article | DOI |
| Russell Impagliazzo, Ragesh Jaiswal & Valentine Kabanets | Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification | 2006 | FOCS'06 | inproceedings | |
| J. Ma, K. Levchenko, C. Kreibich, S. Savage & G. M. Voelker | Unexpected Means of Protocol Inference | 2006 | Proceedings of the Internet Measurement Conference (to appear) | inproceedings | |
| J. Mao, R. Tarjan, B. Zhang & Y. Zhou | Balancing Applied to Maximum Network Flow Problems | 2006 | European Symposium on Algorithms (ESA) | inproceedings | DOI |
| Sashka Davis, Jeff Edmonds & Russell Impagliazzo | Online Algorithms to Minimize Resource Reallocation and Network Communication | 2006 | APPROX | inproceedings | DOI |
| Vadim Lyubashevsky & Daniele Micciancio | Generalized compact knapsacks are collision resistant | 2006 | ICALP | inproceedings | DOI |
| Yi-Kai Liu | Consistency of Local Density Matrices Is QMA-Complete | 2006 | RANDOM | inproceedings | |
| Russell Impagliazzo & Bruce M. Kapron | Logics for reasoning about cryptographic constructions | 2006 | Journal of Comput. Syst. Sci. | article | |
| Reid Andersen, Fan Chung & Kevin Lang | Local Graph Partitioning using PageRank Vectors | 2006 | FOCS'06 | inproceedings | |
| Russell Impagliazzo | Computational Complexity Since 1980. | 2005 | FSTTCS | inproceedings | DOI |
| Ramamohan Paturi, Pavel Pudl�k, Michael E. Saks & Francis Zane | An improved exponential-time algorithm for k-SAT. | 2005 | Journal of ACM | article | DOI |
| Daniele Micciancio, Shien Jin Ong, Amit Sahai & Salil P. Vadhan | Concurrent Zero Knowledge without Complexity Assumptions. | 2005 | ECCC | inproceedings | |
| Alan Nash, Jeffrey B. Remmel & Victor Vianu | PTIME Queries Revisited | 2005 | ICDT | inproceedings | DOI |
| A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan & M. Strauss | Improved Range-Summable Random Variable Construction Algorithms | 2005 | SODA | inproceedings | DOI |
| Vadim Lyubashevsky | The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem | 2005 | RANDOM | inproceedings | DOI |
| F. Chung, R. Graham, J. Mao & A. C. Yao | Oblivious Strategies in the Majority and Plurality Problems | 2005 | Computing and CombinatoricsCOCOON | inproceedings | DOI |
| Daniele Micciancio | The RSA Group is Pseudo-Free | 2005 | EUROCRYPT | inproceedings | DOI |
| Valentine kabanets & Russell Impagliazzo | Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds | 2004 | Computational Complexity | article | |
| A. Gilbert & K. Levchenko | Compressing Network Graphs | 2004 | Proc. of the LinkKDD Workshop at the Tenth ACM Conference on Knowledge Discovery and Data Mining | article | |
| Daniele Micciancio | Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor | 2004 | SIAM J. Comput. | article | DOI |
| Kirill Levchenko, Ramamohan Paturi & George Varghese | On the difficulty of scalably detecting network attacks | 2004 | ACM Comference on Computer and Communications Security | inproceedings | DOI |
| Ramamohan Paturi & Pavel Pudlak | Circuit lower bounds and linear codes | 2004 | ECCC | article | DOI |
| Daniele Micciancio & Oded Regev | Worst-Case to Average-Case Reductions Based on Gaussian Measures | 2004 | FOCS | inproceedings | |
| Charless Fowlkes, Serge Belongie, Fan Chung & Jitendra Malik | Spectral Grouping Using the Nystrom Method | 2004 | IEEE Trans. Pattern Anal. Mach. Intell. | article | |
| Reid Anderson, Fan Chung & Lincoln Lu | Analyzing the Small World Phenomenon Using a Hybrid Model with Local Network Flow | 2004 | WAW | inproceedings | |
| Venkatesh Guruswami, Daniele Micciancio & Oded Regev | The Complexity of the Covering Radius Problem on Lattices and Codes | 2004 | IEEE Conference on Computational Complexity | inproceedings | |
| Fan Chung & Joshua N. Cooper | De Bruijn cycles for covering codes | 2004 | Random Struct. Algorithms | article | |
| Fan Chung, Ronald Graham & George Verghese | Parallelism versus memory allocation in pipelined router forwarding engines | 2004 | SPAA | inproceedings | |
| Lance Fortnow, Russell Impagliazzo, Valentine Kabanets & Christopher Umans | On the complexity of succinct zero-sum games | 2004 | ECCC | article | |
| Reid Anderson, Fan Chung, Arunabha Sen & Guoliang Xue | On Disjoint Path Pairs with Wavelength Continuity Constraint in WDM Networks | 2004 | INFOCOM | inproceedings | |
| Sashka Davis & Russell Impagliazzo | Models of greedy algorithms for graph problems | 2004 | SODA | inproceedings | |
| Reid Anderson, Fan Chung & Lincoln Lu | Drawing Power Law Graphs | 2004 | Graph Drawing | article | |
| Boaz Barak, Russell Impagliazzo & Avi Wigderson | Extracting Randomness Using Few Independent Sources | 2004 | FOCS | inproceedings | |
| Nathan Segerlind, Samuel R. Buss & Russell Impagliazzo | A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution | 2004 | SIAM J. Comput. | article | |
| Eli Ben-Sasson, Russell Impagliazzo & Avi Wigderson | Near Optimal Separation Of Tree-Like And General Resolution | 2004 | Combinatorica | article | |
| Russell Impagliazzo & Philippe Moser | A zero one law for RP | 2003 | IEEE Conference on Computational Complexity | inproceedings | |
| Russell Impagliazzo & Nathan Segerlind | Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations | 2003 | CoRR | inproceedings | |
| Alan Nash, Russell Impagliazzo & Jeffrey B. Remmel | Universal Languages and the Power of Diagonalization | 2003 | IEEE Conference on Computational Complexity | inproceedings | |
| Daniele Micciancio | A Note on the Minimal Volume of Almost Cubic Parallelepipeds | 2003 | Discrete and Computational Geometry | article | |
| Fan R. K. Chung, Ronald L. Graham, Jia Mao & Andrew Chi-Chih Yao | Finding Favorites | 2003 | ECCC | article | |
| Russell Impagliazzo & Bruce M. Kapron | Logics for Reasoning about Cryptographic Constructions | 2003 | FOCS | inproceedings | |
| Paul Beame, Russell Impagliazzo, Toniann Pitassi & Nathan Segerlind | Memoization and DPLL: Formula Caching Proof Systems | 2003 | IEEE Conference on Computational Complexity | inproceedings | |
| Daniele Micciancio & Salil P. Vadhan | Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More | 2003 | CRYPTO | inproceedings | |
| Russell Impagliazzo & Sara Miner More | Anonymous credentials with biometrically-enforced non-transferability | 2003 | WPES | inproceedings | |
| Sanjoy Dasgupta & Anupam Gupta | An elementary proof of a theorem of Johnson and Lindenstrauss | 2003 | Random Struct. Algorithms | article | |
| Valentine Kabanets & Russell Impagliazzo | Derandomizing polynomial identity tests means proving circuit lower bounds | 2003 | STOC | inproceedings | |
| Russell Impagliazzo | Hardness as randomness: a survey of universal derandomization | 2003 | CoRR | article | |
| Victor Vianu | Logic as a Query Language: From Frege to XML | 2003 | STACS | inproceedings | |
| Daniele Micciancio | Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor | 2003 | ECCC | article | |
| Chris Calabro, Russell Impagliazzo, Valentine Kabanets & Ramamohan Paturi | The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs | 2003 | IEEE Conference on Computational Complexity | inproceedings | |
| Ilya Dumer, Daniele Micciancio & Madhu Sudan | Hardness of approximating the minimum distance of a linear code | 2003 | IEEE Transaction on Information Theory | article |
Created by JabRef on 26/02/2007.