44 papers
This paper establishes the first explicit -hardness results for the approximate Covering Radius Problem on lattices in norms for sufficiently large (specifically ), proving that the problem remains hard even for approximation factors approaching $9/8p$ tends to infinity.
This paper establishes that Tetris clearing and survival are NP-hard for any single tetromino type except the O-piece under the Super Rotation System, disproving a long-standing conjecture about the I-piece, while simultaneously providing polynomial-time algorithms for cases involving only dominoes or $1\times k$ pieces under specific initial board conditions.
This paper improves the running time of -approximation algorithms for -median and -means clustering in low-dimensional Euclidean spaces to $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)1/\varepsilond$ is essentially optimal.
This paper proposes a unifying framework for Boolean tensor network complexity dichotomy theorems that classifies unresolved problems into nine cases based on finite group structures of binary functions, resolving higher-order cyclic group cases and advancing the order-1 case while identifying barriers involving quaternion subgroups.
This paper explicitly establishes that the optimum circuit size changes by at most under truth table perturbations, extending the bound to general Hamming distances and verifying its tightness at through exhaustive SAT-based analysis.
This paper resolves the open question regarding the parameterized complexity of QBF with few existential variables by proving that the previously known double-exponential dependence on the number of existential variables is optimal under the ETH for general CNFs, while demonstrating that the problem becomes significantly more tractable for formulas with only two quantifier blocks.
This paper introduces AlphaEvolve, an LLM-based code mutation agent that serves as a unified meta-algorithm to improve the lower bounds of five classical Ramsey numbers and successfully recover or match existing bounds across various cases, demonstrating a shift from bespoke search methods to a single, adaptable framework for combinatorial structure generation.
This paper argues that quantum computational advantage has indeed been achieved, despite the lack of consensus, and outlines future directions for theory and experiments in the field.
This paper presents a simplified and fully analyzed sublinear-time algorithm that achieves a -approximation of the average degree in bounded arboricity graphs using queries, thereby recovering logarithmic factors lost in previous work and offering a modified version with query complexity.
This paper introduces permutation match puzzles on grids, characterizing their solvability via an acyclic constraint graph condition, providing a hook length formula for counting solutions, offering an algorithm for minimal repairs in the basic case, and proving that generalizing the problem to arbitrary permutations renders minimal repair NP-complete.
This paper establishes that the size difference between optimal Boolean circuits and formulas over the AIG basis is strictly limited to 0 or 1, characterizing the precise conditions under which sharing occurs and proving that any non-zero gap arises exclusively from a single gate with fan-out 2.
This paper proposes a unified, domain-agnostic framework for computing the bus-factor by modeling projects as bipartite graphs, proving the NP-hardness of both redundancy and criticality formulations, and introducing a novel robustness-based measure with efficient linear-time approximations that outperforms existing methods in capturing project risk and fragmentation.
This paper presents deterministic polynomial-time algorithms and new structural bounds for factoring sparse polynomials with bounded individual degree, including recovering irreducible factors from blackbox access and improving upon previous runtime complexities for sparse polynomial factorization.
This paper presents a novel automated method combining the substitution technique with systematic backtracking and dynamic programming to prove that the bilinear complexity of $3 \times 3\mathbb{F}_2$ is at least 20, thereby improving the previous lower bound of 19.
This paper presents a polynomial-time algorithm for testing the isomorphism of finite groups that are extensions of abelian groups by -generated groups (including abelian-by-cyclic and abelian-by-simple cases), achieved through a novel method for computing the unit group of a finite ring.
This paper compares three fixed-dimension satisfiability semantics for quantum logic—standard Hilbert-lattice, global commuting-projector, and local partial-Boolean—proving a strict hierarchy where the standard semantics is strictly more expressive than the others, as demonstrated by an explicit formula that is satisfiable in the standard semantics but unsatisfiable under the other two for all dimensions .
This paper demonstrates that a specific polynomial-time decision problem, defined by causal token traversal constraints, inherently requires linear time to execute and cannot be accelerated by parallel computation, thereby revealing a fundamental gap between logical parallelism and causal executability that places the problem outside the classical complexity class.
This paper establishes a base change framework to extend tensor function results from specific fields to general fields, thereby proving that slice rank is linearly bounded by geometric rank and is quasi-supermultiplicative for any 3-tensors over any field.
This paper presents a differentially private scheme for estimating black-box statistics that effectively trades off between statistical efficiency and oracle efficiency, accompanied by lower bounds demonstrating the near-optimality of this approach.
Assuming the hardness of the Learning with Errors (LWE) problem, the paper proves that no quantum algorithm can weakly automate proof search in the -Frege propositional proof system, marking the first established connection between quantum computation and the limitations of automated propositional proof search.