For general graphs, the algorithm’s running-time bound grew nearly as the square of the number of points when finding the largest set of non-overlapping links.For general graphs, the algorithm’s running-time bound grew nearly as the square of the number of points when finding the largest set of non-overlapping links.
Iman Gholami, Ilya Hajiaghayi, MohammadTaghi Hajiaghayi et al.
The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges…The online Steiner Forest problem is a fundamental network design problem in which terminal pairs arrive one at a time and an algorithm must irrevocably purchase edges connecting each pair.
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita et al.
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring?The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar…
Standard graph methods could not guarantee search times growing more slowly than the dataset’s size, even with arbitrarily loose approximations.Standard graph methods could not guarantee search times growing more slowly than the dataset’s size, even with arbitrarily loose approximations.
Mark Bun, Mandar Juvekar
The sign rank of a ± 1-valued matrix A is the minimum rank of a real matrix that agrees with A entrywise in sign.The sign rank of a ± 1-valued matrix A is the minimum rank of a real matrix that agrees with A entrywise in sign. For every sufficiently large d, we give an explicit matrix A with 2^(Θ(d^2)) rows and columns and sign rank Θ(d)…
Zongjun Yang, Rachitesh Kumar, Christian Kroer
We consider T repeated second-price auctions across n pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve…We consider T repeated second-price auctions across n pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective…
Yang P. Liu, Kheeran Naidu, Hoai-An Nguyen et al.
We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model.We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model.
Sirui Liu, Zongpeng Li, Baochun Li
In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast…In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast settings.
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi et al.
We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function f: 2^N → R⁺ and a matroid $M(N, I)$…We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function f: 2^N → R⁺ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal…
The preprint proves that pairwise arc-disjoint directed paths from all senders to each receiver ensure unit flows between matched pairs in an undirected network.The preprint proves that pairwise arc-disjoint directed paths from all senders to each receiver ensure unit flows between matched pairs in an undirected network.
Andrew Krapivin, William Kuszmaul
In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to 1 - ε (for some parameter ε ∈ (0, 1)), while supporting…In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to 1 - ε (for some parameter ε ∈ (0, 1)), while supporting queries, insertions, and deletions in worst-case time O(log…
Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang et al.
We study the fundamental problem of PAC learning positive linear combinations of k arbitrary ReLU activations on R^d with respect to the Gaussian distribution, in L₂…We study the fundamental problem of PAC learning positive linear combinations of k arbitrary ReLU activations on R^d with respect to the Gaussian distribution, in L₂ loss.
Haoming Wang, Ming Yuan
We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices.We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between p…
Nicolas Christianson
We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in R^d with ℓ_p movement costs for any p ∈ [1, ∞).We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in R^d with ℓ_p movement costs for any p ∈ [1, ∞). Previously, the best known lower bound for general p was Ω(max{√d, d^(1-1/p)}), established by…
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We give a combinatorial algorithm that computes an exact minimum-cost flow in n^(2+o(1)) time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87]…We give a combinatorial algorithm that computes an exact minimum-cost flow in n^(2+o(1)) time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs.
Ziyad Benomar, Vianney Perchet
We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to…We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time.
A mathematical proof establishes an optimal lower bound on nondeterministic communication for graph connectivity, resolving a problem that remained open for decades.A mathematical proof establishes an optimal lower bound on nondeterministic communication for graph connectivity, resolving a problem that remained open for decades.
Alexander Meiburg
Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer.Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer.
Deepak Bhati, Pranjal Dutta, Antoine Joux et al.
The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum.The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime M = 2^(o(n)), where the pigeonhole principle guarantees that…
The mathematical method calculates approximate fixed points for nonexpanding mappings and shows that simple stochastic games can be solved in quasipolynomial time.The mathematical method calculates approximate fixed points for nonexpanding mappings and shows that simple stochastic games can be solved in quasipolynomial time.
Priyanshu Pant, Ranveer Singh
A graph is called Pfaffian if it admits a Pfaffian orientation. The Pfaffian recognition problem asks whether a given graph is Pfaffian.A graph is called Pfaffian if it admits a Pfaffian orientation. The Pfaffian recognition problem asks whether a given graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that this problem is polynomial time equivalent to…
Nathan Doumèche
Physics-informed machine learning incorporates physical knowledge into data-driven models, often through a partial differential equation (PDE) that the target is assumed…Physics-informed machine learning incorporates physical knowledge into data-driven models, often through a partial differential equation (PDE) that the target is assumed to satisfy.
Inhyuk Park, Chenglin Fan
We show that for all polynomials T and b, every relation in NTIME(T) has a binary PCP with O(1) non-adaptive queries, perfect completeness, soundness error 1/2 and length…We show that for all polynomials T and b, every relation in NTIME(T) has a binary PCP with O(1) non-adaptive queries, perfect completeness, soundness error 1/2 and length (T+b)·(log(T+b))^(O(1)), which is perfect zero knowledge…
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina et al.
We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium.We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium.
Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang et al.
We give a polynomial-time algorithm that achieves an α_GW + Ω(1/d)-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most d…We give a polynomial-time algorithm that achieves an α_GW + Ω(1/d)-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most d constraints.
Rafael Pass
We give a self-contained constructive proof that the matrix multiplication exponent satisfies ω≤9/4. This bound was recently claimed by OpenAI~cite{original} through…We give a self-contained constructive proof that the matrix multiplication exponent satisfies ω≤9/4. This bound was recently claimed by OpenAI~cite{original} through non-constructive arguments in Strassen's asymptotic spectral…
Florestan Brunck, Christoph Hertrich, Kilian Ruess et al.
We prove that every ReLU network can be exactly simulated by a ReLU network with two hidden layers. We present two proofs: one that is based on fillings in homological…We prove that every ReLU network can be exactly simulated by a ReLU network with two hidden layers. We present two proofs: one that is based on fillings in homological algebra and a direct combinatorial proof.
Maciej Skórski
Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie R'enyi entropy, a fundamental measure…Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie R'enyi entropy, a fundamental measure of uncertainty with applications in cryptography, machine…
Jan van den Brand, Adam Karczmarz, Aryan Patel
We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two…We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported.
Simon Mackenzie, Mashbat Suzuki
Envy-free cake cutting asks how to divide a resource so that no agent prefers another agent's share. Finding such a division with few queries about preferences has been a…Envy-free cake cutting asks how to divide a resource so that no agent prefers another agent's share. Finding such a division with few queries about preferences has been a longstanding challenge.
Tuan Truong Vu, Cheng Tan
GPU kernels are critical to the performance of today's AI services, yet the same operators are rewritten repeatedly: for each GPU generation, numeric format, serving…GPU kernels are critical to the performance of today's AI services, yet the same operators are rewritten repeatedly: for each GPU generation, numeric format, serving regime, and kernel language.
Jaeho Hwang, Byung-Sun Won, Uiwon Hwang
Maximum-likelihood (ML) decoding of linear block codes is NP-hard, so neural decoders are evaluated by how closely they approach it.Maximum-likelihood (ML) decoding of linear block codes is NP-hard, so neural decoders are evaluated by how closely they approach it. We observe that proving a candidate optimal can be far easier than finding it, and build a…
Xin Li, Yan Zhong
We give a short-description decomposition of bounded-width CNFs. For every fixed ε>0, every width-b CNF on m variables is an exact disjoint union of at most 2^(ε m)…We give a short-description decomposition of bounded-width CNFs. For every fixed ε>0, every width-b CNF on m variables is an exact disjoint union of at most 2^(ε m) width-b CNFs, each determined by 2^(O_ε(b))log(m+1) satisfying…
Panagiotis Kanellopoulos, Themistoklis Melissourgos
Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems.Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems. Despite their importance, the complexity of finding approximate solutions has remained unresolved for a…
Lin Chen, Yuchen Mao, Guochuan Zhang
We study integer programs in standard form min{c^Tx:Ax=b, lleqxlequ, xinZⁿ}, where AinZ^(d× n) and all entries of b,c,l,u are integers.We study integer programs in standard form min{c^Tx:Ax=b, lleqxlequ, xinZⁿ}, where AinZ^(d× n) and all entries of b,c,l,u are integers. Let N be an upper bound on the absolute values of the entries of A.
Edith Cohen, Uri Stemmer
Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection.Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially…
Adelmo Morrison Orozco, Nathan Sheffield, Ryan Williams
We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded…We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation.
Baochun Li, Zongpeng Li, Sirui Liu
Network coding allows intermediate nodes to combine messages. Fractional routing instead splits each message among source-destination paths and forwards its parts without…Network coding allows intermediate nodes to combine messages. Fractional routing instead splits each message among source-destination paths and forwards its parts without combining different messages.
Igor C. Oliveira
We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large…We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime.
Tatsuya Terao
We present a simple deterministic semi-streaming algorithm that computes a (1-ε)-approximate maximum matching in general graphs in O(1/ε²) passes.We present a simple deterministic semi-streaming algorithm that computes a (1-ε)-approximate maximum matching in general graphs in O(1/ε²) passes.