1 citations · 1 across the 9 of their papers we have counts for
14 papers
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher +1
We study the one-way communication complexity of the -Boolean Hidden Partition problem. Here, Alice is given an -bit string and Bob is given disjoint blocks of its ind…
Learning Gaussian optical states with quantum computers
Spencer Dimitroff, John Kallaugher, Ashe Miller +1
Recent results have established dramatic advantages in learning properties of quantum states when a quantum computer is available to process or jointly measure multiple copies of t…
Hamiltonian Locality Testing via Trotterized Postselection
John Kallaugher, Daniel Liang
The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro,Oufkir `24], is to determine whether a Hamiltonian is -close to being -local (…
How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
John Kallaugher, Ojas Parekh, Nadezhda Voronova
A series of work [GKK+08, Kal22, KPV24] has shown that asymptotic advantages in space complexity are possible for quantum algorithms over their classical counterparts in the stream…
Complexity Classification of Product State Problems for Local Hamiltonians
John Kallaugher, Ojas Parekh, Kevin Thompson +2
Product states, unentangled tensor products of single qubits, are a ubiquitous ansatz in quantum computation, including for state-of-the-art Hamiltonian approximation algorithms. A…
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
John Kallaugher, Ojas Parekh, Nadezhda Voronova
While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work…
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
John Kallaugher, Ojas Parekh
We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and Krachun [STOC `19] resolved th…
Simulating Random Walks in Random Streams
John Kallaugher, Michael Kapralov, Eric Price
The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounde…
Factorial Lower Bounds for (Almost) Random Order Streams
Ashish Chiplunkar, John Kallaugher, Michael Kapralov +1
In this paper we introduce and study the \textsc{StreamingCycles} problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental i…
A Quantum Advantage for a Natural Streaming Problem
John Kallaugher
Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [S…
An Optimal Algorithm for Triangle Counting in the Stream
Rajesh Jayaram, John Kallaugher
We present a new algorithm for approximating the number of triangles in a graph whose edges arrive as an arbitrary order stream. If is the number of edges in , the n…
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher, Eric Price
A longstanding observation, which was partially proven in \cite{LNW14,AHLW16}, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivi…
The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher, Michael Kapralov, Eric Price
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database pr…
A Hybrid Sampling Scheme for Triangle Counting
John Kallaugher, Eric Price
We study the problem of estimating the number of triangles in a graph stream. No streaming algorithm can get sublinear space on all graphs, so methods in this area bound the space…