Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
38 articles · 3 sources · 38 papers ·
Top topics: Algorithms · AI · Information Retrieval
arXiv:2609.11830v1 Announce Type: cross Abstract: The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the…
arXiv:2608.12664v2 Announce Type: replace Abstract: We prove that, for every constant $\rho>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $\rho$ under a deterministic…
arXiv:2609.11854v1 Announce Type: cross Abstract: Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class…
arXiv:2609.10838v1 Announce Type: cross Abstract: In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap…
arXiv:2609.11175v1 Announce Type: new Abstract: The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems…
arXiv:2609.11013v1 Announce Type: cross Abstract: We study the problem of treasure hunt by a group of $k \geq 1$ agents in vertex-permuted dynamic rings (VP). In this model, the $n$ vertices remain on a ring but are…
arXiv:2609.11822v1 Announce Type: new Abstract: We show that ACC$^0$ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by…
arXiv:2603.03717v3 Announce Type: replace-cross Abstract: Locally decodable codes (LDCs) are error-correcting codes that allow recovery of any single message symbol by probing only a small number of positions from the…
arXiv:2609.11693v1 Announce Type: new Abstract: We consider the two-machine open-shop scheduling problem in which one machine is unavailable during a fixed interval. We study the resumable setting: an operation…
arXiv:2503.02566v2 Announce Type: replace Abstract: Hub Covering Problems are a subclass of Hub Location Problems. The objective is to select a set of hubs that enable paths between given origin-destination delivery…
arXiv:2601.18602v2 Announce Type: replace-cross Abstract: Lov\'asz (1967) showed that two graphs $G$ and $H$ are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., $G$ and $H$…
arXiv:2209.06404v3 Announce Type: replace-cross Abstract: We determine the exact extension threshold for one-factorizations of complete tripartite $3$-uniform hypergraphs. Equivalently, for $n>m$, every order-$m$…
arXiv:2607.23111v3 Announce Type: replace Abstract: A numerical semigroup is a subset of the nonnegative integers, closed under addition and with finite complement. The size of the complement is its genus. The problem…
arXiv:2603.23070v2 Announce Type: replace-cross Abstract: The House of Graphs is an online database of graphs which can be accessed at https://houseofgraphs.org/. It serves as a central repository for complete lists of…
arXiv:2609.08847v2 Announce Type: replace-cross Abstract: Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gy\'arf\'as (1987) proved…
arXiv:2507.18779v2 Announce Type: replace-cross Abstract: A power-free language is characterized by the number of symbols used and a limit on how many times a block of symbols can repeat consecutively. For certain…
arXiv:2603.08895v2 Announce Type: replace-cross Abstract: We study degree-based weighted adjacency matrices associated with symmetric edge-weight functions $\phi(d_u,d_v)$, with emphasis on complete multipartite graphs…
arXiv:2609.11285v1 Announce Type: cross Abstract: We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This…
arXiv:2609.10808v1 Announce Type: cross Abstract: How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using…
arXiv:2607.06451v3 Announce Type: replace-cross Abstract: Single-server private information retrieval (PIR) schemes are known to require linear query time. Recent works circumvent these classical lower bounds by…
Showing 1 day · 38 items available
