44 papers
This paper proposes an alternative quantum information advantage protocol based on parallel-repeated CHSH games that utilizes an information-based memory measure, offering an efficient verifier and a more noise-robust, efficient quantum prover compared to the recent experimental demonstration by Kretschmer et al.
This paper proves that determining whether a computable strategy guarantees a win in the Yu-Gi-Oh! Trading Card Game is an undecidable problem that is actually -complete, demonstrating this by constructing legal decks capable of reducing the Halting Problem and the set of countable well orders to the game's winning condition.
This paper establishes new separations between shallow-depth quantum circuits (specifically those with quantum advice or Toffoli gates with mid-circuit measurements) and classical constant-depth circuits, while also demonstrating that infinite-size gate sets in can implement threshold gates and that higher-dimensional qudit circuits offer no advantage over standard qubit implementations in this regime.
This paper proposes a unified framework for the generation-recognition asymmetry in formal language theory by identifying six distinct dimensions of divergence, challenging the oversimplified view that generation is inherently easy while parsing is hard, and exploring the implications of these operational differences for fields ranging from compiler design to large language models.
This habilitation thesis investigates polynomial algorithmics under space constraints, presenting time- and space-efficient algorithms for fundamental operations and introducing the first quasi-linear algorithm for sparse polynomial interpolation while addressing hard problems in sparse factorization and divisibility.
This paper reinterprets NP witness discovery as an information-acquisition process and demonstrates that in a structureless "psocid" model where witnesses are accessed only via equality probes, the exponentially limited information gain per probe fundamentally prevents reliable recovery within polynomial time, thereby revealing an informational origin for exponential search complexity.
This paper establishes a necessary and sufficient condition for the classical simulability of polynomial-size quantum circuits followed by sparse classical post-processing and demonstrates that constant-depth variants of such circuits can be efficiently simulated by a probabilistic algorithm using commuting quantum circuits with bounded gate complexity.
This paper presents a novel ResultantSolver algorithm that efficiently solves a specific polynomial system over a finite field by exploiting its structured sparsity to compute a univariate polynomial via successive resultants, significantly outperforming both brute-force and standard Gröbner basis methods.
This paper establishes an exact correspondence between the computational power of recurrent graph neural networks and recurrent arithmetic circuits over real numbers by demonstrating their mutual ability to simulate each other's computations.
This paper addresses the computational challenges of generalizing fair top- selection to multiple protected groups while minimizing disparity from a reference function, revealing new hardness barriers for small and proposing an efficient, robust two-pronged solution that incorporates utility loss as an alternative disparity measure.
This paper establishes a theoretical foundation for the superior parallelizability of linear RNNs by demonstrating that they correspond to log-depth arithmetic circuits (-complete), whereas nonlinear RNNs are fundamentally limited by their ability to solve - and -complete problems, thereby explaining why linear variants can be efficiently parallelized like transformers while traditional nonlinear RNNs cannot.
This paper presents a complete classification of the distributed computational complexity for local optimization problems in directed cycles within both deterministic and randomized LOCAL models, identifying four distinct complexity classes and providing an efficient meta-algorithm to automatically determine the complexity and synthesize optimal distributed algorithms for any given problem.
This paper introduces a novel "deferred local-ratio" technique to present a $4/3O(m\sqrt{n})$ time, offering a faster alternative to existing state-of-the-art methods without relying on complex enumeration or LP rounding.
This paper investigates the complexity of restricted fragments of Decision DNNF, specifically -OBDD and Structured Decision DNNF, by establishing lower bounds for CNFs of bounded incidence treewidth, demonstrating exponential separations between various models, identifying efficient cases for the Apply operation, and introducing a relaxed model called Structured -FBDD that effectively handles CNFs of bounded incidence treewidth.
This paper proves that the Maximum Partial List H-Coloring problem is solvable in polynomial time on P_5-free graphs for any fixed graph H, thereby resolving an open question from SODA 2024 and improving upon a previous algorithm by Chudnovsky et al.
This paper resolves the open question regarding the parameterized complexity of the Optimal Morse Matching problem by presenting a $2^{O(k \log k)} n$-time algorithm for bounded-treewidth complexes and proving its optimality under the Exponential Time Hypothesis.
This paper presents and validates quantum algorithms based on Grover's search that solve the NP-complete Network Signal Coordination (NSC) problem and its robust variants, achieving quadratic speedups and maintaining efficiency even when the solution space fraction decays polynomially with network size.
This paper presents efficient classical algorithms for the and Constrained Integer Solution problems previously solved by an efficient quantum algorithm, thereby demonstrating that no exponential quantum speedup exists for these tasks.
This paper introduces SCORE, a reversible programming language that utilizes a proof-assisted state space to ensure all stack manipulation operations are interpreted as total bijective functions, thereby overcoming the limitations of traditional partial bijection approaches and enabling the study of computational complexity in fully reversible models.
This paper proves that the Aaronson-Ambainis conjecture holds for a non-negligible fraction of random restrictions applied to bounded-degree polynomials with sufficient variance, demonstrating that such restrictions typically yield a coordinate with significant influence.