Marcelo Arenas, María Alejandra Schild, Bernardo Subercaseaux
We introduce a new elementary technique for proving $\#P$-hardness results under Turing reductions, and showcase its applicability by settling the counting complexity of several fundamental problems about counting orderings in graphs, posets, and geometric configurations. The technique addresses a natural difficulty in counting reductions: when designing gadgets that attempt to enforce a semantic property, the introduction of the gadgets themselves can affect the function to count in complicated ways. In a nutshell, we introduce an amplification parameter $q$ for the gadgets (e.g., replacing a subset of the vertices of a graph by $q$ copies) and show that the limiting behavior when $q$ tends to infinity, or even to negative values, filters out the unwanted effects of the gadgets, which allows us to recover the desired counts. These limits can be computed symbolically via interpolation, after showing that the probability of a random ordering satisfying the problem's constraints is a rational function in $q$. Concretely, with this methodology, we show $\#P$-completeness for counting the following objects: (a) successive vertex orderings, even on bipartite graphs, (b) $st$-numberings of graphs, (c) shellings, even for bipartite graphs, (d) perfect elimination orderings, even for split graphs, (e) linear extensions of N-free posets of height $3$, (f) linear extensions of posets of height $2$, and (g) peeling sequences of point sets. Result (e) settles a conjecture of Felsner and Manneville (2015), and although result (f) was first proved by Dittmer and Pak (2018), we include an alternative proof, using our technique, that does not rely on the result of Brightwell and Winkler (1991) about hardness of counting for general posets. Result (g) answers a question of Eppstein.
Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux
We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice such that at most $b$ bits of advice are accessed for each input, then it admits a CNF encoding with $\widetilde{O}(t + \sqrt{mb})$ clauses. This constitutes a nonuniform generalization of Robson's (TCS'91) variant of the Cook--Levin theorem, for which a naïve generalization would yield $\widetilde{O}(t+m)$ clauses; our applications leverage $b = o(m)$ to obtain significantly better bounds. Since preprocessed data structures can be modeled as computation with advice, our result allows us to translate space- and time-efficient data structures to compact CNF encodings. As an application, we derandomize a data structure of Larsen and Williams (SODA'17) to show that every $k$-CNF function on $n$ inputs can be encoded with $n^k/2^{Ω_k(\sqrt{\lg n})}$ clauses. Notably, despite encoding a $k$-CNF function, the encoding itself necessarily contains clauses of unbounded width, since an information-theoretic argument shows that the minimum number of bounded-width clauses to encode such functions is $Ω_k(n^{k}/\lg n)$ in the worst case. In general terms, our results imply that for a wide variety of NP-complete problems, one can reduce to CNF-SAT in a way that results in asymptotically fewer clauses than previously known methods.
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Branzei, Michael P. Brenner 等 36 位作者
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks, their ability to contribute to novel, expert-level mathematical discovery is less understood. We present a collection of case studies demonstrating how researchers have successfully collaborated with advanced AI models, specifically Google's Gemini-based models (in particular Gemini Deep Think and its advanced variants), to solve open problems, refute conjectures, and generate new proofs across diverse areas in theoretical computer science, as well as other areas such as economics, optimization, and physics. Based on these experiences, we extract common techniques for effective human-AI collaboration in theoretical research, such as iterative refinement, problem decomposition, and cross-disciplinary knowledge transfer. While the majority of our results stem from this interactive, conversational methodology, we also highlight specific instances that push beyond standard chat interfaces. These include deploying the model as a rigorous adversarial reviewer to detect subtle flaws in existing proofs, and embedding it within a "neuro-symbolic" loop that autonomously writes and executes code to verify complex derivations. Together, these examples highlight the potential of AI not just as a tool for automation, but as a versatile, genuine partner in the creative process of scientific discovery.