Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
35 articles · 3 sources · 35 papers ·
Top topics: Algorithms · AI
arXiv:2608.08578v2 Announce Type: replace Abstract: We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform $\mathrm{AC}^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time…
arXiv:2311.10040v3 Announce Type: replace-cross Abstract: A central task in knowledge compilation is to compile a CNF-SAT instance into a succinct representation format that allows efficient operations such as testing…
arXiv:2609.05005v1 Announce Type: cross Abstract: Algebraic combinatorics often seeks bijections that explain identities between distributions object by object. Encoding combinatorial objects as words lets automata…
arXiv:2609.04931v1 Announce Type: cross Abstract: The widespread adoption of artificial intelligence (AI) within real-world applications has raised a lot of concerns regarding their trustworthiness, especially in…
arXiv:2411.05721v2 Announce Type: replace-cross Abstract: One of the fundamental open problems in the field of tensors is the border Comon's conjecture: given a symmetric tensor $F\in(\mathbb{C}^n)^{\otimes d}$ for…
arXiv:2609.05201v1 Announce Type: cross Abstract: We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove…
arXiv:2609.04950v1 Announce Type: new Abstract: For a finite abelian group $G$ and $k \geq 1$, the generalized Davenport constant $D_k(G)$ is the least $\ell$ such that every sequence over $G$ of length at least $\ell$…
arXiv:2604.02796v2 Announce Type: replace-cross Abstract: As part of the graph minor project, Robertson and Seymour showed in 1990 that the class of graphs embeddable in a given surface can be characterized by a finite…
arXiv:2608.13310v2 Announce Type: replace-cross Abstract: The $(\min,+)$ convolution is a central problem in fine-grained complexity, and it remains open whether it can be computed in truly subquadratic time. We study…
arXiv:2609.04257v1 Announce Type: cross Abstract: For a finite simple graph $G$ with at least one edge, the bondage number $b(G)$ is the least number of edges whose deletion increases the domination number $\gamma(G)$.…
arXiv:2609.00720v2 Announce Type: replace-cross Abstract: In Lazy Cops and Robbers, at most one cop moves on each cop turn. We study the lazy cop number of the generalized hypercube $Q(n,m)$, whose vertex set is…
arXiv:2608.01442v2 Announce Type: replace-cross Abstract: The X-ray of a permutation is a sequence of sums along each diagonal of the associated permutation matrix. They satisfy certain necessary constraints on…
arXiv:2609.05259v1 Announce Type: cross Abstract: A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when…
arXiv:2504.19783v3 Announce Type: replace-cross Abstract: Given a graph $G$ and a natural number $k$, the $k$-recolouring graph $\mathcal{C}_k(G)$ is the graph whose vertices are the $k$-colourings of $G$ and whose…
arXiv:2609.04956v1 Announce Type: cross Abstract: A colorful graph relation enhances the minor relation by merging color sets along contractions and by allowing the removal of colors; it generalizes rooted minors and…
arXiv:2601.04040v3 Announce Type: replace-cross Abstract: The spread of a vertex $v$ in a tree decomposition is the number of bags that contain $v$. We study the trade-off between spread and width in tree…
arXiv:2609.04521v1 Announce Type: new Abstract: Karger's elegant random contraction algorithm for finding a global mincut in a graph has been highly influential. More recent work has obtained several different…
arXiv:2509.25150v3 Announce Type: replace-cross Abstract: We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching…
arXiv:2608.08260v2 Announce Type: replace Abstract: We give a randomised algorithm for Equal Subset Sum that, on $n$ arbitrary integers of at most $m\le2^n$ bits, runs in time $O\big((5/3)^n\mathrm{poly}(n)+n^2m\big)$,…
arXiv:2609.03574v2 Announce Type: replace Abstract: We study the basic problem of approximating the number of spanning trees of a graph. We propose an algorithm that approximates the number of spanning trees in…
Showing 1 day · 35 items available
