CS Paper Radar

Infinite Worlds from One Example: What Local Generators Must Share

Amin Najafgholizadeh, Mohsen Afsharchi

cs.LG cs.GR ·submitted 2026-10-31 15:41 UTC · v2

Abstract

Seeded noise lets games generate any region of an unbounded world on demand. We ask what such a generator needs when every small window must come from one example, the constraint behind Wave Function Collapse. The difficulty is that local constraints can require agreement over arbitrary distances: in a brick wall, each row keeps its place between the mortar lines. We study local generators, each cell a fixed function of the randomness near it. When the constraints carry a quantity that varies across the example, no generator that applies one rule, ignoring position, to independent randomness at every cell can be both exactly valid and faithful to the example's statistics, however far each cell reads. At radius r, staying faithful forces forbidden windows at a density of at least order 1/r, and a construction attains this order. To vary the quantity between exactly valid worlds, a generator needs randomness shared along its direction. We give a finitely checkable condition under which row types drawn from the seed and the position modulo a fixed period suffice for exact validity without learning. A search over the example's patches certifies these quantities and names the input each needs. Across 52 public examples of Wave Function Collapse and 27 from other implementations, it certifies only examples where a learned generator on independent randomness stays far from valid after repair. Given that input, a neural cellular automaton and a diffusion model become valid on 10 and 8 of the 12 certified examples that receive one, and on none from independent randomness. Valid means at most one forbidden window in a thousand after repair. With octaves of seeded noise elsewhere, the automaton is valid on 45 of the 52 public examples and 21 of the 27 from other implementations, and repair keeps random access.

Comment
85 pages, 12 figures, 48 tables. v2: supplementary file merged into the main PDF as appendices; corrections in the appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

cs.FL cs.LG ·2026-09-09 ·Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
code/data similarity 0.57
Abstract · v2: fixed a typo in abstract title; added a figure in abstract page; added connections to known sufficient conditions; added a normalization…

Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization

0.67

Characterizing Local Breadth in Language Generation

cs.DS cs.FLcs.LGstat.ML ·2026-11-11 ·Jon Kleinberg, Fan Wei
similarity 0.55
Abstract

Large language models sharpen the validity--breadth trade-off: a generator should avoid hallucinations without collapsing onto a narrow set of valid outputs. We study generation from positive examples of an unknown target in the Kleinberg--Mullainathan model, with arbitrary, possibly adversarial order and no distributional or computational assumptions. Breadth is measured by lower Banach density, which rules out arbitrarily large sparse holes, unlike prefix-based lower asymptotic density. 1. Exact optima in one dimension: For each target $K$ in a countable family, we characterize its optimal lower Banach density $b(K)$ via equivalent combinatorial and topological formulations. One eventually valid generator attains all $b(K)$ simultaneously. Every $α\in[0,1/2]$ occurs as $b(K)$ in some countable family; finite Cantor--Bendixson point rank guarantees $b(K)=1/2$, even without a uniform rank bound. 2. Unavoidable trade-offs in higher dimensions: For $d\ge2$, there need not be a single best generator: optimizing density for one target may worsen the guarantee for another. An explicit family quantifies this intrinsically multi-objective trade-off. 3. Complete characterization of density profiles: We characterize the full region of simultaneously achievable guarantees, with equivalent combinatorial and topological formulations, after excluding geometrically degenerate rectangles. Every prescribed product $\prod_i[0,α_i]$, $α_i\in[0,1/2]$ can occur as an exact achievable region for some language collection. 4. Near-half guarantees and the sharp endpoint: Under a near-logarithmic nondegeneracy condition, one generator achieves filtered density at least $1/2-\varepsilon$ at all finite-point-rank targets, for every $\varepsilon>0$, improving the previous polylogarithmic threshold. The exact $1/2$ endpoint can fail even for a rank-zero singleton family.

0.24

A Randomized $\frac32$-Approximation for Strategic Facility Location on a Circle

cs.GT ·2026-09-11 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.55
Abstract · v1 is finished in June 2026, and v2 is revised with the assistance of GPT Astra-6

We study strategyproof mechanisms for locating a single facility on a circle so as to serve a set of strategic agents under the utilitarian social cost objective. We analyze a simple parity-dependent mechanism that randomizes between the Random Dictator (RD) mechanism and the Proportional Circle Distance (PCD) mechanism. For an odd number \(n\) of agents, this mechanism mixes RD and PCD with equal probability, as originally proposed by Rogowski and Dziubi{ń}ski (IJCAI 2025). For even \(n\), it mixes RD with a random-deletion extension of PCD, in which one agent is removed uniformly at random before PCD is applied to the remaining agents. Our main result shows that this mechanism is strategyproof and achieves an approximation ratio of \(\frac32\) for every \(n\ge 3\). This improves the \(\frac74\) upper bound of Rogowski and Dziubi{ń}ski, which applied only to odd \(n\), and extends the guarantee to even numbers of agents. Finally, we establish a computer-assisted lower bound of \(1.088187\ldots\) on the approximation ratio of any randomized strategyproof mechanism, improving on the previous lower bound of \(1.0456\) due to Meir (SAGT 2019).

