New papers on Algorithms & complexity
181 new papers on algorithms & complexity in the last 7 days, within Computing. These are the 50 Pipette rates most worth reading, with the main result in the authors' own words.
The best of the week
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 , where is the number of nodes, is the number of edges, and controls the scale of random perturbations.
PreprintClaims a big stepHardness of Online Directed Steiner Network
In this work, we show the first such unconditional, information-theoretic hardness.
PreprintClaims a big stepSingle-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.
PreprintWatermarkable 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.
PreprintBold claims, read criticallyClaims a big stepA New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond
Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical bound for sparse practical Shellsort sequences.
PreprintBold claims, read criticallyClaims a big stepKadison--Singer partitions and Bilu--Linial graph signings in polynomial time
We prove two main algorithmic results in spectral discrepancy.
PreprintClaims a big stepA General Composition Theorem for Approximate Degree
We resolve this question for all total Boolean functions by proving the matching lower bound.
PreprintClaims a big stepFast Geometric Spanners via Approximate Nearest Neighbor Search
In particular, we show the following results for any metric space with aspect ratio admitting a -approximate batch nearest neighbor search algorithm with runtime , (1) There exists an algorithm that, for any , constructs an -distortion spanner with edges and runs in time .
PreprintClaims a big step4-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.
PreprintClaims a big stepParameter-Free Triangle Counting
We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of or any quantities depending on , provided , the length of the stream.
PreprintStrategic 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.
PreprintA Polynomial Kernel for Planar Directed Feedback Vertex Set
We resolve the planar case by giving a deterministic kernel with vertices and arcs.
PreprintClaims a big stepA Fixed-Parameter Algorithm for 4-Block Integer Programming
We give a fixed parameter tractable (FPT) algorithm with running time for integer linear programs with 4-block structure, parameterized by the maximum block dimension and the largest absolute matrix entry .
PreprintClaims a big stepPractical 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.
PreprintCode availableFinding 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.
PreprintClaims a big stepApproximation Algorithm for the Min-Cost Bipartite Matching with Penalties
We present a randomized algorithm that computes a -approximate minimum-cost bipartite matching with penalties in time with high probability.
PreprintClaims a big stepSharp Lovasz-Theta Bounds on Random Graphs
In this work, we resolve this question by proving that the \Lovasz-Theta function of is with high probability, determining its asymptotic value up to vanishing relative error.
PreprintClaims a big stepAn exponential lower bound for the bit pigeonhole principle in resolution over parities
We prove that every DAG-like refutation of the bit pigeonhole principle with pigeons and holes has more than clauses, for every , with no restriction on regularity or depth.
PreprintClaims a big stepA 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.
PreprintReal-world useVector Balancing in Polynomial Time
We present a spectral signing algorithm solving the Koml\'os problem with a constant discrepancy in polynomial time.
PreprintAn Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance
We present the first polynomial-time approximation algorithm for this problem.
PreprintClaims a big stepStrategic 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.
PreprintAnalysis 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.
PreprintReal-world useDynamic 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).
PreprintOnline Algorithms with a Sample: Tight Bounds and Adversarial Robustness
We show a tight -competitive algorithm for set cover, exponentially improving upon the guarantee of Gupta et al. (SODA'24) and answering an open question therein.
PreprintEventual Nonnegativity of a Matrix Is in P
We prove that this problem is decidable in deterministic polynomial time.
PreprintCode availableFactorisability 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.
PreprintDense 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.
PreprintReal-world useCode availableEdge-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.
PreprintReal-world useCode availableFPT Isomorphism Test for -Free Tournaments
We show that isomorphism of -free tournaments can be solved in FPT time , where denotes the size of , and denotes the size of the input tournaments.
PreprintBeyond 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.
PreprintColour 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 total cost without any approximations.
PreprintBold claims, read criticallyLocally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals
For every , there is a menu size depending only on that preserves at least a fraction of the expected maximum-matching size of the full realized graph.
PreprintOptimal Analysis of Greedy for Stochastic Online Euclidean Matching
We prove that Greedy has competitive ratio for every fixed , and for .
PreprintPacing Equilibria in Abstract Mechanisms
We develop a unified theory of pacing equilibria across a hierarchy of mechanisms.
PreprintJEV-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.
PreprintBold claims, read criticallyCode availableA 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 , independently of their dimension and number which is a significantly stronger result than what was known existentially.
PreprintTokaGLINT: 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.
PreprintAn Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations
While the classical translation is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question.
PreprintAdaptive 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.
PreprintBold claims, read criticallyReal-world useSubstantive 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 .
PreprintSubmodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases
Here, we obtain two results.
PreprintBudget-Independent Influence Maximization in Nearly Linear Time
We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least in expected time.
PreprintLossless Hardness Condensation in Deterministic Communication Complexity
We prove that every finite total Boolean matrix of deterministic communication complexity has a submatrix on of its original rows and of its original columns, with and complexity at least , for every fixed .
PreprintFair Prophets
We initiate the study of -fair prophet inequalities.
PreprintStrong 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.
PreprintA 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 individual regret in general-sum games with players and actions, under expected loss-vector feedback.
PreprintMove-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.
PreprintComplete Reductions and Idempotent Representations for -towers
Finally, we compute an explicit idempotent representation that extends existing telescoping algorithms and our complete reduction framework to the general class of -extensions, opening up previously untreatable classes of sums and products.
PreprintProphet Inequalities Beyond Utilitarian Social Welfare
We prove that for every , the online optimum is at least times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every .
Preprint