Skip to Content

Algorithms and Complexity - Publications Archive

Export / Filter

2012

Efficient and Optimally Secure Key-Length Extension for Block Ciphers via Randomized Cascading, Peter Gazi, and Stefano Tessaro, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012).
Identity-Based (Lossy) Trapdoor Functions and Applications, Mihir Bellare, Eike Kiltz, Chris Peikert, and Brent Waters, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012). PDF
Malleable Proof Systems and Applications, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Sarah Meiklejohn, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012).
Standard Security Does Not Imply Security Against Selective-Opening, Mihir Bellare, Rafael Dowsley, Brent Waters, and Scott Yilek, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012). PDF
Trapdoor for Lattices: Simpler, Tighter, Faster, Smaller, Daniele Micciancio, and Chris Peikert, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012).

2011

Achieving Oblivious Transfer Capacity of Generalized Erasure Channel in the Malicious Model, Adriana C. B. Pinto, Rafael Dowsley, Kirill Morozov, and Anderson C. A. Nascimento, IEEE Transactions on Information Theory, Volume 57, Number 8, p.5566-71, (2011). PDF
Authenticated and Misuse-Resistant Encryption of Key-Dependent Data, Mihir Bellare, and Sriram Keelveedhi; Phil Rogaway, eds., Proceedings of Crypto 2011, August, Santa Barbara, CA, (2011). LNCS. PDF
Ciphers that Encipher their Own Keys, Mihir Bellare, David Cash, and Sriram Keelveedhi, Proceedings of the ACM Conference on Computer and Communications Security (CCS), October 2011, Chicago, IL, (2011). PDF
Cryptography Secure Against Related-Key Attack, Mihir Bellare, David Cash, and Rachel Miller, Proceedings of Asiacrypt (AC11), Dec. 2011, Seoul, Korea, (2011). PDF
Efficient Authentication from Hard Learning Problems, Eike Kiltz, Krzysztof Pietrzak, David Cash, Abhishek Jain, and Daniele Venturi; Kenny Paterson, eds., Proceedings of Eurocrypt 2011, May, Tallinn, Estonia, (2011). LNCS.
Identity-Based Encryption Secure Against Selective Opening Attack, Mihir Bellare, Brent Waters, and Scott Yilek; Yuval Ishai, eds., Proceedings of TCC 2011, March, Providence, Rhode Island, (2011). LNCS.
Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions, Daniele Micciancio, and Petros Mol; Phillip Rogaway, eds., CRYPTO 2011 - Proceedings, Volume 6841, p.465-484, (2011). Lecture Notes in Computer Science. URL
Security Amplification for the Cascade of Arbitrarily Weak PRPs: Tight Bounds via the Interactive Hardcore Lemma, Stefano Tessaro; Yuval Ishai, eds., Proceedings of TCC 2011, March, Providence, Rhode Island, (2011). LNCS.
The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited, Thomas Holenstein, Robin Künzler, and Stefano Tessaro; Salil Vadhan, eds., 43rd Annual ACM Symposium on Theory of Computing, June, San Jose, CA, (2011). PDF
The Geometry of Lattice Cryptography, Daniele Micciancio; Alessandro Aldini, and Roberto Gorrieri, eds., Foundations of Security Analysis and Design VI - FOSAD Tutorial Lectures, Volume 6858, p.185-210, (2011). Lecture Notes in Computer Science. URL
Universally Composable and Statistically Secure Verifiable Secret Sharing Scheme Based on Pre-Distributed Data, Rafael Dowsley, Jöorn Müller-Quade, Akira Otsuka, Goichiro Hanaoka, Hideki Imai, and Anderson C. A. Nascimento, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Volume E94-A, Number 2, p.725-34, (2011). PDF

2010

