Formalizations of theorems from papers submitted to ACM STOC 2027 (the 59th Annual ACM Symposium on Theory of Computing). Paper list: https://sigact-stoc.github.io/stoc2027/ . Missions here state a main result of a STOC 2027 paper in Lean 4 with Mathlib; each mission's title begins with the paper title.
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious AdversaryResearch Paper
A multi-armed bandit models a learner that repeatedly chooses one of several actions while observing only the loss of the chosen action. The learner might have benefited from a different action, but the feedback does not reveal that action's loss. A standard benchmark is the best single arm in hindsight. A changing environment calls for a more flexible…
FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence PatternsResearch Paper
A hypergraph records a finite collection of constraints by assigning each constraint the set of variables it involves. In database query evaluation and constraint satisfaction, the shape of these overlaps can determine which decomposition methods are available. Different notions of width measure different freedoms in choosing a decomposition. Fractional…
Factor Closure in Noncommutative Algebraic ComplexityResearch Paper
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 Tight Space Lower Bound for Pivot-Based Distance OraclesResearch Paper
A distance oracle stores information about a graph so that later queries can estimate the distance between two vertices. Storing a separate answer for every pair can require quadratic space, even when the input graph itself has only linearly many edges. Allowing a multiplicative error creates a space–accuracy trade-off. The question addressed here concerns…
Testing Implies Distance Estimation with Polynomial LossResearch Paper
An adjacency query reveals one bit of a graph: whether two specified vertices share an edge. When the graph is large, even reading its entire adjacency matrix can be prohibitive. Property testing asks whether a graph satisfies a specified condition or requires a substantial fraction of its adjacencies to be changed. Distance estimation asks for that…
Breaking the Parity Barrier for Constant-Depth CircuitsResearch Paper
A Boolean circuit computes a bit by combining input bits through logical gates. Circuit complexity asks how many gates a specified function needs when its depth is restricted. Lower bounds separate computational resources even when the function itself is easy to evaluate. For circuits using AND and OR gates with unrestricted fan-in, parity has long provided…
Learning AI Agents, Market Makers, and Stress in Automated MarketsResearch Paper
Two markets can exhibit the same distribution of individual returns while arranging losses differently in time. For a monitor concerned with consecutive losses, the duration of a stressed interval is a separate object from the frequency of stressed periods. The question here is whether this distinction survives a model in which trades respond to the…
Byzantine Broadcast in O(n2) CommunicationResearch Paper
A replicated service needs a precise rule for turning one participant's proposed bit into a common decision. Byzantine broadcast asks for such a rule even when faulty participants can send inconsistent messages, omit messages, or change their behavior after being corrupted. The receiver of a message cannot infer that other parties received the same message.…
Adaptive Steps and Certificates for Semi-Streaming Shortest PathsResearch Paper
A graph can have too many edges to keep in memory while its vertices and a sparse collection of edges still fit. In the semi-streaming model, an algorithm reads an insertion-only stream repeatedly and keeps a small working memory between scans. For shortest paths, the number of complete scans is a substantial part of the cost. Assadi, Hoppenworth and…
On ZLIP: Combinatorial Structures and Reduction to √n-ZSVPResearch Paper
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.…
Fluid Limits and Upper Bounds for Randomized Greedy MatchingResearch Paper
A matching is a set of graph edges with no shared endpoint. Matching algorithms assign disjoint pairs when each participant can receive at most one partner. A local algorithm can build a matching without inspecting the whole graph, but its decisions can prevent later pairs from forming. The Modified Randomized Greedy algorithm, abbreviated MRG, introduces…
Computing faster with a full memory: Catalytic algorithms break time-space lower boundsResearch Paper
A catalytic algorithm, introduced by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), has a small clean work tape and a large dirty work tape. The dirty tape starts with arbitrary content the algorithm cannot choose, and must be returned intact at the end. The original question was whether such memory helps at all, and the first answers concerned…
Maximum Matching and Related Problems in Catalytic LogspaceResearch Paper
A matching in a graph is a collection of edges that share no vertices. A maximum matching has as many edges as any such collection. Matching is a basic problem in combinatorial optimization, but the computational resources needed to construct one depend on the machine model. A polynomial-time procedure can retain intermediate data that do not fit in…
The variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…
Perfect Local Sampling and Subquadratic Counting below the Hard-Core Uniqueness ThresholdResearch Paper
The hard-core model samples an independent set I of a finite graph with probability proportional to λ∣I∣; at λ=1 this is the uniform distribution on independent sets. It is a standard test case for the computational phase transition in counting and sampling, because the tree-uniqueness threshold …
The Power of Simple Mechanisms: A Tight e-Approximation for Gains from Trade in Matching MarketsResearch Paper
A two-sided market brings together buyers who value an item and sellers who hold it at a cost. The first-best gains from trade (GFT) match each trade whose value exceeds its cost. The Myerson–Satterthwaite theorem says that no incentive-compatible, individually rational and budget-balanced mechanism attains this benchmark, even in bilateral trade. So the…
Almost-Linear Modular Composition over Arbitrary Commutative RingsResearch Paper
Polynomial algorithms often need to substitute one polynomial into another while retaining only its remainder modulo a third polynomial. This operation is called modular composition. It describes evaluation in a polynomial quotient algebra, so it appears whenever an algebraic element is represented by a polynomial relation. Over finite fields it occurs in…
Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise IntractabilityResearch Paper
Distributed systems can need to know how many participants they contain even when
communication links change from round to round. Counting asks every participant
to determine this number exactly and then stop. Without identifiers, equal messages
need not originate from the same participant. Receiving a correct estimate is also
different from having enough…
A Bulow–Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple AuctionsResearch Paper
A seller with several distinct items must decide both what to offer and how to price it. Even when there is only one buyer and the buyer values a collection by adding its item values, the seller can offer lotteries as well as deterministic bundles. The benchmark of an optimal truthful auction therefore includes many more choices than posting one price for…
A QPTAS for Stochastic Scheduling of Bernoulli JobsResearch Paper
Scheduling systems often know a job's processing-time distribution before they know
its realized duration. An adaptive policy chooses the next job after observing
previous outcomes. For Bernoulli jobs, a job either completes immediately or
occupies a machine for its full positive size. This isolates the scheduling risk
created by a small probability of a…
No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL ModelResearch Paper
A maximal independent set selects pairwise nonadjacent vertices so that every unselected vertex has a selected neighbor. Distributed algorithms use such sets to break symmetry and organize neighboring processors. The classical algorithms of Luby (1986) and Alon, Babai and Itai (1986) achieve logarithmic randomized round bounds. The pinned submission asks…
4-Block Integer Programming is in FPTResearch Paper
An integer program chooses integer values for variables subject to linear equations and bounds, while minimizing a specified objective. Models with repeated local constraints occur in scheduling, allocation and stochastic optimization. Their size can grow with the number of local blocks even when the form of each block stays small. A useful algorithm must…
An Ω~(lognlogm) Information-Theoretic Lower Bound for Randomized Online Set CoverResearch Paper
A set cover selects sets whose union contains every required element, while minimizing the number selected. In its online version, requirements arrive over time and each must be covered immediately. A choice that looks economical on one prefix may prove unnecessary once more requirements arrive, but purchases cannot be reversed. The problem therefore…
Two choices suffice: k-out sampling leaves O(n/k) intercomponent edges for k≥2Research Paper
Random k-out sampling sparsifies a graph by local choices: every vertex independently picks k of its incident edges. The question is how much connectivity information the sample loses, measured by the number of original edges that join distinct components of the sample. Contracting each sampled component leaves exactly these edges, and adding them to a…
Metric Testing: A Characterization of One-Sided TestabilityResearch Paper
A matrix can be too large to inspect completely even when the property being tested is defined on small collections of its labels. A one-sided tester must accept every valid matrix with probability one while finding a violation with probability at least two thirds whenever repairing the matrix requires a fixed positive fraction of its entries to change. The…