CS Paper Radar

Combinatorial Bernoulli Factories with Polynomially Many Coins

Renato Paes Leme, Rad Niazadeh

cs.DS cs.GTcs.LGmath.PRstat.CO ·submitted 2026-11-12 18:19 UTC · v1

Abstract

We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases $x$ into a random vertex of a polytope $P$ whose mean is exactly $x$. For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior $x$ are polynomial in the dimension and in $1/{δ_*}$, where ${δ_*}=\min_i\{x_i,1-x_i\}$ is never supplied to the algorithm. For perfect matchings this gives $O(n^{8}{δ_*}^{-2}\log(n/{δ_*}))$ flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least $n^{2n-1}$ flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside $P$ and the promise that $x$ is far from the boundary of $P$.

Closest papers

Nearest neighbours by meaning across the whole index.

A QPTAS for Stochastic Scheduling of Bernoulli Jobs

cs.DS cs.CCmath.OC ·2026-10-08 ·Junho Hwang
benchmark similarity 0.65
Abstract · 23 pages, 1 figure

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $Ω(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

0.25

An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube

cs.DS cs.DMmath.OC ·2026-10-15 ·Thomas Dueholm Hansen, Uri Zwick
published similarity 0.62
Abstract · To appear in SOSA 2027

Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region is a combinatorial hypercube, to 2-player turn-based stochastic games (2TBSGs) in which one of the players has two actions from each one of its states. The currently fastest known randomized algorithm for finding the sink of such AUSOs is the Random-Facet algorithm of Kalai (STOC 1992), and of Matoušek, Sharir and Welzl (SoCG 1992), adapted to the binary hypercube by Gärtner (RSA 2002). The expected number of vertex queries made by the algorithm is at most $e^{2\sqrt{n}}$, where $n$ is the dimension of the cube. We design an improved randomized sink-finding algorithm that performs an expected number of only $e^{\sqrt{(2+o(1))n}}$ queries. This is the first improved bound for the problem in over two decades. The improved algorithm is obtained by adapting improved versions of the Random-Facet algorithm for solving general linear programs, and LP-type problems, developed by Kalai (STOC 1992), Gärtner (FOCS 1992), and by Hansen and Zwick (STOC 2015). The improved bound is not implied by these much more general algorithms. A key feature of the improved algorithm and its analysis is its simplicity. The structure of binary AUSOs enables a simpler description and a much simpler analysis of the adapted algorithm. In particular, the recurrence relations bounding the complexity of the algorithm depend on only one variable, and not two, and they can be solved using fairly straightforward techniques.

0.40

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms

cs.DS cs.CCcs.DMmath.CO ·2026-10-29 ·Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
theory similarity 0.61
Abstract · 32 pages plus references

For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In $G(n,p)$ with $C/n\le p\le 1-κ$, the largest induced matching has size $(1+o(1))L$ with high probability, where $L=\log_{1/(1-p)}(np)$. A simple online greedy algorithm finds an induced matching of size $(1/2-ε)L$, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size $(1/2+ε)L$ except with probability $\exp(-Ω(L\log(np)))$. In the sparse regime $p=d/n$, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.

0.25

A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

cs.DC ·2026-08-25 ·Yi-Jun Chang, Kushagra Chatterjee
similarity 0.61
Abstract

We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs $G=(V,E)$ using only a few shared random bits. Specifically, in the $\congest$ model, we compute a matching whose expected number of blocking pairs is at most $\varepsilon |E|$ in $O\left(\frac{\log(1/\varepsilon)}{\varepsilon^4}\right)$ rounds using $O\left(\log(1/\varepsilon)\right)$ shared random bits. Thus, for every constant $\varepsilon>0$, the round complexity is $O(1)$, independent of the number of vertices and the maximum degree. Previous algorithms achieve constant round complexity only for bounded-degree or almost-regular graphs; on general graphs, their round complexity depends polylogarithmically on $n$. Our main technical idea is a degree-guarded freezing rule that allows widely varying degrees to be handled by a single global charging argument, avoiding the $Θ(\log n)$ successive degree thresholds used in previous work. The shared random bits are used only to select a common random output iteration. As consequences, we obtain an $O\left( \frac{\log(1/\varepsilon)}{\varepsilon^4} + \frac{\log n}{\varepsilon} \right)$-round $\congest$ algorithm without pre-shared randomness, via a low-diameter decomposition, and an $O\left(\frac{\log(1/\varepsilon)}{\varepsilon^4}\right)$-round algorithm in the fully-scalable Massively Parallel Computation ($\mpc$) model with linear total memory.

0.08

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.60
Abstract

We generalize integer programming to the setting in which the image $A \mathbf{x}$ is restricted to an explicitly given rational polyhedron $P$. That is, we solve $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}\in P, \mathbf{x}\in\mathbb{Z}_{\geq 0}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and $P$ is an explicitly given rational polyhedron. We present a randomized algorithm running in time $(dΔ)^{O(d)}\operatorname{poly}(L)$ in this regime, where $Δ:= \|A\|_\infty$ and $L$ is the binary input length. This running time matches that of the best-known parameterized algorithms for integer programming, due to Eisenbrand and Weismantel and to Jansen and Rohwedder, and improves on the $O(d^2)$ exponent achieved by Dadush, Léonard, Rohwedder, and Verschae in a more general setting. This result enables several applications, including exact algorithms for integer programming and unbounded knapsack in which the consumed resources $A\mathbf{x}$ must satisfy arbitrary additional linear constraints. We also obtain a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant, resolving an open problem of Randolph and Węgrzycki. For integer programs with $m$ constraints and bounded row doubling, we obtain an $f(C,m)n^{O(m)}\operatorname{poly}(L)$-time algorithm and show that the dependence on $m$ in the exponent of $n$ is necessary under $\mathsf{W[1]}\ne\mathsf{FPT}$.

0.24

Sharp Bounds for Truthful-in-Expectation Scheduling

cs.GT ·2026-11-03 ·Yunpeng Li
theory similarity 0.60
Abstract

We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.

0.18

Directed Hamiltonian-Cycle Parity in $O^*((3/2)^n)$ Deterministic Time and Polynomial Space

cs.DS ·2026-09-07 ·Hanqing Li
theoryhot direction similarity 0.60
Abstract · 14 pages, no figures; revised proof and complexity bounds; added affine-product enumeration and a lower bound for complete enumeration

We give a deterministic algorithm that computes the parity of the number of Hamiltonian cycles in an $n$-vertex directed graph in $O(n^4(3/2)^n)$ time and $O(n^2)$ bits of working space, improving the $O^*(\varphi^n)$ bound of Björklund and Husfeldt. Their local-degree formula reduces the problem to a weighted sum over solutions of structured quadratic equations. We cover the corresponding ternary state space by binary subcubes, each inducing an affine system. The Kuang--Wang cover can be regenerated within the target bound; canonical ownership resolves its overlaps, while self-loop conditional expectations bound every affine solution visit. Rollback elimination shares the work across cover prefixes. The same cover gives a Las Vegas algorithm listing all $L$ solutions of $m$ affine product constraints in $N$ Boolean variables in expected time $\operatorname{poly}(N,m)((3/2)^m+L)$ and polynomial space. Finally, we show that complete enumeration can require $Ω((3/2)^n)$ visits even on strongly connected digraphs after an optimal self-loop choice. This is a limitation of the enumeration method, not a general lower bound for Hamiltonian-cycle parity.

0.40

Stochastic Matching with Polynomial Degree

cs.DS ·2026-11-02 ·Soheil Behnezhad
hot direction similarity 0.59
Abstract

We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.

0.23