A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations, Daniele Micciancio, and Panagiotis Voulgaris, Proceedings of the 42nd ACM symposium on Theory of computing, June, New York, NY, USA, p.351–358, (2010). STOC '10. Cambridge, Massachusetts, USA. URL
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations, Daniele Micciancio, and Panagiotis Voulgaris; Leonard Schulman, eds., 42nd Annual ACM Symposium on Theory of Computing, June, Cambridge, MA, (2010). PDF
Bonsai Trees, or How to Delegate a Lattice Basis, David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert; Henri Gilbert, eds., Proceedings of Eurocrypt 2010, May, Nice, France, (2010). LNCS.
application/pdf iconlattice-hibe.pdf
Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions, Petros Mol, and Scott Yilek; Phong Nguyen, and David Pointcheval, eds., Proceedings of PKC 2010, May, Paris, (2010). LNCS. PDF
Communication Complexity with Synchronized Clocks, Russell Impagliazzo, and Ryan Williams, Computational Complexity, Annual IEEE Conference on, June, Los Alamitos, CA, USA, p.259-269, (2010).
Computational Soundness, Co-Induction, and Encryption Cycles, Daniele Micciancio; Henri Gilbert, eds., Proceedings of Eurocrypt 2010, May, Volume 6110, Nice, France, p.362-380, (2010). LNCS. URL PDF
Constructive Proofs of Concentration Bounds, Russell Impagliazzo, and Valentine Kabanets; Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim, eds., Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Volume 6302, p.617-631, (2010). Lecture Notes in Computer Science. URL
Cryptographic Agility and Its Relation to Circular Encryption, Tolga Acar, Mira Belenkiy, Mihir Bellare, and David Cash; Henri Gilbert, eds., Proceedings of Eurocrypt 2010, May, Volume 6110, Nice, France, p.403-422, (2010). LNCS. URL PDF
Descent polynomials for permutations with bounded drop size, Fan Chung, Anders Claesson, Mark Dukes, and Ronald Graham, European Journal of Combinatorics, Volume 31, Number 7, p.1853 - 1867, (2010). URL
Exact Algorithms and Complexity, Ramamohan Paturi; Ofer Strichman, and Stefan Szeider, eds., Theory and Applications of Satisfiability Testing – SAT 2010, Volume 6175, p.8-9, (2010). Lecture Notes in Computer Science. URL
Faster Exponential Time Algorithms for the Shortest Vector Problem, Daniele Micciancio, and Panagiotis Voulgaris; Moses Charikar, eds., ACM-SIAM Symposium on Discrete Algorithms, January, Austin, TX, p.1468-80, (2010). SODA '10. Austin, Texas. URL PDF
Formula Caching in DPLL, Bea Paul, Russell Impagliazzo, Toniann Pitassi, and Nathan Segerlind, ACM Trans. Comput. Theory, March, Volume 1, New York, NY, USA, p.9:1–9:33, (2010). URL
How to play the Majority game with a liar, Steve Butler, Jia Mao, and Ron Graham, Discrete Mathematics, Volume 310, Number 3, p.622 - 629, (2010). Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. URL
Introduction to the Special Section on Internet and Network Economics, Xiaotie Deng, and Fan Graham, Algorithmica, Volume 58, p.928-929, (2010). URL
Irreducible Apollonian Configurations and Packings, Steve Butler, Ron Graham, Gerhard Guettler, and Colin Mallows, Discrete & Computational Geometry, Volume 44, p.487-507, (2010). URL
Low Memory Distributed Protocols for 2-Coloring, Amos Israeli, Mathew McCubbins, Ramamohan Paturi, and Andrea Vattani; Shlomi Dolev, Jorge Cobb, Michael Fischer, and Moti Yung, eds., Stabilization, Safety, and Security of Distributed Systems, Volume 6366, p.303-318, (2010). Lecture Notes in Computer Science. URL
On the complexity of circuit satisfiability, Ramamohan Paturi, and Pavel Pudlak, Proceedings of the 42nd ACM symposium on Theory of computing, June, New York, NY, USA, p.241–250, (2010). STOC '10. Cambridge, Massachusetts, USA. URL
Physical synthesis of bus matrix for high bandwidth low power on-chip communications, Renshen Wang, Evangeline F. Y. Young, Ronald Graham, and Chung-Kuan Cheng, Proceedings of the 19th international symposium on Physical design, New York, NY, USA, p.91–96, (2010). ISPD '10. San Francisco, California, USA. URL
Pseudorandom Functions and Permutations Provably Secure Against Related-Key Attacks, Mihir Bellare, and David Cash; Tal Rabin, eds., Proceedings of Crypto 2010, August, Volume 6223, Santa Barbara, CA, p.666-684, (2010). LNCS. URL PDF
application/pdf iconrka-crypto10.pdf
Random Oracles with(out) Programmability, Marc Fischlin, Anja Lehmann, Thomas Ristenpart, Thomas Shrimpton, Martijn Stam, and Stefano Tessaro; Masayuki Abe, eds., Proceedings of Asiacrypt 2010, December, Singapore, (2010). LNCS.
Robust Encryption, Michel Abdalla, Mihir Bellare, and Gregory Neven; Daniele Micciancio, eds., Proceedings of TCC 2010, March, Volume 5978, Zurich, p.480-97, (2010). LNCS. URL PDF
The RSA Group is Pseudo-Free, Daniele Micciancio, Journal of Cryptology, April, Volume 23, Number 2, p.169-86, (2010). PDF
Tiling Polygons with Lattice Triangles, Steve Butler, Fan Chung, Ron Graham, and Miklós Laczkovich, Discrete & Computational Geometry, Volume 44, p.896-903, (2010). URL
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson, SIAM Journal on Computing, January, Volume 39, Number 4, Philadelphia, PA, USA, p.1637-65, (2010). URL
application/pdf iconIJKW-Full.pdf
Uniquely Satisfiable k-SAT Instances with Almost Minimal Occurrences of Each Variable, William Matthews, and Ramamohan Paturi; Ofer Strichman, and Stefan Szeider, eds., Theory and Applications of Satisfiability Testing – SAT 2010, Volume 6175, p.369-374, (2010). Lecture Notes in Computer Science. URL
Views and queries: Determinacy and rewriting, Alan Nash, Luc Segoufin, and Victor Vianu, ACM Trans. Database Syst., July, Volume 35, New York, NY, USA, p.21:1–21:41, (2010). URL

