Fooling Thresholds of Halfspaces
arXiv:2609.21329v1 Announce Type: new Abstract: We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This…
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.21329v1 Announce Type: new Abstract: We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This…
arXiv:2608.23828v2 Announce Type: replace Abstract: We prove that exact Euclidean decision-CVP is $\mathsf{NP}$-complete on the coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings…
arXiv:2604.18283v2 Announce Type: replace-cross Abstract: Upper and lower quantum functionals, introduced by Christandl, Vrana and Zuiddam (STOC 2018, J. Amer. Math. Soc. 2023), are families of monotone functions of…
arXiv:2609.21842v1 Announce Type: new Abstract: Tree Decision Diagrams (TDDs) are a data structure recently introduced by Capelli et al. (SAT 2026). They are structured along a vtree and the size of their canonical form…
arXiv:2609.20979v1 Announce Type: cross Abstract: We give an elementary proof of the Koml\'os conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors $v_1,\ldots,v_n\in\mathbb{R}^d$…
arXiv:2609.21567v1 Announce Type: cross Abstract: Quantum Signal Processing is a powerful quantum framework for generating and approximating univariate polynomials. However, QSP is often limited by circuit-depth…
arXiv:2609.21840v1 Announce Type: new Abstract: Assuming the Exponential Time Hypothesis (ETH), fixed-parameter tractability and polynomial-time solvability coincide for homomorphism problems specified by classes of…
arXiv:2609.18807v2 Announce Type: replace-cross Abstract: Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex…
arXiv:2601.09219v3 Announce Type: replace Abstract: The \emph{Tree Augmentation Problem (TAP)} is given a tree $T=(V,E_T)$ and additional set of {\em links} $E$ on $V\times V$, find $F \subseteq E$ such that $T \cup F$…
arXiv:2609.21785v1 Announce Type: cross Abstract: The satisfiability problem for word equations asks whether variables can be replaced by words so that the two sides become equal. For regular word equations, in which…
arXiv:2609.21895v1 Announce Type: cross Abstract: In the 1960s, Erd\H{o}s and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle)…
arXiv:2608.24078v2 Announce Type: replace Abstract: We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and…
arXiv:2609.21116v1 Announce Type: cross Abstract: Let $\mathcal{A}_0$ be the set of finitely generated free groups on some countable alphabet and and define $\mathcal{A}_r$ inductively as the union of…
arXiv:2605.03965v2 Announce Type: replace-cross Abstract: The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag.…
arXiv:2609.21477v1 Announce Type: cross Abstract: The weighted $k$-matroid intersection problem asks for a maximum-weight set that is independent in each of $k$ matroids on a common ground set. The natural LP relaxation…
arXiv:2609.21700v1 Announce Type: cross Abstract: Best match graphs (BMGs) were introduced in mathematical phylogenetics to describe the concept of closest relatives for related genes (leaves of rooted tree) in…
arXiv:2609.15591v2 Announce Type: replace-cross Abstract: We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside…
arXiv:2609.21603v1 Announce Type: cross Abstract: Let $\mathcal A$ be a complete deterministic finite automaton on a state set $Q$ of size $n$ with $k$ letters, and for a proper nonempty subset $S$ of $Q$ let…
arXiv:2609.05780v2 Announce Type: replace-cross Abstract: Is it possible to walk to infinity, avoiding three collinear points, using as steps only the standard unit basis vectors $(0,0,\ldots, 0, 1, 0, \ldots, 0)$? We…
arXiv:2609.21615v1 Announce Type: cross Abstract: The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain…
Showing 1 day · 44 items available