Barna Saha, Christopher Ye
In this note, we provide a deterministic algorithm that computes the (min, +)-Matrix Product $C = A * B$ of two N × N matrices A and B with polynomially bounded integer…In this note, we provide a deterministic algorithm that computes the (min, +)-Matrix Product $C = A * B$ of two N × N matrices A and B with polynomially bounded integer entries in O(N^(2.9964)) time, improving upon the exponent of…
Paul Duetting, Michal Feldman, Mathieu Molina
We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio.We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve 1-e/e^e≈0.8206, matching the upper bound of Chierichetti…
Mina Dalirrooyfard, Christopher Ye
Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of…Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of special token segmentation, pretokenization, and byte-pair…
Seri Khoury, Aaron Schild
We prove that o(log n/loglog n)-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input.We prove that o(log n/loglog n)-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input.
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann et al.
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location…The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus the engine behind the best k-median guarantees, for…
Ruhollah Majdoddin
Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with…Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with exponents 1.9992 for 3SUM, 2.9983 for Exact Triangle and…
A proof showed that Glauber dynamics, with cooling and time averaging, recovered hidden signs above the known algorithmic threshold from a random start.A proof showed that Glauber dynamics, with cooling and time averaging, recovered hidden signs above the known algorithmic threshold from a random start.
Muntaser Syed, Ameerah Alsulami, Marius Silaghi
Serving stacks for large language models manage context through four recurring mechanisms: incremental edits to a growing context, branching and snapshotting for tree…Serving stacks for large language models manage context through four recurring mechanisms: incremental edits to a growing context, branching and snapshotting for tree search, identification of reusable prefixes for KV-cache reuse…
Rajan Udwani, David Wajc
We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite…We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords.
Adam Karczmarz, Michał Włodarczyk
We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if…We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another.
Nick Arnosti, Rad Niazadeh, Pranav Nuti et al.
We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and…We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their…
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time…Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open.
Henry Fleischmann, Jason Li, Thatchaphol Saranurak et al.
We give a randomized reduction from global minimum cut in a directed graph with n vertices and m weighted edges to maximum-flow computations on graphs of total size O(m).We give a randomized reduction from global minimum cut in a directed graph with n vertices and m weighted edges to maximum-flow computations on graphs of total size O(m).
Jeff Giliberti, MohammadTaghi Hajiaghayi, Changki Yun
In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete. An optimal tree edge ranking assigns positive integer ranks to the edges such…In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete. An optimal tree edge ranking assigns positive integer ranks to the edges such that any two edges with the same rank are separated by an…
Erik D. Demaine, Stefan Langerman
We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by…We prove co-RE-completeness, and thus undecidability, of the following problem: given a single (connected) polycube, decide whether it tiles 3D Euclidean space by translations.
Noam Mazor, Andrew Morgan, Rafael Pass
A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information…A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with…
A preprint proved that a fundamental subset problem can be solved faster than a longstanding limit, translating directly to database query optimization.A preprint proved that a fundamental subset problem can be solved faster than a longstanding limit, translating directly to database query optimization.
Saeed Amiri, Sebastian Siebertz
For every fixed proper minor-closed class mathscr C and every ε>0, we give a deterministic LOCAL algorithm that returns a dominating set of size at most (2a(mathscr…For every fixed proper minor-closed class mathscr C and every ε>0, we give a deterministic LOCAL algorithm that returns a dominating set of size at most (2a(mathscr C)+1+ε)γ_f(G) on every G∈mathscr C.
James Fox, David P. Woodruff
Given value-oracle access to a symmetric submodular function f:2^VtoR with |V|=n, a nontrivial minimizer can be found using O(n³) value queries.Given value-oracle access to a symmetric submodular function f:2^VtoR with |V|=n, a nontrivial minimizer can be found using O(n³) value queries.
A preprint proves that the subset sum problem can be solved faster than the meet-in-the-middle barrier by using a partial match algorithm.A preprint proves that the subset sum problem can be solved faster than the meet-in-the-middle barrier by using a partial match algorithm. The approach built on the representation technique framework of Randolph and Węgrzycki.
Nick Fischer, Ce Jin, Yinzhan Xu
Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional…Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bounds for fundamental problems.
Nick Fischer, Adam Polak, Jonas Schmidt
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued…We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs.
A constructed network supported 157 sessions at a coding rate of at least 1, while standard routing reached at most 147/157.A constructed network supported 157 sessions at a coding rate of at least 1, while standard routing reached at most 147/157. In a preprint, a theory paper refuted the undirected multiple-unicast conjecture by constructing a…
Researchers disproved a 2004 conjecture by constructing an undirected network where combining messages achieves a rate strictly above the maximum fractional routing rate.Researchers disproved a 2004 conjecture by constructing an undirected network where combining messages achieves a rate strictly above the maximum fractional routing rate.
Yiwen Kou, Yimeng Wang
Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading…Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds.
Vincent Liew
SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this…SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon.
Zhewei Wei
We show that the worst-case combinatorial discrepancy of n points in the plane with respect to axis-parallel rectangles is Θ(log^(3/2)n).We show that the worst-case combinatorial discrepancy of n points in the plane with respect to axis-parallel rectangles is Θ(log^(3/2)n). The known bounds were Ω(log n) and O(log^(3/2)n); we prove the matching lower bound.
Hanqing Li
We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables.We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables.
Rong-Hua Li, Yichun Yang, Junjie Zhou
We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph G.We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph G. We focus on the eps-error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 & Internet Math 2007].
A preprint proves faster deterministic methods for 3SUM on integers and All-Pairs Shortest Paths on directed graphs, refuting both longstanding computational hypotheses.A preprint proves faster deterministic methods for 3SUM on integers and All-Pairs Shortest Paths on directed graphs, refuting both longstanding computational hypotheses.
Xiaoyu Chen, Kuikui Liu
We design the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by their independence oracles.We design the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by their independence oracles.
Jörg Endrullis, Ievgen Ivanov, Femke van Raamsdonk
Confluence is a fundamental property of nondeterministic computations, arising from parallelism, concurrency, or freedom in the evaluation order.Confluence is a fundamental property of nondeterministic computations, arising from parallelism, concurrency, or freedom in the evaluation order.
Siu On Chan, Jeff Xu
We give a classical polynomial-time algorithm that strongly refutes random quantum 3-SAT at sufficiently large constant constraint density, thereby disproving the quantum…We give a classical polynomial-time algorithm that strongly refutes random quantum 3-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random 3-SAT hypothesis.
Chenghua Liu, Boning Meng
We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit…We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion for tractability.
Prithwish Jana, Viet Bach Hoang, Logan Luna et al.
Proof auto-formalization translates natural-language (NL) theorems and proofs into a formal language (FL) such as Lean, enabling mechanical verification.Proof auto-formalization translates natural-language (NL) theorems and proofs into a formal language (FL) such as Lean, enabling mechanical verification.
Dongchen Li, Hanyu Li
The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for ε-approximate Nash equilibria.The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for ε-approximate Nash equilibria.
Pedro Montealegre, Martín Ríos-Wilson
We prove that prediction for the synchronous two-dimensional majority rule is P-complete under logspace many-one reductions, resolving a problem open for almost three…We prove that prediction for the synchronous two-dimensional majority rule is P-complete under logspace many-one reductions, resolving a problem open for almost three decades.
Alper Cakan
Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007).Whether some problems require quantum proofs has been a central question in quantum complexity (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC 2007).
Tushant Mittal, Shashank Srivastava, Madhur Tulsiani et al.
We show that for any R,ε >0 and any prime p≥ 2, there exists an infinite family of p-ary quantum low-density parity-check (QLDPC) codes, rate R, checks of weight O_ε(1)…We show that for any R,ε >0 and any prime p≥ 2, there exists an infinite family of p-ary quantum low-density parity-check (QLDPC) codes, rate R, checks of weight O_ε(1), and normalized distance at least δ_GV(p,R)-ε.
V. Arvind, Pushkar S. Joglekar
The rational identity testing problem, RIT, asks whether an input rational circuit, computes the zero element of the free skew field.The rational identity testing problem, RIT, asks whether an input rational circuit, computes the zero element of the free skew field. For rational formulas the problem is known to be in deterministic polynomial time.