2009

A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank, Fan Chung; Konstantin Avrachenkov, Debora Donato, and Nelly Litvak, eds., Algorithms and Models for the Web-Graph, Volume 5427, p.62-75, (2009). Lecture Notes in Computer Science. URL
A zero-one law for RP and derandomization of AM if NP is not small, Russell Impagliazzo, and Philippe Moser, Information and Computation, Volume 207, Number 7, p.787 - 792, (2009). URL
An axiomatic approach to algebrization, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova, Proceedings of the 41st annual ACM symposium on Theory of computing, New York, NY, USA, p.695–704, (2009). STOC '09. Bethesda, MD, USA. URL
Analysis of Perceptron-Based Active Learning, Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni, J. Mach. Learn. Res., June, Volume 10, p.281–299, (2009). URL PDF
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets, SIAM J. Comput., July, Volume 39, Philadelphia, PA, USA, p.564–605, (2009). URL
Approximately optimal trees for group key management with batch updates, Minming Li, Ze Feng, Nan Zang, Ronald L. Graham, and Frances F. Yao, Theoretical Computer Science, Volume 410, Number 11, p.1013 - 1021, (2009). [Algorithms, Complexity and Models of Computation] URL
Automatic verification of data-centric business processes, Alin Deutsch, Richard Hull, Fabio Patrizi, and Victor Vianu, Proceedings of the 12th International Conference on Database Theory, New York, NY, USA, p.252–267, (2009). ICDT '09. St. Petersburg, Russia. URL
Automatic verification of database-driven systems: a new frontier, Victor Vianu, Proceedings of the 12th International Conference on Database Theory, New York, NY, USA, p.1–13, (2009). ICDT '09. St. Petersburg, Russia. URL
Bubblesort and Juggling Sequences, Ronald Graham; Yingfei Dong, Ding-Zhu Du, and Oscar Ibarra, eds., Algorithms and Computation, Volume 5878, p.1-1, (2009). Lecture Notes in Computer Science. URL
Chernoff-Type Direct Product Theorems, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets, Journal of Cryptology, Volume 22, p.75-92, (2009). URL
Format-Preserving Encryption, Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers; Michael J. Jacobson, Vincent Rijmen, and Rei Safavi-Naini, eds., Proceedings of Selected Areas in Cryptography (SAC) 2009, August, (2009). Calgary, Canada. URL PDF
Hedged Public-Key Encryption: How to Protect Against Bad Randomness, Mihir Bellare, Zvika Brakerski, Moni Naor, Thomas Ristenpart, Gil Segev, Hovav Shacham, and Scott Yilek; Mitsuru Matsui, eds., Proceedings of Asiacrypt 2009, December, Volume 5912, Tokyo, p.232-249, (2009). LNCS. URL
k-SAT Is No Harder Than Decision-Unique-k-SAT, Chris Calabro, and Ramamohan Paturi; Anna Frid, Andrey Morozov, Andrey Rybalchenko, and Klaus Wagner, eds., Computer Science - Theory and Applications, Volume 5675, p.59-70, (2009). Lecture Notes in Computer Science. URL
Key Insulation and Intrusion Resilience over a Public Channel, Mihir Bellare, Shanshan Duan, and Adriana Palacio; Marc Fischlin, eds., Topics in Cryptology – CT-RSA 2009, Volume 5473, p.84-99, (2009). Lecture Notes in Computer Science. URL
Minimum perimeter rectangles that enclose congruent non-overlapping circles, Boris D. Lubachevsky, and Ronald L. Graham, Discrete Mathematics, Volume 309, Number 8, p.1947 - 1962, (2009). URL
Models of Greedy Algorithms for Graph Problems, Sashka Davis, and Russell Impagliazzo, Algorithmica, Volume 54, p.269-317, (2009). URL
New direct-product testers and 2-query PCPs, Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson, Proceedings of the 41st annual ACM symposium on Theory of computing, New York, NY, USA, p.131–140, (2009). STOC '09. Bethesda, MD, USA. URL
On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem, Vadim Lyubashevsky, and Daniele Micciancio; Shai Halevi, eds., Proceedings of Crypto 2009, August, Volume 5677, Santa Barbara, CA, p.577-594, (2009). LNCS. URL PDF
Packing equal squares into a large square, Fan Chung, and Ron Graham, Journal of Combinatorial Theory, Series A, Volume 116, Number 6, p.1167 - 1175, (2009). URL
Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening, Mihir Bellare, Dennis Hofheinz, and Scott Yilek; Antoine Joux, eds., Proceedings of Eurocrypt 2009, April, Volume 5479, Cologne, p.1-35, (2009). LNCS. URL
application/pdf iconBY-ec09full.pdf
Security Amplification for Interactive Cryptographic Primitives, Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets; Omer Reingold, eds., Theory of Cryptography, Volume 5444, p.128-145, (2009). Lecture Notes in Computer Science. URL
Security Proofs for Identity-Based Identification and Signature Schemes, Mihir Bellare, Chanathip Namprempre, and Gregory Neven, Journal of Cryptology, Volume 22, p.1-61, (2009). URL
Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters’ IBE Scheme, Mihir Bellare, and Thomas Ristenpart; Antoine Joux, eds., Advances in Cryptology - EUROCRYPT 2009, Volume 5479, p.407-424, (2009). Lecture Notes in Computer Science. URL
Static analysis of active XML systems, Serge Abiteboul, Luc Segoufin, and Victor Vianu, ACM Trans. Database Syst., December, Volume 34, New York, NY, USA, p.23:1–23:44, (2009). URL
The Complexity of Satisfiability of Small Depth Circuits, Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi; Jianer Chen, and Fedor Fomin, eds., Parameterized and Exact Computation, Volume 5917, p.75-85, (2009). Lecture Notes in Computer Science. URL
The Giant Component in a Random Subgraph of a Given Graph, Fan Chung, Paul Horn, and Linyuan Lu; Konstantin Avrachenkov, Debora Donato, and Nelly Litvak, eds., Algorithms and Models for the Web-Graph, Volume 5427, p.38-49, (2009). Lecture Notes in Computer Science. URL