0.34

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

cs.DS quant-ph ·2026-09-30 ·Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha
similarity 0.54
Abstract

We give an efficient algorithm for learning $k$-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying $U$ to the all-zero input. For a depth-$d$ circuit on $n$ sites with random $2\ell$-qubit gates, the algorithm learns the original circuit $U$ with high probability in $\text{poly}(n,2^{\ell d})$ time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as $\ell d = O(\log n)$. In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require $\ell d=ω(\log n)$, and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same $\ell d=ω(\log n)$ scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.

0.25

Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs

cs.DM math.PRmath.CO ·2026-09-11 ·Dávid Ferenczi, Alexander Grigoriev
theory similarity 0.54
Abstract · 18 pages, 1 figure

Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.

0.15

Minimal Scenarios Witnessing Genuine Multipartite Nonlocality Possibilistically

cs.IT quant-ph ·2026-10-08 ·Soumyadip Patra, Peter Bierhorst
similarity 0.53
Abstract

We study a strong form of genuine multipartite nonlocality (GMNL), where an $n$-partite scenario admits a quantum strategy generating outcomes belonging to a restricted set with certainty, whereas every strategy built from nonclassical resources shared among at most $k<n$ parties fails this criterion with positive probability. This generalizes what is referred to as strong contextuality/nonlocality, or pseudotelepathy, beyond ruling out local models. For the simplest five-party Bell scenario of two binary-outcome measurement settings per party, we use the inflation technique to demonstrate that a game with a perfect quantum strategy witnesses a robust separation from models built from bipartite resources under local operations and shared randomness (LOSR), establishing the behavior is LOSR-GMNL. We provide broader context for this result by investigating its simulability with resources shared among three or four parties under different resource models and alternative definitions of GMNL. A central open question is whether $n$-party quantum resources can achieve such a separation from models built from $(n-1)$-party resources, for $n\ge 3$. We make progress here by constructing a family of robustly LOSR-GMNL games with $ε$-optimal quantum strategies experimentally indistinguishable in the limit from true probability-one-winning strategies for any desired level of precision.

0.15

Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

cs.DS ·2026-09-29 ·Prashanti Anderson, Peter Manohar, Jeff Xu
similarity 0.53
Abstract · 21 pages

A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refutation, where the instances are uniformly random and thus unsatisfiable with high probability, and search, where the instances are drawn from a planted model so that they are satisfiable. While there is no formal relationship between the refutation and search variants of random CSPs, known algorithms are strikingly similar with near-identical computational thresholds. In this work, we establish a formal relationship between the known algorithms for refutation and search by showing that in either case they achieve a stronger guarantee: they output an assignment $x$ along with a certificate $π$ that the fraction of constraints satisfied by $x$ is within some small $\varepsilon$ of the optimal assignment. We call this guarantee certifiable $\varepsilon$-optimality. As an application, we design new algorithms for a model of semirandom CSPs where the instance hypergraph (or scopes) is random, but the literal negation patterns are adversarially chosen and may depend on the hypergraph. For such CSPs, we give a family of algorithms that output certifiably $\varepsilon$-optimal solutions. We additionally study such semirandom CSPs in the "strong contamination model", where an adversary is allowed to corrupt an $O(δ)$-fraction of constraints after seeing the initial CSP. For such CSPs, we give an algorithm to output a certifiably $O(δ)$-optimal solution.

0.48

World State Generator

cs.AI ·2026-09-21 ·Sungheon Jeong, Sanggeon Yun, Ryozo Masukawa, Haleh Alimohamadi, Mahdi Imani +1 more
similarity 0.53
Abstract

Language agents solve complex tasks through plans and actions. A single step the world refuses puts the goal out of reach, and what the agent does next decides the task. Prompted planners fail at exactly this point, rewriting the refused step in new words, meeting the same refusal, and burning the attempt budget without moving. They fail because the plan was never tied to the world, so a refusal has nothing in the plan to attach to. A world is where a task runs, and it has its own rules, its own admissible actions, and its own constraints. We build synthetic worlds across 7 domains and extract training data from them. A program enforces each world's rules and grades its goal, and every world is admitted only if its goal is reachable from its initial state. Agents run inside and leave verified failures paired with repairs that carried the run to a state the world certified, a record of about 226K trajectories. On this record we train the World State Generator, a model that writes a plan as checkable states of the world and keeps that plan aligned with the world it runs in. That alignment is what a plan written in language lacks, since the world it runs in has physical limits, logical dependencies, and required orders the language never states, and the plan encounters these rules only when a state fails. WSG takes that failure as the rule the world has stated and rewrites the remaining states to obey it, so the plan bends to the world as the run goes on. Across 7 public benchmarks, WSG raises end-to-end success for two open models near 30B parameters over prompting and brings to the level of proprietary model.

0.31