84 papers
This paper introduces the Block Sparse Tensor Train (BSTT) sketch, a structured random projection that unifies existing TT-adapted sketching operators and achieves linear scaling in tensor order and subspace dimension, thereby enabling quasi-optimal error bounds for tensor factorization and rounding tasks.
This paper establishes a rate-distortion theorem demonstrating that hallucinations in large language models are an inevitable consequence of information-theoretically optimal memory compression when distinguishing sparse facts from non-facts, rather than a failure of training or data quality.
This paper presents a polynomial-size representation and a corresponding polynomial-time construction algorithm for the family of all sets with a fixed value in integer-valued symmetric submodular functions, thereby generalizing low-rank structure theorems from graph cut-rank functions to broader connectivity functions and enabling efficient solutions to cardinality-constrained minimization problems.
This paper introduces IsalGraph, a novel method that encodes any finite simple graph into a compact, valid nine-character instruction string using a virtual machine, enabling efficient canonical representation and demonstrating strong correlation between string edit distance and graph edit distance for applications in similarity search and language modeling.
This paper introduces -Motif, a GPU-accelerated subgraph isomorphism algorithm that reformulates graph matching as scalable database operations on motifs, achieving speedups of up to 595 over traditional methods like VF2 while enabling efficient quantum circuit compilation through familiar relational abstractions.
This paper presents a fixed-parameter tractable algorithm that resolves the open question of whether a graph can be covered by fewer than vertex-disjoint paths by outputting either a minimum path cover or an independent set certifying the cover's near-optimality, while also providing the first polynomial-time Hamiltonian path decision for graphs with independence number at most three.
This paper addresses the online busy time scheduling problem on heterogeneous machines by presenting an 8-competitive algorithm for unit-length jobs, establishing a lower bound of 2 on the competitive ratio, and extending the solution to a ratio of less than 16 for jobs of uniform length .
This paper establishes nearly optimal sample complexity bounds for testing the -clique property and -colorability in the dense graph model by applying new extensions of the graph container method.
This paper presents a new algorithm that improves the time complexity for recognizing and enumerating minimal hitting sets in hypergraphs by trading dependency on the number of edges for dependency on the number of vertices, while also establishing that further polynomial improvements in this parameter are equivalent to solving several major open problems in combinatorial algorithms.
This paper resolves an open problem regarding online packet forwarding in line networks by demonstrating that a greedy algorithm achieves a competitive ratio of $2-2^{1-k}4/3$ even for randomized algorithms.
This paper introduces the first comparison-based sorting algorithms that are strictly in-place, using only O(1) extra memory, while achieving optimal O(n(1 + H(A))) running time based on the input's run-based entropy, specifically tailored for memory-constrained embedded systems like refrigerators.
This paper presents and experimentally evaluates space-efficient B-tree variants optimized for memory-constrained flash-based embedded devices, demonstrating that storage-specific adaptations enable efficient on-device indexing and processing for IoT applications.
This paper improves the known bounds for agnostic learning of concept classes with bounded Gaussian surface area by demonstrating that a polynomial degree of suffices for -approximation, thereby yielding near-optimal complexity for learning polynomial threshold functions in the statistical query model.
This paper proposes a novel cascaded accumulator method that efficiently computes time-index powered weighted sums in real-time by reducing multiplicative complexity from to constant multiplications while eliminating the need for storing entire data blocks.
This paper introduces a new one-pass algorithm for weighted reservoir sampling with replacement from data streams of unknown size, which provides a representative sample at any time without post-processing and is proven to be both correct and efficient compared to state-of-the-art methods.
This paper investigates the complexity of the Distance- Dominating Set Reconfiguration problem for under Token Jumping and Token Sliding rules, establishing a PSPACE-complete to P complexity dichotomy on split graphs, providing a linear-time algorithm for trees, and extending hardness results to planar graphs with maximum degree three and various other graph classes.
This paper generalizes the disk scaling model for graph modification by allowing rescaled disks to choose radii within a specific interval, establishing that the problem is in XP for any polynomially recognizable graph class while providing a detailed complexity landscape that includes NP-hardness and FPT results for cluster graphs, polynomial-time solvability for complete graphs, and W[1]-hardness for connected graphs.
This paper addresses the computational challenges of generalizing fair top- selection to multiple protected groups while minimizing disparity from a reference function, revealing new hardness barriers for small and proposing an efficient, robust two-pronged solution that incorporates utility loss as an alternative disparity measure.
This paper introduces optimal prediction-augmented algorithms for testing the independence of distributions that maintain worst-case validity while significantly improving sample efficiency in high-dimensional settings when provided with accurate, albeit untrustworthy, auxiliary predictions.
This paper presents the first approximation algorithms for two generalizations of the Maximum Quadratic Assignment Problem—Maximum List-Restricted Quadratic Assignment and Maximum Quadratic -Matching Assignment—achieving and approximation factors respectively, which asymptotically match the best known bounds for the standard MaxQAP under specific conditions.