2008

3-D floorplanning using labeled tree and dual sequences, Renshen Wang, Evangeline F. Y. Young, Yi Zhu, Fan Chung Graham, Ronald Graham, and Chung-Kuan Cheng, Proceedings of the 2008 international symposium on Physical design, New York, NY, USA, p.54–59, (2008). ISPD '08. Portland, Oregon, USA. URL
A general agnostic active learning algorithm, Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni; J. C. Platt, D. Koller, Y. Singer, and S. Roweis, eds., Advances in Neural Information Processing Systems 20, Cambridge, MA, p.353–360, (2008).
A learning framework for nearest neighbor search, Lawrence Cayton, and Sanjoy Dasgupta; J. C. Platt, D. Koller, Y. Singer, and S. Roweis, eds., Advances in Neural Information Processing Systems 20, Cambridge, MA, p.233–240, (2008).
A Network Coloring Game, Kamalika Chaudhuri, Fan Chung Graham, and Mohammad Jamall; Christos Papadimitriou, and Shuzhong Zhang, eds., Internet and Network Economics, Volume 5385, p.522-530, (2008). Lecture Notes in Computer Science. URL
An Indistinguishability-Based Characterization of Anonymous Channels, Alejandro Hevia, and Daniele Micciancio; Nikita Borisov, and Ian Goldberg, eds., Privacy Enhancing Technologies Symposium, July, Volume 5134, Number 5134, Leuven, Belgium, p.24-43, (2008). LNCS. URL PDF
Analysis of greedy approximations with nonsubmodular potential functions, Ding-Zhu Du, Ronald L. Graham, Panos M. Pardalos, Peng-Jun Wan, Weili Wu, and Wenbo Zhao, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, p.167–175, (2008). SODA '08. San Francisco, California. URL
Asymptotically Efficient Lattice-Based Digital Signatures, Vadim Lyubashevsky, and Daniele Micciancio; Ran Canetti, eds., Proceedings of TCC 2008, March, Volume 4948, New York, p.37-54, (2008). LNCS. URL PDF
Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm, Mihir Bellare, and Chanathip Namprempre, Journal of Cryptology, Volume 21, p.469-491, (2008). URL
Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles, Mihir Bellare, Marc Fischlin, Adam O'Neill, and Thomas Ristenpart; David Wagner, eds., Proceedings of Crypto 2008, August, Volume 5157, Santa Barbara, CA, p.360-78, (2008). LNCS. URL
Efficient Reductions among Lattice Problems, Daniele Micciancio; Shang-Hua Teng, eds., ACM-SIAM Symposium on Discrete Algorithms, January, San Francisco, CA, p.84-93, (2008). SODA '08. San Francisco, California. URL PDF
Enumerating split-pair arrangements, Ron Graham, and Nan Zang, Journal of Combinatorial Theory, Series A, Volume 115, Number 2, p.293 - 303, (2008). URL
From Identification to Signatures Via the Fiat #x2013;Shamir Transform: Necessary and Sufficient Conditions for Security and Forward-Security, M. Abdalla, Jee Hea An, M. Bellare, and C. Namprempre, Information Theory, IEEE Transactions on, August, Volume 54, Number 8, p.3631 -3646, (2008).
Hash Functions from Sigma Protocols and Improvements to VSH, Mihir Bellare, and Todor Ristov; Josef Pieprzyk, eds., Advances in Cryptology - ASIACRYPT 2008, Volume 5350, p.125-142, (2008). Lecture Notes in Computer Science. URL
Hierarchical sampling for active learning, S. Dasgupta, and D. Hsu; Andrew McCallum, and Sam Roweis, eds., Proceedings of the 25th Annual International Conference on Machine Learning (ICML 2008), July, New York, NY, USA, p.208–215, (2008). ICML '08. Helsinki, Finland. URL PDF
Learning the structure of manifolds using random projections, Yoav Freund, Sanjoy Dasgupta, Mayank Kabra, and Nakul Verma; J. C. Platt, D. Koller, Y. Singer, and S. Roweis, eds., Advances in Neural Information Processing Systems 20, Cambridge, MA, p.473–480, (2008).
On the Complexity of Succinct Zero-Sum Games, Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Christopher Umans, Computational Complexity, Volume 17, p.353-376, (2008). URL
Optimal Communication Complexity of Generic Multicast Key Distribution, Daniele Micciancio, and Saurabh Panjwani, IEEE/ACM Transactions on Networking, August, Volume 16, Number 4, Piscataway, NJ, USA, p.803-13, (2008). URL PDF
Quasi-random graphs with given degree sequences, Fan Chung, and Ron Graham, Random Structures & Algorithms, Volume 32, Number 1, p.1–19, (2008). URL
Random projection trees and low dimensional manifolds, Sanjoy Dasgupta, and Yoav Freund, Proceedings of the 40th annual ACM symposium on Theory of computing, May, New York, NY, USA, p.537–546, (2008). STOC '08. Victoria, British Columbia, Canada. URL PDF
Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions, Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier, and Haixia Shi, Journal of Cryptology, Volume 21, p.350-391, (2008). URL
Static analysis of active XML systems, Serge Abiteboul, Luc Segoufin, and Victor Vianu, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, New York, NY, USA, p.221–230, (2008). PODS '08. Vancouver, Canada. URL
SWIFFT: A Modest Proposal for FFT Hashing, Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen; Kaisa Nyberg, eds., Fast Software Encryption, Volume 5086, p.54-72, (2008). Lecture Notes in Computer Science. URL
The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs, Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi, Journal of Computer and System Sciences, Volume 74, Number 3, p.386 - 393, (2008). [Computational Complexity 2003] URL
The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization, Daniele Micciancio, and Scott Yilek; Ran Canetti, eds., Proceedings of TCC 2008, March, Volume 4948, New York, p.535-52, (2008). LNCS. URL PDF
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized, Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson; Richard E. Ladner, and Cynthia Dwork, eds., 40th Annual ACM Symposium on Theory of Computing, May, Victoria, B.C., Canada, p.579-588, (2008). STOC '08. Victoria, British Columbia, Canada. URL
Xl: an efficient network routing algorithm, Kirill Levchenko, Geoffrey M. Voelker, Ramamohan Paturi, and Stefan Savage, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, New York, NY, USA, p.15–26, (2008). SIGCOMM '08. Seattle, WA, USA. URL

