Daily edition · Algorithms
TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.
44 articles · 3 sources · 44 papers ·
Top topics: Algorithms · AI
arXiv:2609.20939v1 Announce Type: new Abstract: In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the…
arXiv:2609.21696v1 Announce Type: new Abstract: Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow…
arXiv:2609.17650v2 Announce Type: replace Abstract: The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has…
arXiv:2609.21612v1 Announce Type: new Abstract: Kannan's algorithm, as analyzed by Hanrot and Stehl\'e in 2007, solves the exact Euclidean shortest vector problem in polynomial space and $n^{\frac{n}{2e}+o(n)}$ time. In…
arXiv:2609.21145v1 Announce Type: cross Abstract: The Viterbi algorithm has been previously used to perform forced alignment of audio to text to mine training data from online resources. However, many existing…
arXiv:2607.15494v2 Announce Type: replace Abstract: Fuzzy minimax nets were recently introduced as a tool for computing the greatest fuzzy bisimulation and simulation between two finite fuzzy graph-based structures. In…
arXiv:2609.21993v1 Announce Type: new Abstract: We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are…
arXiv:2607.00876v3 Announce Type: replace Abstract: Private continual counting is a fundamental problem in differential privacy: given a binary stream of length $n$, where each $1$ corresponds to the contribution of one…
arXiv:2609.20866v1 Announce Type: cross Abstract: For a ferromagnetic Ising model on a graph of maximum degree $\Delta\ge3$, we prove a bound of order $\sqrt n$ on every row of the influence matrix at the tree…
arXiv:2609.21279v1 Announce Type: new Abstract: Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_iA_i=I$ and $\|A_i\|\le\varepsilon$. We prove that the original matrices admit signs…
arXiv:2609.22054v1 Announce Type: cross Abstract: We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$. In particular, every…
arXiv:2609.21236v1 Announce Type: new Abstract: A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an…
arXiv:2609.21245v1 Announce Type: new Abstract: We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the…
arXiv:2609.21348v1 Announce Type: new Abstract: We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at…
arXiv:2609.21889v1 Announce Type: new Abstract: Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance?…
arXiv:2609.20539v2 Announce Type: replace-cross Abstract: A popular selling point of diffusion large language models (dLLMs) is their capacity for parallelism: the ability to generate sequences of text far more…
arXiv:2609.11982v2 Announce Type: replace Abstract: We give a deterministic algorithm that computes the parity of the number of Hamiltonian cycles in an $n$-vertex directed graph in $O(n^4(3/2)^n)$ time and $O(n^2)$…
arXiv:2609.21826v1 Announce Type: cross Abstract: We initiate the study of $\alpha$-fair prophet inequalities. This interpolates between utilitarian welfare $(\alpha=0)$, Nash welfare $(\alpha=1)$, and Rawlsian max-min…
arXiv:2609.19746v2 Announce Type: replace Abstract: A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number…
arXiv:2609.20895v1 Announce Type: new Abstract: Compact summaries are a key tool for approximate query processing over large datasets. For range-query workloads, an $\varepsilon$-net provides a small summary that hits…
Showing 1 day · 44 items available
