Papers nuevos sobre Algoritmos y complejidad

Lo mejor de la semana

• Computación/Algoritmos y complejidad22 de sept de 2026

  Smoothed Analysis of Inconsistent A*

  Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^{2}m\kappa )$, where $n$ is the number of nodes, $m$ is the number of edges, and $\kappa$ controls the scale of random perturbations.

  Zhiyang Chen, Hailong Yao — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Hardness of Online Directed Steiner Network

  In this work, we show the first such unconditional, information-theoretic hardness.

  Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi y 1 más — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

  In this work we present BOLIDE, the first efficient and practical algorithm for estimating binned degree-wise clustering coefficients in streaming.

  Cristian Boldrin, C. Seshadhri — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  Watermarkable Multi-Draft Speculative Sampling via Poisson Processes

  In this work, we develop a novel multi-draft speculative sampling algorithm based on Poisson processes that improves the frontier of this fundamental trade-off.

  Yanxiao Liu, Sicheng Wan, Zhan Gao y 1 más — arXiv

  PreprintAfirmaciones fuertes, leer con cuidadoDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

  Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.

  Bo Liu — arXiv

  PreprintAfirmaciones fuertes, leer con cuidadoDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

  We prove two main algorithmic results in spectral discrepancy.

  Ali Jadbabaie, Amin Saberi, Suvrit Sra — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  A General Composition Theorem for Approximate Degree

  We resolve this question for all total Boolean functions by proving the matching lower bound.

  Samruddhi Pednekar, Supartha Podder — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad24 de sept de 2026

  Fast Geometric Spanners via Approximate Nearest Neighbor Search

  In particular, we show the following results for any metric space $\mathsf{M}=([n],\mathsf{d})$ with aspect ratio $\Delta$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime ${\tau }_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k\in \mathbb{N}$, constructs an $O(ck)$-distortion spanner with $\tilde{O}(k{n}^{1+1/2k}\log \Delta )$ edges and runs in time $\tilde{O}({\tau }_{\mathsf{M}}\cdot k{n}^{1/k}\log \Delta )$.

  Alexandr Andoni, Manuel Paez, Krish Singal y 1 más — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  4-Block Integer Programming is in FPT

  We resolve this question in the positive by providing an FPT time algorithm that solves general 4-block integer program.

  Martin Kouteck\'y, Alexandra Lassota, Koen Ligthart — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Parameter-Free Triangle Counting

  We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of $T$ or any quantities depending on $T$, provided $m$, the length of the stream.

  Asaf Etgar, Anna Gilbert, Quanquan Liu y 1 más — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Strategic Classification Has a Missing Lever: Audit Risk

  In this paper, we propose a model of strategic classification in which the firm jointly designs a linear classifier and an audit profile, which assigns to each fakeable feature a probability of detection and a penalty when caught.

  Raman Ebrahimi, Massimo Franceschetti — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  A Polynomial Kernel for Planar Directed Feedback Vertex Set

  We resolve the planar case by giving a deterministic kernel with $O(k^{66}{\log }^{2}k)$ vertices and arcs.

  Zimo Sheng, Mingyu Xiao — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  A Fixed-Parameter Algorithm for 4-Block Integer Programming

  We give a fixed parameter tractable (FPT) algorithm with running time $f(k,\Delta )\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute matrix entry $\Delta$.

  Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

  We replace both, fine-tune every remaining stage, and obtain the first practical implementation, which runs in space close to the text rather than to the suffix array.

  Jonas Ellert, Lukas Nalbach — arXiv

  PreprintCódigo disponible

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Finding a Positive Index Nash Equilibrium is PPADS-Complete

  We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1.

  Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos y 1 más — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties

  We present a randomized algorithm that computes a $(1+\epsilon )$-approximate minimum-cost bipartite matching with penalties in $O(npoly(\log n,1/\epsilon ))$ time with high probability.

  Eunjin Oh, Seongbin Park, Chanho Song — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  Sharp Lovasz-Theta Bounds on Random Graphs

  In this work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\frac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.

  Aaron Potechin, Jeff Xu — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  An exponential lower bound for the bit pigeonhole principle in resolution over parities

  We prove that every DAG-like $Res(\oplus )$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^{\ell }$ holes has more than $\exp (n/(32768{\ell }^2))=2^{\Omega (n/{\log }^{2}n)}$ clauses, for every $\ell \ge 32$, with no restriction on regularity or depth.

  Kamil Braun — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  A Human-Like Pedestrian Model for Automated Driving Simulations

  Here, we propose an approach to training pedestrian models in simulators so that learned policies generate demonstrably human-like behavior in realistic, complex traffic scenarios, including multiple lanes, heavy traffic, and dangerous driving styles.

  Ruofeng Wang, Patrick Ebel, Philipp Wintersberger y 1 más — arXiv

  PreprintUso en el mundo real

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Vector Balancing in Polynomial Time

  We present a spectral signing algorithm solving the Koml\'os problem with a constant discrepancy in polynomial time.

  Shengtao Guo, Ethan X. Fang, Junwei Lu — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

  We present the first polynomial-time approximation algorithm for this problem.

  Maria Constantin, Adrian Micl\u{a}u\c{s}, Alexandru Popa — arXiv

  PreprintDice ser un gran avance

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Strategic Opinion Manipulation in Multiplex Networks

  We show that this game has a unique Nash equilibrium in closed form, that the resulting consensus is the truthful consensus under a centrality tilted toward a manipulability index of each agent, and that the resulting distortion is the (centrality-weighted) covariance of agents' manipulability and opinions.

  Raman Ebrahimi, Massimo Franceschetti — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  Analysis of trade-offs in urban heat mitigation using a Bayesian Optimization framework for an urban canopy layer model

  Based on an urban street canyon configuration, it was shown that heat mitigation measures that reduce daytime air temperature and UTCI are often associated with higher nighttime temperatures.

  Rebekka Walter, Johanna Gelhaus, David Anton y 2 más — arXiv

  PreprintUso en el mundo real

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  Dynamic Contention Resolution Schemes

  We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs).

  Moran Feldman, Gregory Kehne, Roie Levin y 1 más — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

  We show a tight $O\left(\log (1/p)\cdot \log m+\log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p\cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein.

  Anish Hebbar, Ravi Kumar, Roie Levin y 2 más — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Eventual Nonnegativity of a Matrix Is in P

  We prove that this problem is decidable in deterministic polynomial time.

  Julian D'Costa — arXiv

  PreprintCódigo disponible

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  Factorisability of Low Dimensional Non-Negative Integer Matrices

  We analyse the complexity of primality and finding a factorisation for a composite matrix, providing a first efficient algorithm.

  Paul C. Bell, Eva Foster, Daniel Reidenbach y 1 más — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  Dense Matrices Are Alike; Sparse Matrices Are Sparse in Their Own Way: A Structure-Adaptive Tile Cholesky Factorization

  We let the data structure follow the sparsity structure, across matrices and across tiles within a matrix.

  Esmail Abdul Fattah, Hatem Ltaief, H{\aa}vard Rue y 1 más — arXiv

  PreprintUso en el mundo realCódigo disponible

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Edge-centric Brain Transformer: An Edge-centric Functional Connectivity Learning Framework for fMRI-based Brain Disorder Diagnosis

  Here, we propose an edge-centric brain transformer (EBT) framework that reformulates rs-fMRI analysis as functional connection representation learning.

  Dengyi Zhao, Zhiheng Zhou, Mengyao Zhou y 2 más — arXiv

  PreprintUso en el mundo realCódigo disponible

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  FPT Isomorphism Test for $F$-Free Tournaments

  We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k)\cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments.

  Daniel Neuen — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs

  In contrast, our main contribution is a structural characterization of the optimal design space of reserve functions (i.e., normalized pricing rules) for \OACC, yielding a family of optimal online algorithms.

  Haoxin Sang, Bo Sun, Xiaoqi Tan — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Colour me shocked: Exact Molecular Hessians from local MLIPs in O(N) time using sparse differentiation!

  Based on the insight that we can derive the sparsity pattern for an MLIP's Hessians in closed form, we show in this paper how to use techniques from sparse automatic differentiation to reduce the cost of a local MLIP's Hessians to a system-size-independent number of Hessian-vector products, yielding overall $O(N)$ total cost without any approximations.

  Luca Thiede, Andreas Burger, Al\'an Aspuru-Guzik — arXiv

  PreprintAfirmaciones fuertes, leer con cuidado

  Guardar