2007

A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians, Sanjoy Dasgupta, and Leonard Schulman, J. Mach. Learn. Res., May, Volume 8, p.203–226, (2007). URL
Approximately Optimal Trees for Group Key Management with Batch Updates, Minming Li, Ze Feng, Ronald Graham, and Frances Yao; Jin-Yi Cai, S. Cooper, and Hong Zhu, eds., Theory and Applications of Models of Computation, Volume 4484, p.284-295, (2007). Lecture Notes in Computer Science. URL
Chernoff-Type Direct Product Theorems, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets; Alfred Menezes, eds., Advances in Cryptology - CRYPTO 2007, Volume 4622, p.500-516, (2007). Lecture Notes in Computer Science. URL
Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm, Reid Andersen, and Fan Chung; Jin-Yi Cai, S. Cooper, and Hong Zhu, eds., Theory and Applications of Models of Computation, Volume 4484, p.1-12, (2007). Lecture Notes in Computer Science. URL
Deterministic and Efficiently Searchable Encryption, Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill; Alfred Menezes, eds., Proceedings of Crypto 2007, August, Volume 4622, Santa Barbara, CA, p.535-52, (2007). LNCS. URL PDF
Drawing Power Law Graphs Using a Local/Global Decomposition, Reid Andersen, Fan Chung, and Linyuan Lu, Algorithmica, Volume 47, p.397-397, (2007). URL
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Daniele Micciancio, Computational Complexity, Volume 16, p.365-411, (2007). URL
Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms, Mihir Bellare, and Thomas Ristenpart; Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, eds., Automata, Languages and Programming, Volume 4596, p.399-410, (2007). Lecture Notes in Computer Science. URL
How to Play the Majority Game with Liars, Steve Butler, Jia Mao, and Ron Graham; Ming-Yang Kao, and Xiang-Yang Li, eds., Algorithmic Aspects in Information and Management, Volume 4508, p.221-230, (2007). Lecture Notes in Computer Science. URL
Identity-Based Multi-signatures from RSA, Mihir Bellare, and Gregory Neven; Masayuki Abe, eds., Topics in Cryptology – CT-RSA 2007, Volume 4596, p.145-162, (2007). URL
Local Partitioning for Directed Graphs Using PageRank, Reid Andersen, Fan Chung, and Kevin Lang; Anthony Bonato, and Fan Chung, eds., Algorithms and Models for the Web-Graph, Volume 4863, Berlin, Heidelberg, p.166-178, (2007). Lecture Notes in Computer Science. San Diego, CA, USA. URL
No-Three-in-Line-in-3D, Reid Andersen, Fan Chung, and Linyuan Lu, Algorithmica, Volume 47, p.379-397, (2007). URL
Oblivious and Adaptive Strategies for the Majority and Plurality Problems, Fan Chung, Ron Graham, Jia Mao, and Andrew Yao, Algorithmica, Volume 48, p.147-157, (2007). URL
On Heuristic Time Hierarchies, Konstantin Pervyshev, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, Washington, DC, USA, p.347–358, (2007). URL
On-Line Estimation with the Multivariate Gaussian Distribution, Sanjoy Dasgupta, and Daniel Hsu; Nader Bshouty, and Claudio Gentile, eds., Learning Theory, Volume 4539, p.278-292, (2007). Lecture Notes in Computer Science. URL
Optimal Tree Structures for Group Key Management with Batch Updates, Ronald L. Graham, Minming Li, and Frances F. Yao., SIAM Journal on Discrete Mathematics, Volume 21, Number 2, p.532-547, (2007). URL
Robust Computational Secret Sharing and a Unified Account of Classical Secret-Sharing Goals, Mihir Bellare, and Phillip Rogaway; Sabrina De Capitani di Vimercati, and Paul Syverson, eds., Proceedings of the ACM Conference on Computer and Communications Security, October, Washington, D.C., p.172-84, (2007). CCS '07. Alexandria, Virginia, USA. URL PDF
Specification and verification of data-driven Web applications, Alin Deutsch, Liying Sui, and Victor Vianu, Journal of Computer and System Sciences, Volume 73, Number 3, p.442 - 474, (2007). [Special Issue: Database Theory 2004] URL
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs, Paul Beame, Russell Impagliazzo, and Ashish Sabharwal, Computational Complexity, Volume 16, p.245-297, (2007). URL
The Spectral Gap of a Random Subgraph of a Graph, Fan Chung, and Paul Horn, Internet Mathematics, Volume 4, p.225-244, (2007). URL
Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles, Mihir Bellare, and Sarah Shoup; Tatsuaki Okamoto, and Xiaoyun Wang, eds., Proceedings of PKC 2007, April, Volume 4450, Beijing, China, p.201-16, (2007). LNCS. URL PDF
Unrestricted Aggregate Signatures, Mihir Bellare, Chanathip Namprempre, and Gregory Neven; Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, eds., Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), July, Volume 4596, Wroclaw, Poland, p.411-22, (2007). LNCS. URL PDF
Using PageRank to Locally Partition a Graph, Reid Andersen, Fan Chung, and Kevin Lang, Internet Mathematics, Volume 4, p.35-64, (2007). URL
Worst-Case to Average-Case Reductions Based on Gaussian Measures, Daniele Micciancio, and Oded Regev, SIAM Journal on Computing, Volume 37, Number 1, p.267-302, (2007). URL

