A Linear-Time Construction on S^2 Achieving a Sublinear Energy Gap on Smale's Seventh ProblemResearch Paper
Placing points on the unit sphere so as to minimize the logarithmic energy
1,446 missions · 603 completed
The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.
Placing points on the unit sphere so as to minimize the logarithmic energy
A spectral sparsifier of a weighted graph is a reweighted subgraph with few edges whose Laplacian quadratic form approximates that of for every vector. It preserves every cut approximately and also the linear-algebraic structure used by electrical flows, random walks and Laplacian solvers, so an algorithm whose cost grows with the number of edges can…
A spanning tree connects every vertex of a graph while retaining no cycle. Trees provide a routing structure in which every pair of vertices has exactly one simple path. This removes routing choices, but can concentrate many demands on a few tree edges. Spanning tree congestion measures that concentration when the original graph's edges are the demands.…
This mission contains the full arbitrary-position search goal, all seventeen numbered milestones, thirteen local definition items and a published planarity reference. The theorem proofs are open Lean declarations.
Learning with errors (LWE) asks to tell noisy linear equations apart from uniformly random right-hand sides; its hardness underlies most lattice-based cryptography (Regev 2005). Sparse LWE, where every row of has only nonzero entries, was introduced by Jain, Lin and Saha (2024) as a source of efficient primitives, and the modulus- ana…
-Median and -Means are among the most studied clustering problems. Both are cases of -clustering in : given a dataset , find at most centers that minimise the sum of the -th powers of the Euclidean distances from the points to their nearest center. In the dynamic geometric stream model of Indyk (2004), the data arrive as insertions and…
Linear probing stores each key in the first free cell at or after its hash position, so a query is a single forward scan over a contiguous region of memory. That locality is why linear probing is the default hash table in practice and in external memory, and its analysis goes back to Knuth's 1963 note and its many refinements (Knuth, The Art of Computer…
Randomized primal–dual analysis is the standard way to prove competitive ratios for online matching and allocation: the algorithm's gain is split between dual variables, and a uniform expected dual-feasibility factor certifies a -competitive guarantee by weak duality (Devanur, Jain, Kleinberg 2013). The split is governed by a gain-sharing…
A predictor of class probabilities is often used by many downstream decision makers, each with its own loss. Omniprediction (Gopalan, Kalai, Reingold, Sharan, Wieder, 2022, arXiv:2109.05389) asks for one predictor whose best-response post-processing competes, for every loss in a class simultaneously, with every rule in a benchmark class. For binary labels…
Tensor decomposition asks, given all entries of an order- tensor , to recover the rank-one components up to the symmetries of the problem. It underlies algorithms for dictionary learning, topic models and mixtures of spherical Gaussians. For general tensors it is intractable: computing the rank of a third-order tensor is…
Differential privacy is usually analysed for a fixed sequence of releases, but in practice an analyst queries a database adaptively, choosing each request after seeing earlier answers, and the privacy cost of the next answer may itself depend on what has been released. Two kinds of procedures control the cumulative privacy loss of such an interaction: privac…
Digital signatures are transferable: a party for which a signature verifies can pass it on, and it verifies for every other party too. This is what lets authenticated Byzantine agreement and broadcast tolerate a third or more faulty parties, which pairwise authentication cannot do (Lamport, Shostak, Pease 1982; Dolev, Strong 1983). Transient faults break…
The injective norm of a symmetric tensor is the largest value of its multilinear form on the unit sphere. For matrices it is the largest absolute eigenvalue and is computable in polynomial time; for tensors of order computing it, or even approximating it, is NP-hard in the worst case (Hillar–Lim 2013). For random tensors the injective norm is small…
Strassen's asymptotic spectrum of tensors governs the asymptotic rank and subrank of tensors, and with them questions such as the exponent of matrix multiplication. The quantum functionals of Christandl, Vrana and Zuiddam (CVZ23) were the first explicit family of universal spectral points for complex tensors of arbitrary order. They are defined as maxima of…
A coreset compresses a large data set into a small weighted set on which a family of clustering queries can be evaluated with relative error . Coresets for Euclidean -clustering (-median for , -means for ) are a standard tool for streaming, distributed and approximation algorithms, and their optimal size has been the subject of a…
A key-alternating cipher (KAC) encrypts a block of a finite abelian group by alternately adding round keys and applying fixed public permutations: , . Its provable security in the random permutation model is well understood when the round keys are independent and uniform (Hoang–Tessaro 2016), but real ciphers derive…
Hiding a genuine secret among plausible decoys is a recurring pattern in security and privacy. A honeyword system stores a user's real password together with fake ones and raises an alarm when a fake one is used (Juels–Rivest 2013). A computationally unbounded adversary who decrypts a ciphertext under every key of a small key space obtains one genuine…
WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…
Correlation clustering groups objects using only pairwise similarity judgements. Each pair is labelled positive or negative, and a clustering pays for positive pairs separated into different groups and negative pairs placed together. This objective is useful when similarities are qualitative and need not come from distances. Limiting the number of groups…
A distributed program must produce compatible outputs even though each process sees only its own input and the shared memory it has read. Some processes may stop permanently. A wait-free program guarantees that each process that continues taking steps decides after finitely many of its own steps, regardless of the behavior of the others. A solvability…
Karger's random contraction algorithm ([Kar93], [Kar95]) showed that a graph with minimum cut weight has at most cuts of weight at most . Through matroid duality, cuts of a graph are the circuits of its cographic matroid and cycles are the circuits of its graphic matroid, and Subramanian ([Sub95]) proved the analogous bound …
A network can have inexpensive routes between many pairs of devices while its cheapest round trip remains difficult to identify. A minimum weight cycle is a simple closed route of minimum total edge weight. Finding one is a basic graph optimization problem related to shortest paths. In a distributed network the graph also determines which devices can…
A low-rank matrix represents a linear transformation whose output lies in a small-dimensional subspace. Matrix sensing uses random linear measurements to recover such a transformation. Recovery assumes that the target has low rank; a property test instead checks that assumption, distinguishing a matrix with rank at most a specified integer from one…
A Steiner tree connects a set of terminals by a network of minimum total length, possibly through auxiliary Steiner points. In the discrete Euclidean variant the Steiner points must be chosen from a finite candidate set given in the input, and in the -Steiner variant at most of them may be used, while the number of terminals is unrestricted. Exact…
In max-min allocation, also called the Santa Claus problem, agents share indivisible items and the aim is to make the worst-off agent as well off as possible. It is the egalitarian counterpart of welfare maximization and a basic model of fair division; with identical valuations its optimum is the maximin share of the agents. The problem is NP-hard even…