• Computación/Algoritmos y complejidad24 de sept de 2026

  Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

  For every $\epsilon >0$, there is a menu size $k_{\epsilon }$ depending only on $\epsilon$ that preserves at least a $(1-\epsilon )$ fraction of the expected maximum-matching size of the full realized graph.

  Sara Ahmadian, Edith Cohen, Mohammad Roghani — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Optimal Analysis of Greedy for Stochastic Online Euclidean Matching

  We prove that Greedy has competitive ratio $O(1)$ for every fixed $d\ne 2$, and $\Theta (\sqrt{\log n})$ for $d=2$.

  Mingwei Yang, Sophie H. Yu — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad24 de sept de 2026

  Pacing Equilibria in Abstract Mechanisms

  We develop a unified theory of pacing equilibria across a hierarchy of mechanisms.

  Salam Afiouni, Christian Kroer — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad24 de sept de 2026

  JEV-Star: Fast, Low-Cost StarCraft II Control with Language-Model Planning

  We present JEV-Star, a StarCraft II controller that defeats the strongest non-cheating built-in AI, Lv7, by combining fast JEV action selection with persistent GPT-6 planning.

  Weiyu Ma, Liangbing Zhao, Yongcheng Zeng y 1 más — arXiv

  PreprintAfirmaciones fuertes, leer con cuidadoCódigo disponible

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

  We prove that the original matrices admit signs with discrepancy $O(\sqrt{\epsilon }\log (2r))$, independently of their dimension and number which is a significantly stronger result than what was known existentially.

  Tarun Kathuria — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  TokaGLINT: A Scalable GPU-Tailored Implicit Solver for Full 3D Tokamak Electromagnetic Simulations

  We introduce TokaGLINT, a GPU-accelerated implicit solver for electromagnetic field computations in full 3D tokamak simulations, aimed at efficient large-scale parallel GPU computing.

  Zifan Yang, Haoyuan Zhang, Jialin Li y 5 más — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations

  While the classical translation $FO3\Rightarrow CoR$ is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question.

  Yuya Uezato — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Adaptive Parallel-in-Time Integration with Dynamic Resource Management

  In this work, we present our novel approach to extending PFASST with DRM, which enables (a) dynamic adaptation of computing resources, (b) adaptive selection of the number of PFASST iterations based on local convergence behavior, and (c) coupling of these two adaptations into a single resizing strategy.

  Keerthi Gaddameedi, Dominik Huber, Martin Schreiber y 4 más — arXiv

  PreprintAfirmaciones fuertes, leer con cuidadoUso en el mundo real

  Guardar