2006

A Duality between Clause Width and Clause Density for SAT, Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.252-260, (2006).
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets, FOCS (to appear), (2006).
Balancing Applied to Maximum Network Flow Problems, J. Mao, R. Tarjan, B. Zhang, and Y. Zhou, European Symposium on Algorithms (ESA), Number LNCS 4168, p.612–623, (2006).
Can every randomized algorithm be derandomized?, Russell Impagliazzo, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, New York, NY, USA, p.373–374, (2006). STOC '06. Seattle, WA, USA. URL
Consistency of Local Density Matrices Is QMA-Complete, Yi-Kai Liu, RANDOM, p.438–449, (2006).
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations, Russell Impagliazzo, and Nathan Segerlind, ACM Trans. Comput. Logic, Volume 7, Number 2, p.199–218, (2006).
Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress Report, Alan Nash, Luc Segoufin, and Victor Vianu; Thomas Schwentick, and Dan Suciu, eds., Database Theory – ICDT 2007, Volume 4353, p.59-73, (2006). Lecture Notes in Computer Science. URL
Generalized Compact Knapsacks Are Collision Resistant, Vadim Lyubashevsky, and Daniele Micciancio; Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, eds., Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), July, Volume 4051, Venice, Italy, p.144-55 (volume 2), (2006). LNCS. PDF
Local Graph Partitioning using PageRank Vectors, Reid Andersen, Fan Chung, and Kevin Lang, FOCS (to appear), (2006).
Logics for Reasoning about Cryptographic Constructions, Russell Impagliazzo, and Bruce M. Kapron, Journal of Computer and System Sciences, March, Volume 72, Number 2, p.286-320, (2006).
On Bounded Distance Decoding for General Lattices, Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio, RANDOM, p.450–461, (2006).
Online Algorithms to Minimize Resource Reallocation and Network Communication, Sashka Davis, Jeff Edmonds, and Russell Impagliazzo, APPROX, p.104–115, (2006).
Unexpected Means of Protocol Inference, J. Ma, K. Levchenko, C. Kreibich, S. Savage, and G. M. Voelker, Proceedings of the Internet Measurement Conference (to appear), (2006).

