82 papers
This paper presents a novel automated method combining the substitution technique with systematic backtracking and dynamic programming to prove that the bilinear complexity of $3 \times 3\mathbb{F}_2$ is at least 20, thereby improving the previous lower bound of 19.
This paper establishes that for Bayesian inference of planted matchings between correlated 1D point sets under critical scaling, the posterior distribution admits a local approximation with a well-defined infinite-volume limit in the partial matching case, whereas the exact matching case requires global sorting and a flow-based indexing to define its asymptotic marginal statistics.
This paper presents a polynomial-time algorithm for approximately sampling uniformly random equitable colorings when the number of colors exceeds $2\Delta$, utilizing the geometry of polynomials framework to establish a multivariate local Central Limit Theorem for color class sizes.
This paper introduces the class of -cuttable undirected phylogenetic networks as a computationally useful alternative to tree-child-orientable networks, demonstrating that they are recognizable in polynomial time and render the NP-hard Tree Containment problem solvable in polynomial time for .
This paper presents a differentially private scheme for estimating black-box statistics that effectively trades off between statistical efficiency and oracle efficiency, accompanied by lower bounds demonstrating the near-optimality of this approach.
This paper introduces Exploration Space Theory (EST), a formal lattice-theoretic framework that adapts Knowledge Space Theory to location-based recommendation by modeling prerequisite dependencies among points of interest, thereby providing structural guarantees for validity, optimality, and explainability in the Exploration Space Recommender System (ESRS).
This paper introduces the first formal framework for cooperative multi-agent reinforcement learning with submodular rewards, proposing algorithms that achieve a 1/2-approximation guarantee and sublinear regret bounds while overcoming the exponential complexity of joint policy optimization.
This paper demonstrates that a provable quantum-classical separation persists in the sparse Sachdev-Ye-Kitaev (SYK) model for sparsification probabilities , as efficient quantum algorithms achieve constant-factor ground state approximations while classical Gaussian states are limited to only -factor approximations.
This paper introduces a novel, succinct QUBO formulation for permutation problems using sorting networks that reduces variable complexity to while enabling unbiased sampling and supporting complex operations like multiplication, inversion, and order checking.
This paper resolves an open question by demonstrating the first explicit separation between oblivious and adaptive differential privacy in the continual observation model, showing that while an oblivious algorithm can remain accurate for exponentially many time steps, any adaptive algorithm fails after only a constant number of steps.
This paper investigates minimal unsatisfiable subsets (MUSs) of 2-CNF formulas by presenting a linear-time recognition procedure, establishing polynomial-time algorithms for finding MUSs with one or two unit-clauses, and extending previous results on the NP-completeness of deficiency-1 MUSs.
This paper introduces the Huffman-Bucket Sketch (HBS), a mergeable data structure that losslessly compresses HyperLogLog sketches to near-optimal space using a global Huffman codebook, achieving amortized constant-time updates while requiring the codebook to be rebuilt only logarithmically often as cardinality increases.
This paper resolves an open problem by demonstrating that centralized reconfiguration of geometric amoebot structures using joint movements can be achieved in sublinear time, specifically rounds for transforming any structure into a canonical line segment and constant time for spiral-to-line conversions, without relying on auxiliary assumptions like metamodules.
This paper introduces massively parallel computation algorithms for graph orientation and coloring that operate in the strongly sublinear memory regime with rounds, breaking the previous barrier by achieving performance dependent on the graph's subgraph density .
This paper presents a deterministic algorithm that reconstructs bounded degree, bounded treelength graphs using shortest path distance queries, thereby improving upon previous bounds by a logarithmic factor and matching the known lower bound for bounded chordality graphs.
This paper mathematically proves that in three-dimensional space, the Cauchy walk (Lévy exponent ) uniquely achieves scale-invariant, near-optimal detection across diverse target sizes and shapes by transitioning from volume-dominated to surface-area-dominated search strategies, thereby establishing a rigorous foundation for the Lévy flight foraging hypothesis in 3D.
This paper introduces "Sample-and-Search," a learning-augmented algorithm for high-dimensional -median clustering that utilizes a predictor to preprocess data, thereby significantly reducing both computational complexity and exponential dimensionality dependency while achieving lower clustering costs compared to state-of-the-art methods.
This paper proves that the Transposition rule for the online list update problem achieves an expected access cost of at most OPT + 1 in the i.i.d. model, thereby confirming a 50-year-old conjecture by Rivest and demonstrating that this simple, memoryless strategy is nearly optimal for sorting items by unknown access probabilities.
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.