Publications Archive

2013

A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations, Daniele Micciancio, and Panagiotis Voulgaris, SIAM J. on Computing, Volume 42, Issue 3, p.1364-1391, (2013). 

Algorithms for the Densest Sub-Lattice Problem, Daniel Dadush, and Daniele Micciancio, SODA, p.1103-1122, (2013).

An equational approach to secure multi-party computation, Daniele Micciancio, and Stefano Tessaro, ITCS, p.355-372, (2013). URL 

Dirichlet PageRank and Ranking Algorithms Based on Trust and Distrust, Fan Chung Graham, Alexander Tsiatas, and Wensong Xu, Internet Mathematics, Volume 9, Number 1, p.113-134, (2013). URL 

Every locally characterized affine-invariant property is testable, Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett, The 45th ACM Symposium on Theory of Computing (STOC 2013), (2013). [to appear] URL

Full analysis of PRINTcipher with respect to invariant subspace attack: efficient key recovery and countermeasures, S. Bulygin, Michael Walter, and J. Buchmann, Designs, Codes and Cryptography, (2013). 

Hardness of SIS and LWE with Small Parameters, Daniele Micciancio, and Chris Peikert, CRYPTO, Volume 8042, p.21-39, (2013). LNCS. 

Improved algebraic side-channel attack on AES, M. S. E. Mohamed, S. Bulygin, M. Zohner, A. Heuser, Michael Walter, and J. Buchmann, Journal of Cryptographic Engineering, Volume 3, Issue 3, p.139-156, (2013). PDF 

Many Weak Keys for PRINTcipher: Fast Key Recovery and Countermeasures, Stanislav Bulygin, Michael Walter, and Johannes Buchmann, CT-RSA, p.189-206, (2013). URL 

New Bounds for Matching Vector Families, Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett, The 45th ACM Symposium on Theory of Computing (STOC 2013), (2013). [to appear] URL 

On the Exact Complexity of Evaluating Quantified k-CNF, Chris CalabroRussell Impagliazzo, and Ramamohan Paturi, Algorithmica, Volume 65, Number 4, p.817-827, (2013). URL 

2012

A note on marking lines in [k] n - In honor of Rick Wilson's 65th birthday, Steve Butler, and Ronald L. Graham, Des. Codes Cryptography, Volume 65, Number 3, p.165-175, (2012). URL 

A satisfiability algorithm for AC$^0$, Russell ImpagliazzoWilliam Matthews, and Ramamohan Paturi, SODA, p.961-972, (2012). URL 

Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing, Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway, ASIACRYPT, p.134-153, (2012). URL 

Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for \#AC^0SAT, Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan, IEEE Conference on Computational Complexity, p.117-125, (2012). URL 

Braess's paradox in expanders, Fan Chung Graham, Stephen J. Young, and Wenbo Zhao, Random Struct. Algorithms, Volume 41, Number 4, p.451-468, (2012). URL 

Character design and stamp algorithms for Character Projection Electron-Beam Lithography, Peng Du, Wenbo Zhao, Shih-Hung Weng, Chung-Kuan Cheng, and Ronald L. Graham, ASP-DAC, p.725-730, (2012). URL 

Common Knowledge and State-Dependent Equilibria, Nuh Aygun Dalkiran, Moshe Hoffman, Ramamohan PaturiDaniel Ricketts, and Andrea Vattani, SAGT, p.84-95, (2012). URL 

Diameter of random spanning trees in a given graph, Fan R. K. Chung, Paul Horn, and Linyuan Lu, Journal of Graph Theory, Volume 69, Number 3, p.223-240, (2012). URL 

Efficient and Optimally Secure Key-Length Extension for Block Ciphers via Randomized Cascading, Peter Gazi, andStefano Tessaro, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012). 

Finding and Visualizing Graph Clusters Using PageRank Optimization, Fan R. K. Chung, and Alexander Tsiatas, Internet Mathematics, Volume 8, Number 1-2, p.46-72, (2012). URL 

Foundations of garbled circuits, Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway, ACM Conference on Computer and Communications Security, p.784-796, (2012). URL 

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 

Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction, Daniele Micciancio, Theory of Computing, Volume 8, Number 1, p.487-512, (2012). URL 

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits, Chris Beck, Russell Impagliazzo, and Shachar Lovett, FOCS, p.101-110, (2012). URL 

