Complexity and Algorithms in Graphs

Últimos artículos

• A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

  Santosh S. Vempala · 25 de septiembre de 2026

  We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling,…

• Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

  Shi Fu, Youming Qiao, Dacheng Tao, Zongqi Wan, Qixin Zhang · 23 de septiembre de 2026

  Over the past decade, a growing body of research has shown that $\gamma$-weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural network pruning, and video summarization. Despite its prevalence, maximizing a $\gamma$-weakly submodular function subjec…

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

  Shi Fu, Qixin Zhang, Dacheng Tao · 10 de septiembre de 2026

  Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most $k$ available elements and changes only $O(1)$ elements after …

• Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

  Vaneet Aggarwal, Yiyang Lu · 3 de septiembre de 2026

  We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adv…

• On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problems

  Ali Hussaini Umar, Jean Barbier, Matthieu Jonckheere, Manuel Sáenz · 20 de agosto de 2026

  Hard combinatorial optimization problems, many of which are NP-hard, present fundamental algorithmic challenges. Average-case analysis on random instances has emerged as a powerful framework for understanding typical algorithmic performance beyond worst-case guarantees. A substantial body of work ha…

• Correlation Clustering with Random Partial Information

  Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari · 18 de agosto de 2026

  Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the t…

• Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students

  Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan · 17 de agosto de 2026

  This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a s…

• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

  Vaneet Aggarwal · 13 de agosto de 2026

  We study nonnegative submodular maximization subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity…

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

  Michael Menart, Aleksandar Nikolov, Ohad Shamir · 29 de julio de 2026

  We prove two lower bounds for the first order oracle complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory. We first show that any such (possibly randomized) algorithm must make $\tilde{\Omega}(\frac{d^2}{\sqrt{m}})$ oracle queries. For d…

• Encoding orders and trees in real-valued functions

  G Conant, C Terry · 27 de julio de 2026

  We prove function-theoretic analogues of a quantitative result of Hodges on extracting the order property from a sufficiently large 2-tree coded in a binary relation. Similar analogues for functions were previously obtained by Daskalakis and Golowich and by Anderson and Benedikt. These results are f…

• Shallower ReLU Network Representations via Exact Linear Algebra

  Kilian Rue{\ss}, Gennadiy Averkov, Florestan Brunck, Moritz Grillo, Christoph Hertrich, Georg Loho, Jack Stade, Moritz Stargalla, Matthew Sun, Martin Winter · 27 de julio de 2026

  We prove that the maximum of $n$ real numbers is exactly representable by a ReLU network with two hidden layers for every $n\le 10$. The constructions are obtained by reducing the problem to exact rational linear algebra: after a symmetry reduction, the necessary cancellations are encoded in finite …

• Autonomous disproofs of the sum-product conjecture over $\mathbb R$ with GPT-5.5 Pro

  Yichen Huang · 24 de julio de 2026

  OpenAI's recent disproof of the Erd\H{o}s unit distance conjecture marked a milestone for AI in mathematics. It also inspired another breakthrough: a human disproof of the Erd\H{o}s--Szemer\'edi sum-product conjecture over $\mathbb R$. In this paper, we present a simple agent built on GPT-5.5 Pro. U…

• The Dimension of Nonterminating Resampling Computations

  Yunbei Xu · 21 de julio de 2026

  A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the …

• Regularity as seen by Alice and Bob

  Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez, Rafał Stefański · 16 de julio de 2026

  The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in communication complexity, we generalize the setting by relaxing the computability assumptions and allowing non-Boolean o…

• Graph Partitioning with Demands: Generalized Conductance and its Applications

  Micha{\l} Szyfelbein, Dariusz Dereniowski · 16 de julio de 2026

  In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph $G=(V,E,c,w)$ with a capacity function $c\colon E\to \mathbb{N}$ and a demand function $w\colon V\times V\to \mathbb{N}$. Our main focus is the problem of finding a cut $(…

• Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

  Micha{\l} Szyfelbein, Dariusz Dereniowski · 16 de julio de 2026

  Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a …

• Tropical Circuits with Scalar Multiplication Gates

  Christoph Hertrich, Moritz Stargalla · 14 de julio de 2026

  We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement $\max$, $+$, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bi…

• Data-dependent Evaluations for Budgeted Submodular Maximization

  Lejian Zhang, Xueyan Tang, Jing Tang · 8 de julio de 2026

  Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is n…

• Active Learning on Adversarially Corrupted Graphs

  Marco Bressan, Nicol\`o Cesa-Bianchi, Tommaso d`Orsi, Emmanuel Esposito, Silvio Lattanzi · 7 de julio de 2026

  Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} inside a graph $G^*$. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the …

• AI-Assisted Discovery of Convex Relaxations via Dual Agents

  Sungyoon Kim, Mert Pilanci · 1 de julio de 2026

  Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighte…

• Local-Minima-Preserving Continuous Relaxation of Ising Problems

  Debraj Banerjee, Santanu Mahapatra, Kunal N. Chaudhury · 30 de junio de 2026

  The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landsc…

• FactorLibrary: From Polynomials to Circuits via Recursive Subgoals

  Rohan Pandey, Michael Ruofan Zeng, Weikun K. Zhang, Kaijie Jin, Naomi Morato, Archit Ganapule, Bhaumik Mehta, Jarod Alper · 25 de junio de 2026

  Finding minimal arithmetic circuits for polynomials over finite fields is a combinatorially hard problem central to algebraic complexity theory. We formulate it as a reinforcement learning problem in two directions, bottom-up and top-down. To address the challenge of a fast-growing combinatorial sea…

• Representing Piecewise-Linear Functions by Functions with Minimal Arity

  Christoph Koutschan, Anton Ponomarchuk, Josef Schicho · 19 de junio de 2026

  Any continuous piecewise-linear function $F\colon \mathbb{R}^{n}\to \mathbb{R}$ can be represented as a linear combination of $\max$ functions of at most $n+1$ affine-linear functions. In our previous paper [``Representing piecewise linear functions by functions with small arity'', AAECC, 2023], we …

• Efficiently Representing Algorithms With Chain-of-Thought Transformers

  Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill · 19 de junio de 2026

  The increasing popularity of \emph{reasoning} models -- language models that output a series of reasoning or thought tokens before producing an answer -- is justified, in part, by theoretical results showing that chain-of-thought (CoT) transformers can simulate Turing machines, and thus perform arbi…

• Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

  Ishant Shanu · 9 de junio de 2026

  Submodular function minimization has gained a lot of interest in recent years. They are highly applicable in the area of Computer Vision and Machine Learning. Often such applications require to work with submodular functions defined on distributive lattice. Current best way of dealing with it is usi…