Computer Science Group Preprints

Year Content Icon
Yixin Shen, Rajendra Kumar, Yanlin Chen, D. Aggarwal Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding.
Luisa Siniscalchi, Mark Simkin , Joao Ribeiro, Maciej Lukasz Obremski, D. Aggarwal Computational and Information-Theoretic Two-Source (Non-Malleable) Extractors.
D. Aggarwal, Maciej Lukasz Obremski Inception makes non-malleable codes shorter as well!.
Anurag Anshu, R. Jain, Alexander Streltsov Quantum state redistribution with local coherence.
Anurag Anshu, R. Jain Quantum decoupling via efficient `classical' operations and the entanglement cost of one-shot quantum protocols.
A. Anshu, M. Hayashi, NA Warsi Secure communication over fully quantum Gelfand-Pinsker wiretap channel.
H. Klauck, Debbie Lim The Power of One Clean Qubit in Communication Complexity.
I. Kerenidis, Alessandro Luongo Quantum classification of the MNIST dataset via Slow Feature Analysis.
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, Antonios Varvitsiotis Vector Coloring the Categorical Product of Graphs.
I. Arad, Eyal Bairey, Netanel H. Lindner Learning a local Hamiltonian from local measurements.
Juan Miguel Arrazola, Eleni Diamanti, I. Kerenidis Quantum superiority for verifying NP-complete problems with linear optics.
Anurag Anshu, M. Hayashi, Naqueeb Ahmad Warsi Secure communication over fully quantum Gelfand-Pinsker wiretap channel.
A. Anshu, Min-Hsiu Hsieh, R. Jain Noisy quantum state redistribution with promise and the Alpha-bit.
Ansis Rosmanis, Jamie William Jonathon Sikora, Gus Gutoski Fidelity of quantum strategies with applications to cryptography.
Jamie William Jonathon Sikora, Zhaohui Wei Device-independent dimension test in a multiparty Bell experiment.
Jamie William Jonathon Sikora, John Selby A simple proof of the impossibility of bit-commitment in generalised probabilistic theories using cone programming.
A. Anshu, R. Jain, NA Warsi A unified approach to source and message compression.
Ritajit Majumdar, Saikat Basu, P. Mukhopadhyay, Susmita Sur-Kolay Error tracing in linear and concatenated quantum circuits.
P. Mukhopadhyay, Y. Qiao Sparse multivariate polynomial interpolation in the basis of Schubert polynomials.
T. Lee, Z.H. Wei, Ronald de Wolf Some upper and lower bounds on PSD-rank.
Jaikumar Radhakrishnan, Pranab Sen, NA Warsi One-Shot Private Classical Capacity of Quantum Wiretap Channel: Based on one-shot quantum covering lemma.
A.Prakash, A.Varvitsiotis Matrix factorizations of correlation matrices and applications.
Albert Atserias, L. Mancinska, David E. Roberson, Robert mal, Simone Severini, A.Varvitsiotis Quantum and non-signalling graph isomorphisms.
Chris Godsil, David E. Roberson, Brendan Rooney, Robert mal, A.Varvitsiotis Graph Homomorphisms via Vector Colorings.
A. Anshu A lower bound on expected communication cost of quantum state redistribution.
I. Kerenidis, A.Prakash Quantum Recommendation Systems.
L. Mancinska, David E. Roberson, A.Varvitsiotis Deciding the existence of perfect entangled strategies for nonlocal games.
Samuel Fiorini, Tony Huynh, Gwenal Joret, A.Varvitsiotis The excluded minors for isometric realizability in the plane.
Chris Godsil, David E. Roberson, Brendan Rooney, Robert mal, A.Varvitsiotis Universal completability, least eigenvalue frameworks, and vector colorings.
Tomotaka Kuwahara, I. Arad, L. Amico, V. Vedral Local reversibility and entanglement structure of many-body ground states.
A. Pereszlenyi One-Sided Error QMA with Shared EPR Pairs -- A Simpler Proof.
M. Laurent, A.Varvitsiotis Positive Semidefinite Matrix Completion, Universal Rigidity and the Strong Arnold Property.
R. Jain, Nisheeth K. Vishnoi, T. Lee A quadratically tight partition bound for classical communication complexity and query complexity.
R. Jain, P. Yao A strong direct product theorem in terms of the smooth rectangle bound.
M.E. McKague, L. Sheridan Insider-proof encryption with applications for quantum key distribution.
A. Pereszlenyi Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap.
R. Jain, P. Yao A parallel approximation algorithm for mixed packing and covering semidefinite programs.
Aleksandrs Belovs, T. Lee Quantum Algorithm for k-distinctness with Prior Knowledge on the Input.
Anne Broadbent, J. Fitzsimons, Elham Kashefi QMIP = MIP*.
Marcus Schaffry, Erik M. Gauger, John J. L. Morton, J. Fitzsimons, Simon C. Benjamin Ensemble based quantum metrology.
Matthew McKague BQP interactive proof for recursive Fourier sampling.
T. Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek An adversary for algorithms.
Ming Lam Leung, Yang Li, Shengyu Zhang Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models.
S. Zhang Quantum Strategic Game Theory.
I. Kerenidis, S. Zhang A quantum protocol for sampling correlated equilibria unconditionally and without a mediator.