|
Click on a project in the table below for all publications registered to that project.
Project AFM1: Quantum Information Processing
2010
- Nitin Saxena, C. Seshadhri: From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits CoRR abs/1002.0145 (2010)
2009
- Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah: Sound 3-Query PCPPs Are Long. TOCT 1(2): (2009)
- Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster: Hardness and Algorithms for Rainbow Connectivity CoRR abs/0902.1255: (2009)
- Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster: Hardness and Algorithms for Rainbow Connectivity. STACS 2009: 243-254
- Oded Regev, Ben Toner: Simulating Quantum Correlations with Finite Communication. SIAM J. Comput. 39(4): 1562-1580 (2009)
- Andris Ambainis, Robert Spalek, Ronald de Wolf: A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3):422-461 (2009)
- Andrew Drucker, Ronald de Wolf: Quantum Proofs for Classical Theorems CoRR abs/0910.3376 (2009)
- Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. (SIAMCOMP) 39(1):1-24 (2009)
- Jop Briet, Ronald de Wolf: Locally Decodable Quantum Codes. STACS 2009:219-230
- Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings CoRR abs/0912.3162 (2009)
- Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. ICALP 2009:195-209
- Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems CoRR abs/0907.0774 (2009)
- Chandan Saha, Ramprasad Saptharishi, Nitin Saxena: The Power of Depth 2 Circuits over Algebras CoRR abs/0904.2058 (2009)
- Chandan Saha, Ramprasad Saptharishi, Nitin Saxena: The Power of Depth 2 Circuits over Algebras. FSTTCS 2009:371-382
- Nitin Saxena, C. Seshadhri: An Almost Optimal Rank Bound for Depth-3 Identities. IEEE Conference on Computational Complexity 2009:137-148
- Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for deterministic polynomial factoring. ISSAC 2009:191-198
2008
- Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. (SIAMCOMP) 37(5):1387-1400 (2008)
- Avraham Ben-Aroya, Oded Regev, Ronald de Wolf: A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. FOCS 2008:477-486
- Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing. ICALP 2008:845-856
- Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. (SIAMCOMP) 38(5):1695-1708 (2008)
- Nitin Saxena, C. Seshadhri: An Almost Optimal Rank Bound for Depth-3 Identities CoRR abs/0811.3161 (2008)
- Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for Deterministic Polynomial Factoring CoRR abs/0804.1974 (2008)
- Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures CoRR abs/0811.3165 (2008)
- Nitin Saxena, C. Seshadhri: An Almost Optimal Rank Bound for Depth-3 Identities. Electronic Colloquium on Computational Complexity (ECCC) (ECCC) 15(108) (2008)
- Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for Deterministic Polynomial Factoring. Electronic Colloquium on Computational Complexity (ECCC) (ECCC) 15(043) (2008)
- Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures. Electronic Colloquium on Computational Complexity (ECCC) (ECCC) 15(099) (2008)
- Eli Ben-Sasson, Prahladh Harsha, Oded Lachish and Arie Matsliah. Sound 3-Query PCPPs Are Long. In ICALP 2008, pages 686-697, 2008.
- Eldar Fischer, Arie Matsliah. Testing Graph Isomorphism. In SIAM J. Comput. (SIAMCOMP), 38(1), pages 207-225, 2008.
- Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom. On the Query Complexity of Testing Orientations for Being Eulerian. In APPROX-RANDOM, pages 402-415, 2008.
- Robert W. Spekkens, D. H. Buzacott, A. J. Keehn, Ben Toner and G. J. Pryde. Experimental demonstration of preparation contextuality and parity-oblivious multiplexing. To appear in Phys. Rev. Lett. (in arXiv.org quant-ph/0805.1463), 2008.
- Debbie Leung, Ben Toner and John Watrous. Coherent state exchange in multi-prover quantum interactive proof systems. In arXiv.org quant-ph/0804.4118, 2008.
- Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner and Stephanie Wehner. The quantum moment problem and bounds on entangled multiprover games. In Proceedings of 23rd IEEE Conference on Computational Complexity (CCC 2008), pages 199-210, 2008.
- Howard Barnum, Oscar Dahlsten, Matthew Leifer and Ben Toner. Nonclassicality without entanglement enables bit commitment. Proceedings of 2008 IEEE Information Theory Workshop (ITW 2008), pages 386-390, 2008.
- Schaffner, C. - Terhal, B. - Wehner, S.D.C.: Robust Cryptography in the Noisy-Quantum-Storage Model Series: arXiv.org e-Print archive, Nr. 0807.1333, July 2008. Cornell University Library
- Wehner, S.D.C. - Wullschleger, J.: Composable Security in the Bounded-Quantum-Storage Model first edition, 2008, pp. 604 - 615, conference title: Automata, Languages and Programming, International Colloquium, (ICALP), Number 23, Date: 2008. IEEE
- Ballester, M. - Wehner, S.D.C. - Winter, A.: State Discrimination With Post-Measurement Information IEEE Transactions on Information Theory, Vol. 54, Nr. 9, 2008, pp. 4183 - 4198.
- Kempe, J. - Regev, O. - Toner, B.F.: Unique games with entangled provers are easy first edition, 2008, pp. 447 - 456, conference title: Annual IEEE Symposium on Foundations of Computer Science, (FOCS), Number 49, Date: 2008. IEEE
- Kempe, J. - Kobayashi, H. - Matsumoto, K. - Toner, B.F. - Vidick, T.: Entangled games are hard to approximate first edition, 2008, pp. 447 - 456, conference title: Annual IEEE Symposium on Foundations of Computer Science, (FOCS), Number 49, Date: 2008. IEEE
- Doherty, Andrew C. - Liang, Yeong-Cherng - Toner, B.F. - Wehner, S.D.C.: The quantum moment problem and bounds on entangled multi-prover games first edition, 2008, conference title: IEEE Conference on Computational Complexity, (CCC), Number 23, Date: 2008. IEEE
- Barnum, Howard - Dahlsten, Oscar - Leifer, M. - Toner, B.F.: Nonclassicality without entanglement enables bit commitment first edition, 2008, pp. 386 - 390, conference title: 2008 IEEE Information Theory Workshop, (ITW 2008), Date: 2008. IEEE
- Unger, F.P.: Noise Threshold for Universality of Two-Input Gates IEEE Transactions on Information Theory, Vol. 54, Nr. 8, Art.nr. 4567603, August 2008, pp. 3693 - 3698.
- Unger, F.P. - Cleve, R. - Slofstra, W. - Upadhyay, S.: Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems Computational complexity, Vol. 17, Nr. 2, April 2008, pp. 282 - 299, ISSN: 1016-3328, e-ISSN: 1420-8954. Birkh\ufffduser
2007
- Bram Vermeer, Harry Buhrman: Quantum Information Processing. ERCIM News (ERCIM) 2007(71) (2007)
- Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf: Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. (MST) 40(4):379-395 (2007)
- Wehner, S.D.C. - Winter, A.: Higher entropic uncertainty relations for anti-commuting observables Series: arXiv.org e-Print archive, Nr. 0710.1185, October 2007. Cornell University Library
- Wehner, S.D.C. - Wullschleger, J.: Composable security in the bounded-quantum-storage model Series: arXiv.org e-Print archive, Nr. 0709.0492, September 2007. Cornell University Library
- Saxena, N.: Diagonal Circuit Identity Testing and Lower Bounds Series: Electronic Colloquium on Computational Complexity, Nr. TR07-124, December 2007, pp. 1 - 18, ISSN: ISSN 1433-8092.
- Saxena, N. - Severini, S. - Shparlinski, I. E.: Parameters of Integral Circulant Graphs and Periodic Quantum Dynamics Series: International Journal of Quantum Information, Nr. 5, May 2007, pp. 417 - 430. World Scientific Publishing Company
- Smith, G. S. B. - Smolin, J. - Wehner, S.D.C.: A simple family of nonadditive quantum codes Physical Review Letters, Vol. 99, 2007, pp. 130505 - last, ISSN: 0031-9007, e-ISSN: 1079-7114. American Physical Society
- Wehner, S.D.C. - Ballester, M.: Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases Physical Review A: atomic, molecular and optical physics, Vol. 75, 2007, pp. 022319 - last, ISSN: 1050-2947, e-ISSN: 1094-1622. American Physical Society
- Vereshchagin, N.K.: Kolmogorov complexity of enumerating finite sets Information processing letters : a journal devoted to the rapid publication of short contributions in the field of information processing, Vol. 103, Nr. 1, June 2007, pp. 34 - 39, ISSN: 0020-0190. Elsevier
- Noga, A. - Newman, I - Tardos, G. - Shen, A. - Vereshchagin, N.K.: Partitioning multi-dimensional sets in a small number of ``uniform'' parts European journal of combinatorics = Journal europ\ufffden de combinatoire = Europ\ufffdische Zeitschrift f\ufffdr Kombinatorik, Vol. 28, 2007, pp. 134 - 144, ISSN: 0195-6698. Academic Press
- Damgaard, I. - Fehr, S. - Salvail, L. - Schaffner, C.: Secure Identification and QKD in the Bounded-Quantum-Storage Model In: Lecture Notes in Computer Science, Series: Lecture notes in computer science, Vol. 4622, 2007, pp. 342 - 359, ISBN: 978-3-540-74142, ISSN: 0302-9743, e-ISSN: 1611-3349, conference title: Annual International Cryptology Conference, (CRYPTO), Number 27, August 19-23, Santa Barbara, USA. Editors: Menezes, A.. Springer
- Damgaard, I. - Fehr, S. - Renner, R. - Salvail, L. - Schaffner, C.: A Tight High-Order Entropic Quantum Uncertainty Relation With Applications In: Lecture Notes in Computer Science, Series: Lecture notes in computer science, Vol. 4622, 2007, pp. 360 - 378, ISBN: 978-3-540-74142, ISSN: 0302-9743, e-ISSN: 1611-3349, conference title: Annual International Cryptology Conference, (CRYPTO), Number 27, August 19-23, Santa Barbara, USA. Editors: Menezes, A.. Springer
- Oded Regev and Ben Toner. Simulating Quantum Correlations with Finite Communication. In: to appear in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007
- N. Kayal and N. Saxena. Polynomial Identity Testing for Depth 3 Circuits. In: The special issue of the journal of Computational Complexity on the 21st Conference on Computational Complexity (volume 16, number 2, pages 115-138), 2007
- N. Saxena, S. Severini, and I. E. Shparlinski. Parameters of Integral Circulant Graphs and Periodic Quantum Dynamics. In: International Journal of Quantum Information (volume 5, number 4, pages 417-430), 2007
2006
- Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, and Falk Unger. New Limits on Fault-Tolerant Quantum Computation. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006) (pages 411-419), IEEE Computer Society, Berkeley, California, USA, October 21-24, 2006
- Harry Buhrman and Robert Spalek. Quantum verification of matrix products. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006 (pages 880-889), ACM Press 2006, Miami, Florida, USA, January 22-26, 2006
- N. Kayal and N. Saxena. Complexity of Ring Morphism Problems. In: The special issue of the journal of Computational Complexity on the 20th Conference on Computational Complexity (volume 15, number 4, pages 342-390), 2006
- Brassard, Gilles, Buhrman, Harry, Linden, Noah, Mthot, Andr Allan, Tapp, Alain, and Unger, Falk. Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial. In: PhysRevLett.96.250401, 2006
- Harry Buhrman, Matthias Christandl, Falk Unger, Stephanie Wehner, and Andreas Winter. Implications of Superstrong Nonlocality for Cryptography. In: Proceedings of the Royal Society A (volume 462, number 2071, pages 1919-1932), 2006
- Harry Buhrman, Matthias Christandl, Patrick Hayden, Hoi-Kwong Lo, and Stephanie Wehner. Security of Quantum Bit String Commitment depends on the information measure. In: Physical Review Letters 97, 250501, 2006
|