• Computación/Algoritmos y complejidad24 de sept de 2026

  Substantive Agency and Computational Non-Anticipability: An Axiomatic Route to a Conditional Separation of P and N P

  This paper characterises substantive agency and identifies the additional bridges under which it has a standard complexity-theoretic consequence: conditionally, P __ = N P .

  J\'erome Clech — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases

  Here, we obtain two results.

  Chandra Chekuri, Lars Rohwedder, Neta Singer y 2 más — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Budget-Independent Influence Maximization in Nearly Linear Time

  We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least $1-\delta$ in $O((m+n){\epsilon }^{-3}\log (2n/\delta ))$ expected time.

  Zhijie Zhang — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  Lossless Hardness Condensation in Deterministic Communication Complexity

  We prove that every finite total Boolean matrix of deterministic communication complexity $c\ge 4$ has a submatrix on $2^k$ of its original rows and $2^k$ of its original columns, with $k={\Theta }_{\epsilon }(c)$ and complexity at least $(1-\epsilon )(k+1)$, for every fixed $0<\epsilon <1$.

  Simon Mackenzie — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad21 de sept de 2026

  Fair Prophets

  We initiate the study of $\alpha$-fair prophet inequalities.

  Paul Duetting, Michal Feldman, Mathieu Molina — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity

  We prove a quantum strong selective direct-product theorem for all functions using a new multiplicative adversary formulation for relations that satisfies a strong selective direct product property while being strong enough to capture any query lower bound for functions proven by negative-weights adversaries.

  Paul Beame, Niels Kornerup, Michael Whitmeyer — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games

  In this work, we prove that plain Optimistic Hedge with a constant step size can attain $O_{n,d}(1)$ individual regret in general-sum games with $n$ players and $d=(d_1,\dots ,d_n)$ actions, under expected loss-vector feedback.

  Junsoo Ha — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad25 de sept de 2026

  Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching

  We present Move-rb, a bi-directional r-index built on the optimized r-index Move-r.

  Johannes Fischer, Lukas Nalbach — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad22 de sept de 2026

  Complete Reductions and Idempotent Representations for $R\Pi {\Sigma }^{\ast }$-towers

  Finally, we compute an explicit idempotent representation that extends existing telescoping algorithms and our complete reduction framework to the general class of $R\Pi {\Sigma }^{\ast }$-extensions, opening up previously untreatable classes of sums and products.

  Yiman Gao, Jakob Obrovsky, Carsten Schneider — arXiv

  Preprint

  Guardar
• Computación/Algoritmos y complejidad23 de sept de 2026

  Prophet Inequalities Beyond Utilitarian Social Welfare

  We prove that for every $n$, the online optimum is at least $\Gamma \approx 0.7059$ times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every $p\le 1$.

  Daniel Halpern, Abhiram Manohara, Alexandros Psomas — arXiv

  Preprint

  Guardar