Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
43 articles · 3 sources · 43 papers ·
Top topics: Algorithms
arXiv:2604.25321v2 Announce Type: replace Abstract: Discrete probabilistic programs (DPPs) provide a highly expressive formalism for compactly defining arbitrary finite probabilistic models. This expressivity comes at a…
arXiv:2609.30804v1 Announce Type: cross Abstract: We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to…
arXiv:2609.21279v2 Announce Type: replace Abstract: Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_i A_i=I$ and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned…
arXiv:2609.25816v2 Announce Type: replace-cross Abstract: A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We consider the property testing task of…
arXiv:2609.30900v1 Announce Type: new Abstract: \textsc{Odd Cycle Transversal} is a classic $\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph…
arXiv:2609.30590v1 Announce Type: cross Abstract: We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at…
arXiv:2609.31099v1 Announce Type: cross Abstract: We study collision-free movement problems on graphs, where the task is to coordinate a set of robots so that they reach a target formation satisfying a desired property…
arXiv:2608.24527v2 Announce Type: replace-cross Abstract: We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus…
arXiv:2609.30421v1 Announce Type: new Abstract: This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through…
arXiv:2507.13159v2 Announce Type: replace Abstract: Linear programming rounding is a fundamental technique in the design of approximation and online algorithms. A growing body of work has investigated online rounding…
arXiv:2609.31256v1 Announce Type: new Abstract: Inspired by the planted clique problem for random graphs, we introduce the planted totally-isotropic space problem for random tensors as follows. Let $U\cong…
arXiv:2603.25914v2 Announce Type: replace-cross Abstract: We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $\Omega((\log n/\log\log n)^2)$ for…
arXiv:2410.09425v3 Announce Type: replace Abstract: In this paper, we consider the recoverable robust shortest path problem in acyclic digraphs, employing interval budgeted uncertainty to model uncertain second-stage…
arXiv:2609.30829v1 Announce Type: cross Abstract: Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell…
arXiv:2609.31090v1 Announce Type: cross Abstract: We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a…
arXiv:2609.30354v1 Announce Type: new Abstract: We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least…
arXiv:2509.09813v2 Announce Type: replace-cross Abstract: We study the problem of learning Hamiltonians $H$ that are $s$-sparse in the Pauli basis, given access to their time evolution. Although Hamiltonian learning has…
arXiv:2602.19680v2 Announce Type: replace Abstract: We study Facility Location with Matching, a Facility Location problem where, given additional information about which pair of clients is compatible to be matched, we…
arXiv:2609.31614v1 Announce Type: new Abstract: We give a gap-free differentially private algorithm for the principal component analysis (PCA) problem with Gaussian data.
arXiv:2609.31290v1 Announce Type: new Abstract: Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every…
Showing 1 day · 43 items available
