Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph HomomorphismsResearch Paper
A graph homomorphism partition function assigns to a symmetric weight matrix and a graph the number
136 missions · 10 completed
A graph homomorphism partition function assigns to a symmetric weight matrix and a graph the number
Matrix discrepancy asks how to assign plus and minus signs to a collection of matrices so their signed sum is small. A bound independent of the matrix dimension is useful when the matrices represent many simultaneous quadratic measurements: cancellation must hold in every direction, rather than for a single scalar sum. The Kadison–Singer problem, in its…
A short arithmetic computation can describe an integer too long to write out efficiently. Repeated squaring already produces this effect using only the literal 1, addition and multiplication. Determining the sign of the resulting integer is therefore a separate computational question from evaluating it in binary. This question matters in exact numerical…
Collision finding is a basic benchmark of quantum query complexity and of post-quantum security: the cost of finding inputs with equal outputs bounds the security of hash functions and of protocols built from them against quantum attackers. Two refinements matter in practice. One asks for many collisions at once (security reductions for multi-instance…
The group isomorphism problem asks whether two finite groups, given by their Cayley tables (multiplication tables), are isomorphic. It lies in NP, is not known to be in P or NP-complete, and is a recognised bottleneck for graph isomorphism: Babai's quasipolynomial-time algorithm for graphs does not carry over, and the classical bound for groups of order is…
A counting oracle for a distribution on answers a query with the marginal probability . Any-order autoregressive and masked diffusion models provide exactly this access. With it, can be sampled coordinate by coordinate, but that takes sequential rounds. The question of parallel sampling is how many adaptive rounds…
Let be a finite field with elements. Root-finding asks, given a polynomial that is split (a product of linear factors) and separable (coprime with its derivative), for the set of its roots in . Factoring arbitrary polynomials over reduces to this problem in deterministic polynomial time (Berleka…
Polynomial approximations of Boolean functions are a basic tool in complexity theory. A real polynomial pointwise approximates a Boolean function if on every input of the Boolean cube. Two measures of matter: its degree, which governs quantum query lower bounds and learning algorithms, and its coefficient ℓ1-norm , the sum of…
A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. Exact algorithms for deciding whether a graph admits a specified number of colors are studied in computational complexity because their running times measure how much of an exponential search can be avoided. The relevant parameter here is the number of vertices,…
Convex optimization asks for a feasible point whose objective value is close to the smallest feasible value. When the objective is available only through queries, the number of queries describes how much information an algorithm needs about an unknown function. Quantum algorithms can query superpositions of points, so a classical query lower bound does not…
Moving data costs energy, and in a circuit the cost grows with the distance a bit travels. Grover's bit-meter measure charges every transmitted bit by the length of the wire it crosses (Grover 2015); with it, Blake and Kschischang proved that decoding positive-rate codes over a binary erasure channel with exponentially small block error probability needs …
Training a classifier asks for parameters that fit observed examples. Even when the data can be classified perfectly, the task of finding suitable parameters can have substantial computational cost. The question here concerns exact training: deciding whether any parameter choice makes zero mistakes on the entire supplied data set. It concerns computation on…
A communication problem distributes an input among several participants and asks how many bits they must exchange to compute an answer. In the number-on-forehead model, each participant sees every input block except their own. With three participants, these views overlap substantially: a fact hidden from one participant is visible to the other two. Lower…
A Boolean function is -Fourier-sparse when at most of its Fourier coefficients are nonzero. Sparse functions include parities and -juntas (which have at most nonzero coefficients), so sparsity is one of the basic "concise representation" classes of learning theory and property testing. A tester for this class reads at a…
A tensor decomposition expresses a multidimensional array as a sum of outer products of vectors. Its factors describe separate contributions in each coordinate direction. In applications such as latent-variable estimation and spectral data analysis, a decomposition is useful when those contributions can be distinguished from other explanations of the same…
Submodular facility location asks how to assign clients to facilities when the cost of serving a group has diminishing marginal increments. All facilities share the same cost function. This homogeneous setting distinguishes the question from variants with a different function at each facility. It allows economies of scale while retaining the geometric…
Property testing asks for randomized algorithms that query a Boolean function at a few points and decide, with probability at least , whether has a property or is -far from it, meaning that at least an fraction of its values must change to land in . The classical resource is the number…
Agnostic learning of halfspaces asks for a linear classifier whose error is within of the best halfspace, with no assumption on how labels are generated. Statistically the problem is easy: samples suffice in dimension . Computationally it is not: the best known algorithms run in time or …
The exponent of matrix multiplication is the least such that matrices over a field can be multiplied with arithmetic operations; equivalently, it measures the growth of the tensor rank of the matrix multiplication tensor . In October 2026 OpenAI announced a proof that …
Extended Frege (EF) is the propositional proof system obtained from the textbook Frege system by adding the extension rule, which names a fresh variable as an abbreviation of a short formula (Cook–Reckhow 1979). Recent cryptographic constructions rely on EF proofs of correctness of concrete circuits, and the efficiency of those constructions is governed by…
Algebraic complexity theory asks how many additions and multiplications are needed to compute a polynomial. Next to exact computation it studies approximate computation: a polynomial is in the border of a class of circuits if circuits from the class, with constants depending on a parameter , compute , so that is their limit as …
Given a class of predictors (Boolean circuits of bounded size, models of a fixed architecture), why is a labeling hard to approximate by members of ? The hardcore lemma of complexity theory answers this for Boolean labels and the 0-1 loss: if every errs on a -fraction of inputs, then there is a measure of…
A basic structural question in algebraic complexity is whether factors of a polynomial with a small circuit also have small circuits. In the commutative setting small-circuit bounds for factors were established by Kaltofen ([10]), closure of commutative VNP in characteristic zero and sufficiently large characteristic was proved by Chou, Kumar and Solomon…
A lattice is the set of integer combinations of a finite collection of linearly independent vectors. Its geometry can be simple while its given coordinates conceal that simplicity. The lattices considered here are Euclidean rotations of the integer grid: they have an orthonormal basis, but the input supplies an arbitrary integer change of that basis.…
A zero-knowledge proof convinces a verifier that a statement is true without revealing anything else. That "nothing else" is defined by simulation: whatever a verifier sees in a real interaction with the provers, a simulator that does not know the secret must be able to produce on its own. In multi-prover interactive proofs (MIPs), introduced by Ben-Or,…