Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
61 articles · 3 sources · 61 papers ·
Top topics: Algorithms
arXiv:2608.30351v1 Announce Type: new Abstract: We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) =…
arXiv:2608.12550v2 Announce Type: replace Abstract: Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition…
arXiv:2608.29764v1 Announce Type: new Abstract: Elementary Object Systems (EOSs) are a model in the nets-within-nets (NWNs) paradigm, where tokens in turn can host standard Petri nets. We study the complexity of…
arXiv:2608.28658v1 Announce Type: cross Abstract: Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs…
arXiv:2608.30036v1 Announce Type: new Abstract: Given a finite set $A$ of natural numbers whose greatest common divisor is one, the Frobenius number $g(A)$ is the largest integer that is not a non-negative integer…
arXiv:1601.04794v3 Announce Type: replace Abstract: A new framework is developed for studying phase transitions in CSPs. Motivated by phase transition problems in CSPs, we prove a more general concentration inequality…
arXiv:2608.29592v1 Announce Type: cross Abstract: We resolve three open problems concerning parsing expression grammars (PEGs). We construct a single language $C$ satisfying $C\in\mathsf{LIN}\cap\mathsf{PEG}$ and…
arXiv:2607.12078v4 Announce Type: replace-cross Abstract: We characterize the digraphs that admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable…
arXiv:2608.29840v1 Announce Type: cross Abstract: We develop a computational framework for Bayesian decision-making. We show that as long as no action is optimal in every state, Bayes-optimal choice is intractable. This…
arXiv:2608.28813v1 Announce Type: new Abstract: We show that a certified formalization of the hitting-set-existence axiom of Atserias and Tzameret, instantiated on the parity-based Nisan-Wigderson compression class of…
arXiv:2608.29416v1 Announce Type: cross Abstract: We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$…
arXiv:2608.31120v1 Announce Type: cross Abstract: The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions…
arXiv:2608.30340v1 Announce Type: cross Abstract: Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative…
arXiv:2608.27416v2 Announce Type: replace-cross Abstract: The Non-Cancelling Intersections (NCI) conjecture of Amarilli, Monet and Suciu [arXiv:2401.16210] states that the union of a finite family of sets can always be…
arXiv:2608.28659v1 Announce Type: cross Abstract: Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their…
arXiv:2508.00349v2 Announce Type: replace-cross Abstract: Popular matchings provide a model of matching under preferences in which a solution corresponds to a Condorcet winner in voting systems. In a bipartite graph in…
arXiv:2608.29573v1 Announce Type: cross Abstract: Function correcting codes (FCCs) are designed to protect a specified function evaluation of messages at a higher level than the level of protection for messages, against…
arXiv:2608.30353v1 Announce Type: cross Abstract: Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an…
arXiv:2608.06215v3 Announce Type: replace-cross Abstract: In this paper, we build upon the analysis initiated by Gennadiy Averkov and Matthias Schymura (2022) and establish that the number of distinct columns of a…
arXiv:2510.18260v2 Announce Type: replace Abstract: This paper proposes Warshall algorithm-a greedy algorithm for determining connectedness and clustering in matrix-weighted graphs. Built upon a sufficient condition for…
Showing 1 day · 61 items available