Malleable Proof Systems and Applications, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Sarah Meiklejohn,Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012). 

Multi-commodity Allocation for Dynamic Demands Using PageRank Vectors, Fan R. K. Chung, Paul Horn, and Jacob Hughes, WAW, p.138-152, (2012). URL 

New Direct-Product Testers and 2-Query PCPs, Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson, SIAM J. Comput., Volume 41, Number 6, p.1722-1768, (2012). URL 

On Problems as Hard as CNF-SAT, Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström, IEEE Conference on Computational Complexity, p.74-84, (2012). URL 

On the (im)possibility of obfuscating programs, Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang, J. ACM, Volume 59, Number 2, p.6, (2012). URL 

On-line Ciphers and the Hash-CBC Constructions, Mihir Bellare, Alexandra Boldyreva, Lars R. Knudsen, and Chanathip Namprempre, J. Cryptology, Volume 25, Number 4, p.640-679, (2012). URL 

Optimizing Guessing Strategies for Algebraic Cryptanalysis with Applications to EPCBC, Michael Walter, Stanislav Bulygin, and Johannes Buchmann, Inscrypt, (2012). PDF 

Pseudorandomness from Shrinkage, Russell Impagliazzo, Raghu Meka, and David Zuckerman, FOCS, p.111-119, (2012).URL 

Quasi-random hypergraphs revisited, Fan Chung Graham, Random Struct. Algorithms, Volume 40, Number 1, p.39-48, (2012). URL 

Ranking and Sparsifying a Connection Graph, Fan Chung Graham, and Wenbo Zhao, WAW, p.66-77, (2012). URL 

RKA Security beyond the Linear Barrier: IBE, Encryption and Signatures, Mihir Bellare, Kenneth G. Paterson, and Susan Thomson, ASIACRYPT, p.331-348, (2012). URL 

Semantic Security for the Wiretap Channel, Mihir BellareStefano Tessaro, and Alexander Vardy, CRYPTO, p.294-311, (2012). URL 

Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model, Kamalika Chaudhuri, Fan Chung Graham, and Alexander Tsiatas, Journal of Machine Learning Research - Proceedings Track, Volume 23, p.35.1-35.23, (2012). URL 

Standard Security Does Not Imply Security Against Selective-Opening, Mihir Bellare, Rafael Dowsley, Brent Waters, andScott Yilek, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012). PDF 

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space, Paul Beame, Christopher Beck, and Russell Impagliazzo, STOC, p.213-232, (2012). URL 

Trapdoor for Lattices: Simpler, Tighter, Faster, Smaller, Daniele Micciancio, and Chris Peikert, Proceedings of Eurocrypt 2012, April 2012, Cambridge, UK, (2012). PDF 

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 BellareDavid 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 BellareDavid 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 VoulgarisSTOC, 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 MicciancioJournal of Cryptology, April, Volume 23, Number 2, p.169-86, (2010).PDF 

Tiling Polygons with Lattice Triangles, Steve Butler, Fan ChungRon Graham, and Miklós Laczkovich, Discrete & Computational Geometry, Volume 44, p.896-903, (2010). URL 

Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized, Russell ImpagliazzoRagesh 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, andRamamohan 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 algebrizatio, 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 ImpagliazzoRagesh 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 ZangRonald 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 ImpagliazzoRagesh Jaiswal, and Valentine Kabanets, Journal of Cryptology, Volume 22, p.75-92, (2009). URL 

Format-Preserving Encryption, Mihir BellareThomas 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, andDaniele 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 ImpagliazzoRagesh 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 CalabroRussell 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 GrahamRonald 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

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 LyubashevskyDaniele 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 CalabroRussell 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 ImpagliazzoRagesh 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 LevchenkoGeoffrey M. VoelkerRamamohan 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 ImpagliazzoRagesh 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, andFan 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 ChungRon GrahamJia 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 CalabroRussell 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 ImpagliazzoRagesh 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, andRussell 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 LevchenkoRamamohan 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 CalabroRussell 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).