2 citations · 7 across the 9 of their papers we have counts for
12 papers
Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
Seyoon Ragavan, Noah Shutty
Regev's reduction quantumly finds codewords satisfying nonlinear constraints by decoding the dual code. To date, applications that have not been dequantized have relied on efficien…
A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
Aparna Gupte, Seyoon Ragavan, Mark Zhandry
We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template prop…
Efficient Unclonable Encryption from Pauli Eigenstates
Seyoon Ragavan
We give, to our knowledge, the first plain-model, one-time information-theoretically secure, efficient unclonable encryption scheme for one classical bit. Previous work by Bhattach…
Exponentially Fewer-Server PIR from Sparser -Decoding Polynomials
Aparna Gupte, Seyoon Ragavan
We show that under a plausible number-theoretic conjecture, for any constant there exists an -server private information retrieval (PIR) protocol that on an -bit database…
Optimization Using Locally-Quantum Decoders
Noah Shutty, Avijit Mandal, Seyoon Ragavan +8
It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related t…
Catalytic Tree Evaluation From Matching Vectors
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluat…
Parallel Spooky Pebbling Makes Regev Factoring More Practical
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Katherine Van Kirk
Pebble games, an abstraction from classical reversible computing, have found use in the design of quantum circuits for inherently sequential tasks. Gidney showed that allowing Hada…
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan +1
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA int…
Cloning Games, Black Holes and Cryptography
Alexander Poremba, Seyoon Ragavan, Vinod Vaikuntanathan
In this work, we introduce a new toolkit for analyzing cloning games, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. T…
Space-Efficient and Noise-Robust Quantum Factoring
Seyoon Ragavan, Vinod Vaikuntanathan
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution…
On the cut-query complexity of approximating max-cut
Orestis Plevrakis, Seyoon Ragavan, S. Matthew Weinberg
We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [RSW18]. Graph algorithms in this cut query model and…
A Proof of The Triangular Ashbaugh-Benguria-Payne-Pólya-Weinberger Inequality
Ryan Arbon, Mohammed Mannan, Michael Psenka +1
In this paper, we show that for all triangles in the plane, the equilateral triangle maximizes the ratio of the first two Dirichlet-Laplacian eigenvalues. This is an extension of w…