9 papers
Soft Guidance Starts to Outperform CoT Prompting as LLMs Improve
Denys Pushkin, Albert Q. Jiang, Aryo Lotfi +3
Chain-of-Thought (CoT) prompting remains the standard baseline for evaluating models' reasoning abilities. Originally, this technique was introduced to elicit step-by-step reasonin…
Recovering Assignments with One-Sided Noise
Cassandra Marcussen, Elchanan Mossel, Colin Sandon
We study the query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise. We consider the following 1-CNF recovery probl…
Finding Planted Cycles in a Random Graph
Julia Gaudio, Colin Sandon, Jiaming Xu +1
In this paper, we study the problem of finding a collection of planted cycles in an \ER random graph , in analogy to the famous Planted Clique Problem.…
Phase Transitions in Planted k-Factor Recovery
Julia Gaudio, Colin Sandon, Jiaming Xu +1
This paper studies the problem of inferring a -factor, specifically a spanning -regular graph, planted within an Erdos-Renyi random graph . We show that as the ave…
Polynomial Freiman-Ruzsa, Reed-Muller codes and Shannon capacity
Emmanuel Abbe, Colin Sandon, Vladyslav Shashkov +1
In 1948, Shannon used a probabilistic argument to show the existence of codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple…
Tensor Reed-Muller Codes: Achieving Capacity with Quasilinear Decoding Time
Emmanuel Abbe, Colin Sandon, Oscar Sprumont
Define the codewords of the Tensor Reed-Muller code to be the evaluation vectors of all multivariate polynomials in the variables $\le…