2005

Improved Range-Summable Random Variable Construction Algorithms, A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan, and M. Strauss, SODA, January, (2005).
Oblivious Strategies in the Majority and Plurality Problems, F. Chung, R. Graham, J. Mao, and A. C. Yao, Computing and Combinatorics, (2005).
PTIME Queries Revisited, Alan Nash, Jeffrey B. Remmel, and Victor Vianu, ICDT, p.274-288, (2005).
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem, Vadim Lyubashevsky, RANDOM, (2005).
The RSA Group is Pseudo-Free, Daniele Micciancio, EUROCRYPT, p.387-403, (2005).

2004

A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution, Nathan Segerlind, Samuel R. Buss, and Russell Impagliazzo, SIAM J. Comput., Volume 33, Number 5, p.1171-1200, (2004).
Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor, Daniele Micciancio, SIAM J. Comput., Volume 34, Number 1, p.118-169, (2004).
Analyzing the Small World Phenomenon Using a Hybrid Model with Local Network Flow, Reid Anderson, Fan Chung, and Lincoln Lu, WAW, p.19-30, (2004).
Circuit lower bounds and linear codes, Ramamohan Paturi, and Pavel Pudlak, ECCC, Volume 004, (2004).
Compressing Network Graphs, A. Gilbert, and K. Levchenko, Proc. of the LinkKDD Workshop at the Tenth ACM Conference on Knowledge Discovery and Data Mining, August, (2004).
De Bruijn cycles for covering codes, Fan Chung, and Joshua N. Cooper, Random Struct. Algorithms, Volume 25, Number 4, p.421-431, (2004).
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, Valentine Kabanets, and Russell Impagliazzo, Computational Complexity, Volume 13, Number 1-2, p.1-46, (2004).
Drawing Power Law Graphs, Reid Anderson, Fan Chung, and Lincoln Lu, Graph Drawing, p.12-17, (2004).
Extracting Randomness Using Few Independent Sources, Boaz Barak, Russell Impagliazzo, and Avi Wigderson, FOCS, p.384-393, (2004).
Models of greedy algorithms for graph problems, Sashka Davis, and Russell Impagliazzo, SODA, p.381-390, (2004).
Near Optimal Separation Of Tree-Like And General Resolution, Eli Ben-Sasson, Russell Impagliazzo, and Avi Wigderson, Combinatorica, Volume 24, Number 4, p.585-603, (2004).
On the complexity of succinct zero-sum games, Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Christopher Umans, ECCC, Volume 0001, (2004).
On the Difficulty of Scalably Detecting Network Attacks, Kirill Levchenko, Ramamohan Paturi, and George Varghese, Proceedings of the ACM Conference on Computer and Communications Security, October, Washington, D.C., p.12-20, (2004). PDF
On Disjoint Path Pairs with Wavelength Continuity Constraint in WDM Networks, Reid Anderson, Fan Chung, Arunabha Sen, and Guoliang Xue, INFOCOM, (2004).
Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines, Fan Chung Graham, and George Varghese, Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June, Barcelona, Spain, p.103-111, (2004). PDF
Spectral Grouping Using the Nystrom Method, Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik, IEEE Trans. Pattern Anal. Mach. Intell., Volume 26, Number 2, p.214-225, (2004).
The Complexity of the Covering Radius Problem on Lattices and Codes, Venkatesh Guruswami, Daniele Micciancio, and Oded Regev, IEEE Conference on Computational Complexity, p.161-173, (2004).
Worst-Case to Average-Case Reductions Based on Gaussian Measures, Daniele Micciancio, and Oded Regev, FOCS, p.372-381, (2004).

