- Reconstruction of Random Graphs with Few Participants
With Animashree Anandkumar and Jon Kelner,
Best paper award Sigmetrics 2011. - Monotonicity and Implementability
With Itai Ashlagi, Mark Braverman,
and Dov Monderer
Econometrica September 2010. - Quantum Money
With Scott Aaronson, Eddie Farhi,
David Gosset, Jon Kelner and Andrew Lutomirski.
Invited Survey in Communications of the ACM (CACM).
Invited talk at QIP 2011 - Quantum State Restoration and Single Copy Tomography
With Eddie Farhi,
David Gosset, Andrew Lutomirski, Daniel Nagaj and
Peter Shor. [arxiv:0912.3823]
PRL (Physical Review Letters), November 2010. - Adaptive Versus Non-adaptive Strategies for Quantum Channel Discrimination
With Aram Harrow, Debbie W. Leung and
John Watrous [arXiv:0909.0256v1]
Phys. Rev. A 2010. - Position Auctions with Budgets: Existence and Uniqueness
With Itai Ashlagi, Mark Braverman,
Ron Lavi and Moshe Tennenholtz
B.E. Journal of Theoretical Economics (Advances tier).
10th workshop on ad auctions. - Cache Replacement Policies for Multicore Processors
Innovations in Computer Science (ICS) 2010. - Global Alignment of Molecular Sequences via Ancestral State Reconstruction
With Alexander Andoni, Constantinos Daskalakis and Sebastien Roch
Innovations in Computer Science (ICS) 2010. - Breaking and Making Quantum Money
With Scott Aaronson, Eddie Farhi,
David Gosset, Jon Kelner, Andrew Lutomirski and
Peter Shor.
Innovations in Computer Science (ICS) 2010. - Guaranteeing Perfect Revenue From Perfectly Informed Players
With Jing Chen and Silvio Micali
Innovations in Computer Science (ICS) 2010. - Derandomizng Algorithms on Product Distributions
With Ariel Gabizon.
Innovations in Computer Science (ICS) 2010. - Quantum algorithms for testing properties of distributions
With Sergey Bravyi, Aram Harrow. [arXiv:0907.3920v1]
IEEE Transactions on Information theory. Preliminary version appeared in STACS 2010. - A Quantum Algorithm for Linear Systems of Equations
With Aram Harrow and Seth Lloyd. [arXiv:0811.3171]
Editor's suggestion in PRL (Physical Review Letters). vol. 15, no. 103, pp. 150502, 2009.
Selected to Virtual Journal of Quantum Information Oct'09
Invited talk at QIP2010
Media Coverage: Slashdot, MIT News, PhysOrg, American Physical Society, Science News. Nature Physics, Scientific American - Local Graph Partitions for Approximation and Testing
With Jonathan Kelner, Huy N. Nguyen and Krzysztof Onak.
FOCS 2009. - Sorting and Selection with Imprecise Comparisons
With Miklós Ajtai, Vitaly Feldman and Jelani Nelson.
ICALP 2009. - Quantum Multiprover Interactive Proofs with Communicating Provers
With Michael Ben-Or and Haran Pilpel.
Invited talk at QIP2009
FOCS 2008. - The Bayesian Learner is Optimal for Noisy Binary Search (and pretty good for quantum as well)
With Michael Ben-Or.
QIP2006
FOCS 2008. - Broadcasting with Side Information
With Noga Alon, Eyal Lubetzky, Uri Stav and Amit Weinstein.
FOCS 2008. - No Nonlocal Box is Universal
With Frédéric Dupuis,
Nicolas Gisin, André Allan Méthot, Haran Pilpel. [quant-ph/0701142]
JMP - Journal of Mathematical Physics 48, 082107.
Selected to the Virtual Journal of Quantum Information Sep'07. - Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority With Michael Ben-Or,
Claude Crépeau,
Daniel Gottesman and Adam Smith.
QIP2006.
FOCS 2006. - Fast Quantum Byzantine Agreement
With Michael Ben-Or.
STOC 2005.
Working Papers
- Phylogenetic Reconstruction with Insertions and Deletions
With Alex Andoni and Mark Braverman,
Preprint 2010. - Super-Polynomial Quantum Speed-ups for Evaluating Boolean Formulas with Hidden Structure
With Bohua Zhan and Shelby Kimmel,
Preprint 2010. - Quantum Money from Knots
With Eddie Farhi,
David Gosset, Andrew Lutomirski and
Peter Shor.
Preprint 2010. [arXiv:1004.5127] - Non-Price Equilibria in Markets of Discrete Goods
With Haim Kaplan,
Yishay Mansour,
and
Noam Nisan.
Preprint 2011 - Matching Markets with Couples Revisited
With Itai Ashlagi, and Mark Braverman,
Preprint 2011.