2003

A zero one law for RP, Russell Impagliazzo, and Philippe Moser, IEEE Conference on Computational Complexity, p.48-52, (2003).
A Note on the Minimal Volume of Almost Cubic Parallelepipeds, Daniele Micciancio, Discrete and Computational Geometry, Volume 29, Number 1, p.133-138, (2003).
Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor, Daniele Micciancio, ECCC, Volume 066, (2003).
An elementary proof of a theorem of Johnson and Lindenstrauss, Sanjoy Dasgupta, and Anupam Gupta, Random Struct. Algorithms, Volume 22, Number 1, p.60-65, (2003).
Anonymous credentials with biometrically-enforced non-transferability, Russell Impagliazzo, and Sara Miner More, WPES, p.60-71, (2003).
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations, Russell Impagliazzo, and Nathan Segerlind, CoRR, (2003).
Derandomizing polynomial identity tests means proving circuit lower bounds, Valentine Kabanets, and Russell Impagliazzo, STOC, p.355-364, (2003).
Finding Favorites, Fan R. K. Chung, Ronald L. Graham, Jia Mao, and Andrew Chi-Chih Yao, ECCC, Volume 078, (2003).
Hardness as randomness: a survey of universal derandomization, Russell Impagliazzo, CoRR, (2003).
Hardness of approximating the minimum distance of a linear code, Ilya Dumer, Daniele Micciancio, and Madhu Sudan, IEEE Transaction on Information Theory, Volume 49, Number 1, p.22-37, (2003).
Logic as a Query Language: From Frege to XML, Victor Vianu, STACS, p.1-12, (2003).
Logics for Reasoning about Cryptographic Constructions, Russell Impagliazzo, and Bruce M. Kapron, FOCS, p.372-383, (2003).
Memoization and DPLL: Formula Caching Proof Systems, Paul Beame, Russell Impagliazzo, Toniann Pitassi, and Nathan Segerlind, IEEE Conference on Computational Complexity, (2003).
Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More, Daniele Micciancio, and Salil P. Vadhan, CRYPTO, p.282-298, (2003).
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs, Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi, IEEE Conference on Computational Complexity, (2003).
Universal Languages and the Power of Diagonalization, Alan Nash, Russell Impagliazzo, and Jeffrey B. Remmel, IEEE Conference on Computational Complexity, p.337-346, (2003).


by Dr. Radut.