Theory of Computing Report

We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis. 1) Obfuscation can serve as a general-purpose *worst-case to average-case reduction*, reducing the existence of various forms of cryptography to corresponding worst-case assumptions. 2) We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worst-case hardness assumptions beyond P \neq NP, and (ii) leveraging *worst-case* hardness reductions, either proved by traditional complexity-theoretic methods or facilitated further by cryptography. Concretely, our results include: - Optimal Hardness. Assuming sub-exponential indistinguishability obfuscation (iO), we give fine-grained worst-case to average case reductions for circuit-SAT. In particular, if finding an NP-witness requires nearly brute-force time in the worst case, then the same is true for some efficiently sampleable distribution. In fact, we show that under these assumptions, there exist families of one-way functions with optimal time-probability security tradeoffs. Under an additional, stronger assumption -- the optimal non-deterministic hardness of refuting circuit-SAT -- we construct additional cryptographic primitives such as PRGs and public-key encryption that have such optimal time-advantage security tradeoffs. - Direct Product Hardness. Again assuming iO and optimal non-deterministic hardness of SAT refutation, we show that the "(search) $k$-fold SAT problem" -- the computational task of finding satisfying assignments to $k$ circuit-SAT instances simultaneously -- has (optimal) hardness roughly $(T/2^n)^k$ for time $T$ algorithms. In fact, we build "optimally secure one-way product functions" (Holmgren-Lombardi, FOCS '18), demonstrating that optimal direct product theorems hold for some choice of one-way function family. - Single-Input Correlation Intractability. Assuming either iO or LWE, we show a worst-case to average-case reduction for strong forms of single-input correlation intractability. That is, powerful forms of correlation-intractable hash functions exist provided that a collection of worst-case "correlation-finding" problems are hard. - Non-interactive Proof of Quantumness. Assuming sub-exponential iO and OWFs, we give a non-interactive proof of quantumness based on the worst-case hardness of the white-box Simon problem. In particular, this proof of quantumness result does not explicitly assume quantum advantage for an average-case task. To help prove our first two results, we show along the way how to improve the Goldwasser-Sipser "set lower bound" protocol to have communication complexity quadratically smaller in the multiplicative approximation error $\epsilon$.

Science is correlations with stories. Validity is the style guide for these stories. It is the acceptable rhetoric that scientific stories can use. Validity constrains how we talk about empirical results, forcing scientists to use a particular form of argumentation to make their case. Validity provides rules for what makes a story “good” science.

As it is typically taught, scientific validity is immediately broken down into two disjoint components: internal validity and external validity. A scientific study is internally valid if the evidence presented supports its main claims. It is externally valid if other scientists can apply the results to other studies. Though the term validity carries a heavy rhetorical baggage of truthfulness, you can see that what exactly we mean by “support” or “apply” is necessarily hard to pin down. And hence we have to rely on community expectations for working definitions.

You can see disciplinary norms most clearly when you dig into internal validity. Definitively showing that a scientific observation corroborates a hypothesis is a lofty goal. In practice, internal validity is reduced to a checklist. Were there obvious flaws in the experimental setup? Were there variables that the authors didn’t control for? Did the authors train on the test set?

This checklist might not be a set of necessary or even sufficient conditions for inferring good science. The associated community decided on this particular list because, at some time in the past, someone skipped one of these steps and bad science happened. For example, unblinding in a randomized trial might threaten internal validity. It’s possible that knowing which group a subject was in influenced the subject’s or trialist’s behavior in the experiment. Hence, we decided that preserving blinding in randomized trials is critical to mitigate bias.

On the other hand, some zealous science reformers argue for conventions with far less obvious necessity. My favorite example is preregistration. For its adherents, preregistration constrains “research degrees of freedom” so that people don’t data dredge and find spurious signals in their data. However, while writing a good experimental plan is worthwhile, preregistration infantilizes science into a woefully naive sequence of randomized controlled experiments. A “valid” preregistration plan necessitates knowing the outcome of all aspects of an experiment before conducting it. Preregistration makes it impossible to adapt to the actuality of experimental conditions.

In machine learning, we had our own internal validity conventions with suspect necessity. Validity was a major topic in our machine learning evaluation class, and realizing that these conventions were just conventions was the strongest takeaway for me. Taboos like adaptive overfitting to the test set are still taught as part of our rules for internal validity. More and more evidence comes in that this doesn’t compromise claims in the way we thought it did. The upside of these negative examples is that communities can adjust their standards. We can update our rigid validity checklists in light of new empirical data, like good scientists should.

External validity concerns whether results in one study apply to another study. In other words, are experiments reproducible in different contexts? The stories of external validity concern just how much we expect a result to hold as context changes. Which parts of a logical relationship should be the same, and which parts should differ in different settings? These stories are useful because they facilitate consensus about the mechanisms that truly make an intervention effective. If we accept that an original experiment was done in good faith, tests of external validity probe which parts of the experimental setup are needed to yield a similar result. How we describe the difference between a replication context and the original context is another set of stories.

Finally, there is construct validity, which is far more complex and more challenging to operationalize. It is the stories we tell about our interventions and measurements themselves. How do empirical artifacts connect to abstract concepts? There are tests of construct validity, but these tests necessarily rely on the specific expectations of the relevant scientific disciplines. The constructs of psychology differ from those in cell membrane biology, even though they both pertain to human systems.

These myriad facets of validity not only provide a style guide for writing but provide a framework for critique.1 Validity trains scientists to be maximally skeptical. How to look for flaws in the experimental setup, to look for violations of ceteris paribus assertions, to look for flaws in generalizability.

It’s critical for students to learn this! It’s how disciplines progress, for better or for worse. The social culture of research proceeds by finding bugs in the theoretical grounding of past results and doing new studies to patch the bugs. Scientists have to be trained to find bugs, and hence it is critical that any course on methods and evaluation covers the norms for what bugs are in the first place. Peer review, in its broadest, most general form, is done in the domain specific language of validity.

Internal validity is how you poke at people’s experimental setups, their statistical methodology, and the inherent biases in their designs. Construct validity attacks the meaning and interpretations of experimental interventions and outcomes themselves. External validity is a set of critiques against generalizability.

It’s helpful to have these scientific rules written out so everyone can agree upon a baseline for scientific play. We can (and do!) change the rules if they are preventing us from telling useful stories about correlations. At its best, validity enables improvisational creative work where scientists push against the boundaries of empirical techniques and serendipitously find new facts. At its worst, validity handcuffs researchers into dribbling out incremental results for CV padding. Like all academic systems, the rules of the validity game change slowly.

Addendum: Jordan Ellenberg wrote to me with a necessary rejoinder to this post: “I think you are unnecessarily harsh about dribbling out incremental results, which in my view is the fertilizer of science, both in the sense that it promotes growth and in the sense that some people see it as just a pile of shit.” He’s right! I need to figure out how to rephrase the second-to-last sentence here. To be continued…

Subscribe now

By Ben Recht

Authors: Pritam Chattopadhyay, Avijit Misra, Tanmoy Pandit, Goutam Paul

According to the Landauer principle, any logically irreversible process accompanies entropy production, which results in heat dissipation in the environment. Erasing of information, one of the primary logically irreversible processes, has a lower bound on heat dissipated into the environment, called the Landauer bound (LB). However, the practical erasure processes dissipate much more heat than the LB. Recently, there have been a few experimental investigations to reach this bound both in the classical and quantum domains. There has also been a spate of activities to enquire about this LB in finite time, with finite-size heat baths, non-Markovian and nonequilibrium environment in the quantum regime where the effects of fluctuations and correlation of the systems with the bath can no longer be ignored. This article provides a comprehensive review of the recent progress on the Landauer bound, which serves as a fundamental principle in the thermodynamics of computation. We also provide a perspective for future endeavors in these directions. Furthermore, we review the recent exploration toward establishing energetic bounds of a computational process. We also review the thermodynamic aspects of error correction, which is an indispensable part of information processing and computations. In doing so, we briefly discuss the basics of these fields to provide a complete picture.

Authors: Alexander S. Wein

This is a survey on the use of low-degree polynomials to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems. In a nutshell, this framework measures the complexity of a statistical task by the minimum degree that a polynomial function must have in order to solve it. The main goals of this survey are to (1) describe the types of problems where the low-degree framework can be applied, encompassing questions of detection (hypothesis testing), recovery (estimation), and more; (2) discuss some philosophical questions surrounding the interpretation of low-degree lower bounds, and notably the extent to which they should be treated as evidence for inherent computational hardness; (3) explore the known connections between low-degree polynomials and other related approaches such as the sum-of-squares hierarchy and statistical query model; and (4) give an overview of the mathematical tools used to prove low-degree lower bounds. A list of open problems is also included.

Authors: Djamel Eddine Amir, Benjamin Hellouin de Menibus

Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for $G$-shifts, where $G$ is a finitely generated group with decidable word problem. A $G$-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of $G$-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.

Authors: Jasper Yao

We establish fundamental computational complexity barriers to verifying AI safety as system capabilities scale. Our main results show that for AI systems with expressiveness EXP$(m)$ above a critical threshold $\tau$, safety verification requires exponential time and is coNP-complete. We formalize the Capability-Risk Scaling (CRS) dynamic, which demonstrates how increasing AI capability drives societal safety requirements toward perfection, creating an inescapable tension with verification complexity. Through four core theorems, we prove that (1) verification complexity grows exponentially with system expressiveness, (2) safe policies comprise at most a $2^{-2^m}$ fraction of the policy space, (3) no finite set of alignment techniques can provide universal coverage, and (4) robust safety properties form measure-zero sets for neural networks. These results characterize an "intractability gap" where practical safety requirements fall within the region of computational intractability. We conclude by presenting a strategic trilemma: AI development must either constrain system complexity to maintain verifiable safety, accept unverifiable risks while scaling capabilities, or develop fundamentally new safety paradigms beyond verification. Our work provides the first systematic complexity-theoretic analysis of AI alignment and establishes rigorous bounds that any safety approach must confront. A formal verification of the core theorems in Lean4 is currently in progress.

Authors: Salwa Faour, Fabian Kuhn

The maximum independent set problem is a classic optimization problem that has also been studied quite intensively in the distributed setting. While the problem is hard to approximate in general, there are good approximation algorithms known for several sparse graph families. In this paper, we consider deterministic distributed CONGEST algorithms for the weighted version of the problem in trees and graphs of bounded arboricity. For trees, we prove that the task of deterministically computing a $(1-\epsilon)$-approximate solution to the maximum weight independent set (MWIS) problem has a tight $\Theta(\log^*(n) / \epsilon)$ complexity. The lower bound already holds on unweighted oriented paths. On the upper bound side, we show that the bound can be achieved even in unrooted trees. For graphs $G=(V,E)$ of arboricity $\beta>1$, we give two algorithms. If the sum of all node weights is $w(V)$, we show that for any $\epsilon>0$, an independent set of weight at least $(1-\epsilon)\cdot \frac{w(V)}{4\beta}$ can be computed in $O(\log^2(\beta/\epsilon)/\epsilon + \log^* n)$ rounds. This result is obtained by a direct application of the local rounding framework of Faour, Ghaffari, Grunau, Kuhn, and Rozho\v{n} [SODA '23]. We further show that for any $\epsilon>0$, an independent set of weight at least $(1-\epsilon)\cdot\frac{w(V)}{2\beta+1}$ can be computed in $O(\log^3(\beta)\cdot\log(1/\epsilon)/\epsilon^2 \cdot\log n)$ rounds. This improves on a recent result of Gil [OPODIS '23], who showed that a $1/\lfloor(2+\epsilon)\beta\rfloor$-approximation to the MWIS problem can be computed in $O(\beta\cdot\log n)$ rounds. As an intermediate step, we design an algorithm to compute an independent set of total weight at least $(1-\epsilon)\cdot\sum_{v\in V}\frac{w(v)}{deg(v)+1}$ in time $O(\log^3(\Delta)\cdot\log(1/\epsilon)/\epsilon + \log^* n)$, where $\Delta$ is the maximum degree of the graph.

Authors: Samuel C. Gutekunst

We study the edge-length polytope, motivated both by algorithmic research on the Circulant Traveling Salesman Problem (Circulant TSP) and number-theoretic research related to the Buratti-Horak-Rosa conjecture. Circulant TSP is a special case of TSP whose overall complexity is a significant still-open question, and where on an input with vertices $\{1, 2, ..., n\}$, the cost of an edge $\{i, j\}$ depends only on its length $\min\{|i-j|, n-|i-j|\}$. The edge-length polytope provides one path to solving circulant TSP instances, and we show that it is intimately connected to the factorization of $n$: the number of vertices scales with $n$ whenever $n$ is prime and with $n^{3/2}$ whenever $n$ is a prime-squared, but there are a superpolynomial number of vertices whenever $n$ is a power of 2. In contrast, the more-standard Symmetric TSP Polytope has roughly $n!$ vertices. Hence, for Circulant TSP, a brute-force algorithm checking every vertex is actually efficient in some cases, based on the factorization of $n$. As an intermediate step, we give superpolynomial lower-bounds on two combinatorial sequences related to the Buratti-Horak-Rosa conjecture, which asks what combinations of edge lengths can comprise a Hamiltonian path.

Authors: Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada

The concept of $k$-planarity is extensively studied in the context of Beyond Planarity. A graph is $k$-planar if it admits a drawing in the plane in which each edge is crossed at most $k$ times. The local crossing number of a graph is the minimum integer $k$ such that it is $k$-planar. The problem of determining whether an input graph is $1$-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor $2 - \varepsilon$ for any $\varepsilon > 0$ [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of $k = 1$, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case $k \ge 1$ and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing $1$-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most $3$ and pathwidth at most $4$, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most $2$.

Authors: Noga Alon, Danny Segev

Since its inception in the mid-60s, the inventory staggering problem has been explored and exploited in a wide range of application domains, such as production planning, stock control systems, warehousing, and aerospace/defense logistics. However, even with a rich history of academic focus, we are still very much in the dark when it comes to cornerstone computational questions around inventory staggering and to related structural characterizations, with our methodological toolbox being severely under-stocked. The central contribution of this paper consists in devising a host of algorithmic techniques and analytical ideas -- some being entirely novel and some leveraging well-studied concepts in combinatorics and number theory -- for surpassing essentially all known approximation guarantees for the inventory staggering problem. In particular, our work demonstrates that numerous structural properties open the door for designing polynomial-time approximation schemes, including polynomially-bounded cycle lengths, constantly-many distinct time intervals, so-called nested instances, and pairwise coprime settings. These findings offer substantial improvements over currently available constant-factor approximations and resolve outstanding open questions in their respective contexts. In parallel, we develop new theory around a number of yet-uncharted questions, related to the sampling complexity of peak inventory estimation as well as to the plausibility of groupwise synchronization. Interestingly, we establish the global nature of inventory staggering, proving that there are $n$-item instances where, for every subset of roughly $\sqrt{n}$ items, no policy improves on the worst-possible one by a factor greater than $1+\epsilon$, whereas for the entire instance, there exists a policy that outperforms the worst-possible one by a factor of nearly $2$, which is optimal.

I just beat Sifu. The last boss was hard. I got there with about my actual age, so it was sort of personal that I could still beat Yang. (In Sifu your character ages when you lose, and it’s game over at 70, I hope this is one of the more unrealistic aspects of the game; I enjoyed this mechanism). It took many trials, and I had to carefully study his timings and moves. But in the end, the experience has confirmed my thoughts in the previous post, that we need to rethink combat systems to make them much more fun and engaging. Strong as he was, Yang was stupid. He should have noticed that after a specific combo, I was almost always able to land a few hits. This made the fight quite dull, in the end.

So I am planning to update my scratch game to better illustrate, and the next step would be to put some AI in it, for which I guess I need to port it to C++ or something, I suspect it’s not easy to do that in Scratch.

By Manu

The Trevisan Prize for outstanding work in the Theory of Computing is sponsored by the Department of Computing Sciences at Bocconi University and the Italian Academy of Sciences.

The prize is named in honor of Luca Trevisan in recognition of his major contributions to the Theory of Computing. It aims to recognize outstanding work in the field, and to broaden the reach of awards both in terms of research areas and recognition of individuals.

The prize is biennial (given once every two years) and consists of two prizes, given to:

• A mid-career scientist whose work has had a significant and lasting impact
• An early-career scientist whose work has demonstrated exceptional promise

In addition to the one-time monetary prize, the Italian Academy of Sciences will contribute a commemorative statue, presented to the winners as a symbol of their excellence.

The prize ceremony will take place at Bocconi University, where the winners will be asked to give public lectures (three in total):

• Mid-career awardee: one scientific lecture and one lecture aimed at a general audience
• Early-career awardee: one scientific lecture

The call for nominations can be found here: https://cs.unibocconi.eu/trevisan-prize

By Boaz Barak

Computer Science Canada | Informatique Canada has announced the list of recipients of its awards for 2024. 

Members of the TCS community will be pleased to see that Faith Ellen (University of Toronto) is one of the recipients of the Lifetime Achievement Award 2024.  Congratulations Faith!

On a personal note, I am also delighted to see that Nicola Cotumaccio was selected for the Canadian Computer Science Distinguished Dissertation Award 2024 . Nicola's PhD thesis, entitled Data compression meets automata theory, was supervised by Travis Gagie (Dalhousie University), Nicola Prezza (Ca' Foscari University of Venice) and Catia Trubiani (Gran Sasso Science Institute), as part of a joint Gran Sasso Science Institute-Dalhousie University degree,  and was supported by a scholarship from Dante Labs. 

Nicola was also a co-recipient of the Best PhD thesis award of the Italian Chapter of the EATCS. 

To my mind, the best way to get a glimpse of the work Nicola presented in his award-winning doctoral dissertation is to read the short summary he published in the Bulletin of the EATCS. However, I strongly encourage anyone interested in TCS to have a look at the full dissertation or at the articles on which it is based, including one that was published in the JACM. 

Since February 2024, Nicola has been a postdoctoral researcher at the University of Helsinki. I look forward to seeing the developments in his academic career. 

By Luca Aceto

“The obstacle was always the path.” Adapted from a Zen proverb

In the Renaissance, apprentices learned to paint by grinding pigments, mixing oils, stretching canvas, and copying masterworks line by line. In architecture, students spent years sketching by hand before they touched a computer. In math, the best way to understand a theorem is to try to prove it yourself—and fail.

Today, that slow accumulation of competence is being replaced by a faster rhythm.

Ask an AI to write a proof, generate a building, produce an image, or answer a math question—and it will. But something essential gets skipped. And what gets skipped doesn’t just disappear. It quietly erodes.

AI gives us output without process. The result: polished answers with no foundation.

The Eroding Scaffold

Learning isn’t just about information. It’s about structure and the path you took to get there. You don’t truly understand a concept until you’ve built the scaffold it rests on—step by step, skill by skill.

Mira’s Derivative

Take Mira, a student learning calculus. She’s supposed to learn how to compute derivatives. The teacher explains the chain rule: when one function is nested inside another, you must differentiate both, in the right order. It’s abstract, so Mira does what students do—she turns to an AI tutor.

She types:

“Find the derivative of sin(x² + 3x).”

The AI answers instantly:

cos(x² + 3x) · (2x + 3)

It even offers a short explanation. Mira copies it down and moves on.

What she didn’t do:

– Simplify the inner expression.

– Apply the rule mechanically.

– Make a mistake and figure it out.

– Internalize the rhythm of composition and change.

Now fast-forward two months. Mira sees a problem she’s never encountered:

“Differentiate xᵡ.”

She freezes. No familiar template. No AI available. No internal scaffold to fall back on.

She reached the destination — but never built the path.

The skipped struggle was what encoded the concept.

Leo’s Essay

Now consider Leo, a college student writing an essay on political philosophy. He’s supposed to take a position on Hobbes’s Leviathan and argue whether absolute sovereignty is justified today.

Traditionally, Leo would:

– Clarify Hobbes’s argument,

– Develop a counterposition,

– Find textual evidence,

– Draft and revise a logical structure.

Instead, he types:

“Write a 5-paragraph essay arguing against Hobbes’ justification of sovereign power.”

The AI delivers—fluent, plausible, even citing sources. Leo pastes it in, tweaks a few lines, and submits.

A week later, he’s asked:

“How would Hobbes respond to modern surveillance capitalism?”

He flounders. The structure was never his. The reasoning was never practiced. The scaffolding was never built.

He didn’t outsource writing. He outsourced thinking.

Teachers aren’t grading the prose. They’re grading the reasoning it reveals.

Art Without Sketching, Architecture Without Lines

In design and architecture, we’re seeing the same thing. AI can generate facades, floor plans, and renders in minutes. But without grounding in scale, structure, or constraint, designs become fragile—beautiful but unbuildable. The result is a facade that ignores sun direction, a floor plan that fails fire code, and a portrait with six fingers.

In art, tools like Midjourney let users create stunning illustrations from a few words. But if you can’t draw, can you see? Can you revise? Can you critique? Can you tell what’s off?

Drawing is not just a means of production—it’s a way of learning to notice. Line by line, it teaches scale, proportion, balance, rhythm. Without that training, feedback becomes guesswork. Revision becomes roulette.

When the tool does the shaping, the human stops developing the eye.

And when the AI makes a mistake—one that’s subtle, structural, or compositional—there’s no foundation to catch it. You don’t just lose the sketch. You lose the ability to tell when something is wrong.

Oversight Collapse

AI doesn’t reason — it samples.

When a model like GPT writes a paragraph or answers a question, it isn’t deriving a conclusion from first principles. It’s drawing from a probability distribution — choosing what sounds most plausible based on past data.

The result? Output that feels fluent — but isn’t guaranteed to be correct.

That’s what makes AI mistakes dangerous. They’re not just wrong. They’re plausibly wrong — errors with the gloss of insight. And if we’ve skipped the scaffolding, we can’t tell the difference between coherence and truth.

This is the tipping point: when we’re still “in the loop,” but can no longer verify what we see. We’ve become fluent — but not competent. You look like you’re in control. But you’re just along for the ride.

And the risk isn’t limited to math or logic. In “wicked” domains — ethics, design, law, writing — there may be no single right answer. What matters is the ability to justify, adapt, revise, and notice what doesn’t quite fit.

That capacity comes from friction — from having built the internal scaffold of reasoning.

AI gives us output. But it skips the reasoning. It removes the friction — and with it, the growth.

From Work to Erosion

In a recent post, I argued that AI is reshaping work not by replacing entire jobs, but by separating judgment/decision from execution/action. Tools like GPT, Copilot, and dashboards take over action-level tasks. But what remains human is the ability to frame problems, make judgments, and verify outcomes.

In that example, Ada, a software engineer, wasn’t made obsolete. Her job changed. Execution was automated. Judgment was not.

But here’s the deeper risk: what if using AI to execute also erodes our ability to decide?

That’s the dynamic explored here. When AI lets us skip foundational steps—whether in calculus, writing, or design—it removes the very scaffolding that enables judgment to form.

At first, it feels like acceleration. But over time, it becomes erosion.

The erosion of action-level skill becomes the erosion of decision-level agency.

What Can Be Done

The goal isn’t to abandon AI. It’s to use it without losing ourselves.

That means:

– Choosing tools that show their work, not just their output.

– Practicing skills we no longer “need,” because they still underpin everything else.

– Teaching not just what to do, but how to decide, how to verify, and how to notice what’s missing.

What’s at stake isn’t just productivity. It’s agency.

Final Thought: The Skills We Skip Are Still Ours to Build

When we let AI do the scaffolding for us, we don’t just skip steps—we weaken the very structures that make thinking, reasoning, and creating possible.

The skills we skip don’t vanish. They decay. Quietly. Until we need them—and find we’ve forgotten how they worked.

So yes, use AI. But build the scaffold anyway.
Because the point isn’t just getting it right — it’s still knowing what right looks like.

That’s the kind of knowing worth protecting.

Originally published in this Substack post.

By nisheethvishnoi

Authors: Alfredo Hubard, Arnaud de Mesmay, Hugo Parlier

In this paper, we provide upper and lower bounds on the crossing numbers of dense graphs on surfaces, which match up to constant factors. First, we prove that if $G$ is a dense enough graph with $m$ edges and $\Sigma$ is a surface of genus $g$, then any drawing of $G$ on $\Sigma$ incurs at least $\Omega \left(\frac{m^2}{g} \log ^2 g\right)$ crossings. The poly-logarithmic factor in this lower bound is new even in the case of complete graphs and disproves a conjecture of Shahrokhi, Sz\'ekely and Vrt'o from 1996. Then we prove a geometric converse to this lower bound: we provide an explicit family of hyperbolic surfaces such that for any graph $G$, sampling the vertices uniformly at random on this surface and connecting them with shortest paths yields $O\left(\frac{m^2}{g} \log ^2 g\right)$ crossings in expectation.

Authors: Josef Hoppe, Vincent P. Grande, Michael T. Schaub

Cell complexes (CCs) are a higher-order network model deeply rooted in algebraic topology that has gained interest in signal processing and network science recently. However, while the processing of signals supported on CCs can be described in terms of easily-accessible algebraic or combinatorial notions, the commonly presented definition of CCs is grounded in abstract concepts from topology and remains disconnected from the signal processing methods developed for CCs. In this paper, we aim to bridge this gap by providing a simplified definition of CCs that is accessible to a wider audience and can be used in practical applications. Specifically, we first introduce a simplified notion of abstract regular cell complexes (ARCCs). These ARCCs only rely on notions from algebra and can be shown to be equivalent to regular cell complexes for most practical applications. Second, using this new definition we provide an accessible introduction to (abstract) cell complexes from a perspective of network science and signal processing. Furthermore, as many practical applications work with CCs of dimension 2 and below, we provide an even simpler definition for this case that significantly simplifies understanding and working with CCs in practice.

Authors: Pengfei Wang, Ziyang Zhang, Wensong Wang, Shuangmin Chen, Lin Lu, Shiqing Xin, Changhe Tu

Extracting high-fidelity mesh surfaces from Signed Distance Fields has become a fundamental operation in geometry processing. Despite significant progress over the past decades, key challenges remain namely, how to automatically capture the intricate geometric and topological structures encoded in the zero level set of SDFs. In this paper, we present a novel isosurface extraction algorithm that introduces two key innovations: 1. An incrementally constructed power diagram through the addition of sample points, which enables repeated updates to the extracted surface via its dual regular Delaunay tetrahedralization; and 2. An adaptive point insertion strategy that identifies regions exhibiting the greatest discrepancy between the current mesh and the underlying continuous surface. As the teaser figure shows, our framework progressively refines the extracted mesh with minimal computational cost until it sufficiently approximates the underlying surface. Experimental results demonstrate that our approach outperforms sofa methods, particularly for models with intricate geometric variations and complex topologies.

Authors: Hong Duc Bui

We resolve a conjecture posed by Covella, Frati and Patrignani by proving the straight-line orthogonal drawing of the complete ternary tree with $n$ nodes satisfying the subtree separation property with smallest area has area $\Omega(n^{1.031})$. We also improve the upper bound of this area to $O(n^{1.032})$.

Authors: Theodoros Yianni, Farid Shahandeh

Generalized contextuality is a hallmark of nonclassical theories like quantum mechanics. Yet, three fundamental computational problems concerning its decidability and complexity remain open. First, determining the complexity of deciding if a theory admits a noncontextual ontological model; Second, determining the complexity of deciding if such a model is possible for a specific dimension $k$; Third, efficiently computing the smallest such model when it exists, given that finding the smallest ontological model is NP-hard. We address the second problem by presenting an algorithm derived from a geometric formulation and its reduction to the intermediate simplex problem in computational geometry. We find that the complexity of deciding the existence of a noncontextual ontological model of dimension $k$ is at least exponential in the dimension of the theory and at most exponential in $k$. This, in turn, implies that computing the smallest noncontextual ontological model is inefficient in general. Finally, we demonstrate the fundamental difference between finding the smallest noncontextual ontological model and the smallest ontological model using an explicit example wherein the respective minimum ontic sizes are five and four.

Authors: José Luis Balcázar

We state the graph-theoretic computational problem of finding tight paths in a directed, edge-weighted graph, as well as its simplification of finding tight pairs. These problems are motivated by the need of algorithms that find so-called basic antecedents in closure spaces, in one specific approach to data analysis. We discuss and compare several algorithms to approach these problems.

Authors: Max Lovig, Conor Sheehan, Konstantinos Tsirkas, Ilias Zadik

Local-search methods are widely employed in statistical applications, yet interestingly, their theoretical foundations remain rather underexplored, compared to other classes of estimators such as low-degree polynomials and spectral methods. Of note, among the few existing results recent studies have revealed a significant "local-computational" gap in the context of a well-studied sparse tensor principal component analysis (PCA), where a broad class of local Markov chain methods exhibits a notable underperformance relative to other polynomial-time algorithms. In this work, we propose a series of local-search methods that provably "close" this gap to the best known polynomial-time procedures in multiple regimes of the model, including and going beyond the previously studied regimes in which the broad family of local Markov chain methods underperforms. Our framework includes: (1) standard greedy and randomized greedy algorithms applied to the (regularized) posterior of the model; and (2) novel random-threshold variants, in which the randomized greedy algorithm accepts a proposed transition if and only if the corresponding change in the Hamiltonian exceeds a random Gaussian threshold-rather that if and only if it is positive, as is customary. The introduction of the random thresholds enables a tight mathematical analysis of the randomized greedy algorithm's trajectory by crucially breaking the dependencies between the iterations, and could be of independent interest to the community.

In the June CACM, Micah Beck writes an opinion piece Accept the Consequences where he is quite skeptical of the role of theory in real-world software development, concluding

It is important that we teach practical computer engineering as a field separate from formal computer science. The latter can help in the understanding and analysis of the former, but may never model it well enough to be predictive in the way the physical sciences are.

I certainly agree that theoretical results can't perfectly predict how algorithms work in practice, but neither does physics. The world is much more complex, both computationally and physically, to perfectly model. Physics gives us an approximation to reality that can help guide engineering decisions and theory can do the same for computation.

You need a basis to reason about computation, lest you are just flying blind. Theory gives you that basis.

Let's consider sorting. Beck complains that Quicksort runs in \(O(n^2)\) time in the worst case even though it is used commonly in practice, while the little-used Insertion sort runs in worst-case \(O(n\log n)\). Let's assume Beck meant an algorithm like heapsort that actually has \(O(n\log n)\) worst-case performance. But theorists do more than fixate on worst-case performance, Quicksort runs in \(O(n\log n)\) on average, and on worst-case if you use a random pivot, or a more complex deterministic pivoting algorithm. Introsort combines Quicksort efficiency and worst-case guarantees and is used in some standard libraries.

Beck worries about secondary storage and communication limitations but theorists have studied sorting in those regimes as well. 

The other example he talks about is about a theoretical result that one cannot use an unreliable network to implement one that is completely reliable while textbooks consider TCP to be reliable. But in fact TCP was designed to allow failure because it took account of the theoretical result, not in spite of it.

Beck ends the article talking about Generative AI where theory hasn't kept up with practice at all. Beck calls for using classical AI tools based on formal logic as guardrails for generative AI. However, the lack of theoretical understanding suggests that such guardrails may significantly weaken generative AI's expressive power. Without adequate theory, we must instead rely more heavily on extensive testing, particularly for critical systems.

There are stronger examples Beck could have used, such as algorithms that solve many NP-complete problems efficiently in practice despite their theoretical intractability. Even here, understanding the theoretical limitations helps us focus on developing better heuristics and recognizing when problems might be computationally difficult.

I agree with Beck that relying solely on the theoretical models can cause some challenges but rather than have the students "unlearn" the theory, encourage them to use the theory appropriately to help guide the design of new systems.

Beck's call to separate software development from theory only underscores how important we need to keep them intertwined. Students should know the theoretical foundations, for they shape problem solving, but they should also understand the limitations of these models.

By Lance Fortnow

Trevisan Prize 2025

Here is a call for nominations for a new theoretical computer science prize, in memory of  Luca Trevisan. (h/t Alon Rosen.)

Three Near Future Events at HUJI

While the Erdős Lectures 2025 given by Mehtaab S. Sawhney, are still going strong, here are announcements of three near-future events.

1. Landau’s lectures: Jonathan Pila (Oxford)
2. 6th Joram Seminar: hyperconnectivity and Groups, speakers Noam Lifshitz, Guy Kindler, Dor Minzer. 
3. The 14th Annual Conference of the Israeli Chapter of the Game Theory Society will take place at Hebrew University on Thursday, June 24, 2025 (Program ). The afternoon session will celebrate Robert Aumann’s 95th birthday.

    

By Gil Kalai

This announcement is meant to spread the word about a new award in Theoretical Computer Science, dedicated to Luca Trevisan. Please nominate your fellow researchers!

The deadline for nominations is August 2025 (with a notification of intent due July 31). More information about the call for nominations and the award can be found on the website; some of it is reproduced below.

The prize is named in honor of Luca Trevisan in recognition of his major contributions to the Theory of Computing. It aims to recognize outstanding work in the field, and to broaden the reach of awards both in terms of research areas and recognition of individuals. 

The prize is biennial (given once every two years) and consists of two prizes, given to:

• A mid-career scientist whose work has had a significant and lasting impact (15K EUR)
• An early-career scientist whose work has demonstrated exceptional promise (10K EUR)

In addition to the one-time monetary prize, the Italian Academy of Sciences will contribute a commemorative statue, presented to the winners as a symbol of their excellence.

By plustcs

Authors: Mukul Lokhande, Santosh Kumar Vishvakarma

The increasing complexity of AI models requires flexible hardware capable of supporting diverse precision formats, particularly for energy-constrained edge platforms. This work presents PARV-CE, a SIMD-enabled, multi-precision MAC engine that performs efficient multiply-accumulate operations using a unified data-path for 4/8/16-bit fixed-point, floating point, and posit formats. The architecture incorporates a layer adaptive precision strategy to align computational accuracy with workload sensitivity, optimizing both performance and energy usage. PARV-CE integrates quantization-aware execution with a reconfigurable SIMD pipeline, enabling high-throughput processing with minimal overhead through hardware-software co-design. The results demonstrate up to 2x improvement in PDP and 3x reduction in resource usage compared to SoTA designs, while retaining accuracy within 1.8% FP32 baseline. The architecture supports both on-device training and inference across a range of workloads, including DNNs, RNNs, RL, and Transformer models. The empirical analysis establish PARVCE incorporated POLARON as a scalable and energy-efficient solution for precision-adaptive AI acceleration at edge.

Authors: Shahaf Bassan, Guy Amir, Meirav Zehavi, Guy Katz

Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of trees (e.g., boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what particularly makes an ensemble (un)-interpretable, including how fundamental factors like the (1) *number*, (2) *size*, and (3) *type* of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for various ensemble configurations. Our analysis uncovers nuanced complexity patterns influenced by various factors. For example, we demonstrate that under standard complexity assumptions like P$\neq$NP, interpreting ensembles remains intractable even when base models are of constant size. Surprisingly, the complexity changes drastically with the number of base models: small ensembles of decision trees are efficiently interpretable, whereas interpreting ensembles with even a constant number of linear models remains intractable. We believe that our findings provide a more robust foundation for understanding the interpretability of ensembles, emphasizing the benefits of examining it through a computational complexity lens.

Authors: Petr Hliněný, Jan Jedelský

We introduce a two-way connection between FO transductions (logical transformations) of planar graphs, and a certain variant of fan-crossing (fan-planar) drawings of graphs which for bounded-degree graphs essentially reduces to being k-planar for fixed k. For graph classes, this connection allows to derive non-transducibility results from nonexistence of the said drawings and, conversely, from nonexistence of a transduction to derive nonexistence of the said drawings. For example, the class of 3D-grids is not k-planar for any fixed k. We hope that this connection will help to draw a path to a possible proof that not all toroidal graphs are transducible from planar graphs. Our characterization can be extended to any fixed surface instead of the plane. The result is based on a very recent characterization of weakly sparse FO transductions of classes of bounded expansion by [Gajarsk\'y, G{\l}adkowski, Jedelsk\'y, Pilipczuk and Toru\'nczyk, arXiv:2505.15655].

Authors: Sandeep Sen

We formalize a new paradigm for optimality of algorithms, that generalizes worst-case optimality based only on input-size to problem-dependent parameters including implicit ones. We re-visit some existing sorting algorithms from this perspective, and also present a novel measure of sortedness that leads to an optimal algorithm based on partition sort. This paradigm of measuring efficiency of algorithms looks promising for further interesting applications beyond the existing ones.

Authors: Matthew Ding, Robbie King, Bobak T. Kiani, Eric R. Anschuetz

Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev--Ye--Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings--O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to \emph{not} persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability $1-p$, where $p=\Theta(1/n^3)$ and $n$ is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification. In this work we initiate the study of the sparse SYK model where $p \in [\Theta(1/n^3),1]$. We show there indeed exists a certain robustness of sparsification. First, we prove that the quantum algorithm of Hastings--O'Donnell for $p=1$ still achieves a constant-factor approximation to the ground energy when $p\geq\Omega(\log n/n)$. Additionally, we prove that with high probability, Gaussian states cannot achieve better than a $O(\sqrt{\log n/pn})$-factor approximation to the true ground state energy of sparse SYK. This is done through a general classical circuit complexity lower-bound of $\Omega(pn^3)$ for any quantum state achieving a constant-factor approximation. Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states when $p \geq \Omega(\log n/n)$, extending the analogous $p=1$ result of Hastings--O'Donnell.

Authors: Andrej Brodnik, Bengt J. Nilsson, Gordana Vujović

The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items' sizes in each bin is at least~1. Boyar~{\em et~al}.\@~\cite{boyar2021} present a strategy that with $O(\log \log n)$ bits of advice, where $n$ is the length of the input sequence, achieves a competitive ratio of $8/15\approx0.5333\ldots$. We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of~$135/242\approx0.5578\ldots$, still using $O(\log \log n)$ bits of advice.

Authors: Mujin Choi, Claire Hilaire, Martin Milanič, Sebastian Wiederrecht

We study a conjecture due to Dallard, Krnc, Kwon, Milani\v{c}, Munaro, \v{S}torgel, and Wiederrecht stating that for any positive integer $d$ and any planar graph $H$, the class of all $K_{1,d}$-free graphs without $H$ as an induced minor has bounded tree-independence number. A $k$-wheel is the graph obtained from a cycle of length $k$ by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when $H$ is a $k$-wheel for any $k\geq 3$. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important $\mathsf{NP}$-hard problems such as Maximum Independent Set are tractable on $K_{1,d}$-free graphs without large induced wheel minors. Moreover, for fixed $d$ and $k$, we provide a polynomial-time algorithm that, given a $K_{1,d}$-free graph $G$ as input, finds an induced minor model of a $k$-wheel in $G$ if one exists.

Authors: Junfeng Liu, Jiarui Ye, Mengshi Chen, Meng Li, Siqiang Luo

LSM-tree-based data stores are widely used in industry due to their exceptional performance. However, as data volumes grow, efficiently querying large-scale databases becomes increasingly challenging. To address this, recent studies attempted to integrate learned indexes into LSM-trees to enhance lookup performance, which has demonstrated promising improvements. Despite this, only a limited range of learned index types has been considered, and the strengths and weaknesses of different learned indexes remain unclear, making them difficult for practical use. To fill this gap, we provide a comprehensive and systematic benchmark to pursue an in-depth understanding of learned indexes in LSM-tree systems. In this work, we summarize the workflow of 8 existing learned indexes and analyze the associated theoretical cost. We also identify several key factors that significantly influence the performance of learned indexes and conclude them with a novel configuration space, including various index types, boundary positions, and granularity. Moreover, we implement different learned index designs on a unified platform to evaluate across various configurations. Surprisingly, our experiments reveal several unexpected insights, such as the marginal lookup enhancement when allocating a large memory budget to learned indexes and modest retraining overhead of learned indexes. Besides, we also offer practical guidelines to help developers intelligently select and tune learned indexes for custom use cases.

Authors: Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu

The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $\Theta(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $\Omega(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity.

Authors: Tomás González, Giulia Fanti, Aaditya Ramdas

Private Evolution (PE) is a promising training-free method for differentially private (DP) synthetic data generation. While it achieves strong performance in some domains (e.g., images and text), its behavior in others (e.g., tabular data) is less consistent. To date, the only theoretical analysis of the convergence of PE depends on unrealistic assumptions about both the algorithm's behavior and the structure of the sensitive dataset. In this work, we develop a new theoretical framework to explain PE's practical behavior and identify sufficient conditions for its convergence. For $d$-dimensional sensitive datasets with $n$ data points from a bounded domain, we prove that PE produces an $(\epsilon, \delta)$-DP synthetic dataset with expected 1-Wasserstein distance of order $\tilde{O}(d(n\epsilon)^{-1/d})$ from the original, establishing worst-case convergence of the algorithm as $n \to \infty$. Our analysis extends to general Banach spaces as well. We also connect PE to the Private Signed Measure Mechanism, a method for DP synthetic data generation that has thus far not seen much practical adoption. We demonstrate the practical relevance of our theoretical findings in simulations.

Authors: Davide Cenzato, Francisco Olivares, Nicola Prezza

Suffixient sets are a novel prefix array (PA) compression technique based on subsampling PA (rather than compressing the entire array like previous techniques used to do): by storing very few entries of PA (in fact, a compressed number of entries), one can prove that pattern matching via binary search is still possible provided that random access is available on the text. In this paper, we tackle the problems of determining whether a given subset of text positions is (1) a suffixient set or (2) a suffixient set of minimum cardinality. We provide linear-time algorithms solving these problems.

Authors: Florian Adriaens, Nikolaj Tatti

Diversity maximization problem is a well-studied problem where the goal is to find $k$ diverse items. Fair diversity maximization aims to select a diverse subset of $k$ items from a large dataset, while requiring that each group of items be well represented in the output. More formally, given a set of items with labels, our goal is to find $k$ items that maximize the minimum pairwise distance in the set, while maintaining that each label is represented within some budget. In many cases, one is only interested in selecting a handful (say a constant) number of items from each group. In such scenario we show that a randomized algorithm based on padded decompositions improves the state-of-the-art approximation ratio to $\sqrt{\log(m)}/(3m)$, where $m$ is the number of labels. The algorithms work in several stages: ($i$) a preprocessing pruning which ensures that points with the same label are far away from each other, ($ii$) a decomposition phase, where points are randomly placed in clusters such that there is a feasible solution with maximum one point per cluster and that any feasible solution will be diverse, $(iii)$ assignment phase, where clusters are assigned to labels, and a representative point with the corresponding label is selected from each cluster. We experimentally verify the effectiveness of our algorithm on large datasets.

The replication crisis in psychology is over. Or at least that’s what I read in this news article in Science yesterday. Paul Bogdan, a neuroscientist at Duke, scanned 240,000 papers in psychology and found that weak p-values had decreased from 32% to 26% in papers published between 2004 and 2024. Let’s break out the champagne, everyone. I don’t want to dump on Paul, who’s caught up in a viral whirlwind here. I’m just surprised by the fervor of the science reform community’s excitement that made this paper go viral in the first place.

Joe Bak Coleman has been on a tear about the overreaction on Bluesky. I recommend his timeline for exasperated puzzlement about what on earth the results of this paper mean. But it should be obvious that the problem in psychology was not that 6% of the papers had p-values in a bad range. Shouldn’t we expect 0% of the results to be weak if we were all good scientists? We’re going to settle for 26%?

Peter Ellis wrote a great blog post about what “weak p-values” could even mean for those of us who like to get into the statistical mud. He points out, correctly, that modeling the proper distribution of p-values requires massive, unjustifiable, unverifiable assumptions. He shows that under standard models where effects, interventions, and outcomes are chosen at random in trials (random trials with controls, if you will), the distribution of p-values is extremely sensitive to how you model the population of potential experiments.

Studying the replication crisis with more statistical modeling will never bring us any resolution.1 To do studies of what we should “expect” to see, one has to assume some probabilistic model for generating science. These models are woefully inadequate for capturing anything about the social dynamics of how science works. They necessarily ignore the fact that people writing scientific papers know they have to run a null hypothesis significance test to get their paper published. This is Goodhart’s Law screaming at you loudly: p-values are a regulatory mechanism, not a measurement device.

It doesn’t usually get much clearer than this. We only talk about p-values at all because they are a bar that must be cleared to get some study approved, be it a drug trial, an A/B tested piece of code, or a scientific paper. Studying the distribution of p-values around 0.05 is studying Milton Friedman’s thermostat.

When you blog for long enough, you find yourself saying the same thing more than once. I can see why Matt Levine is so successful. He says the same five things every week, but the people doing money stuff keep doing the same outrageous things, so it never gets old. In the spirit of everything being securities fraud, Bogdan’s paper and its reaction are hitting multiple buttons at once for me: Observational studies are never-dispositive stories about correlations, significance testing is a regulatory device, p-values are correlation coefficients in a trench coat.

I’ve said that last one before a dozen times on here, but I think I need to keep saying it.

In 99.999% of the cases where the term is used, p-value is a goofy way of summarizing the correlation between an intervention and its outcome. Here’s how you do it. First, compute the Pearson correlation coefficient between the treatment and outcome. This is a number between -1 and 1. Multiply this number by the square root of the sample size. If this scaled correlation coefficient, call it the score, has magnitude larger than 2, we say the p-value is less than 0.05. If the score is larger than 2.6, we say the p-value is less than 0.01. If the score is larger than 3, we say the p-value is less than 0.0025. And if the score is larger than 4.4, we say the p-value is less than 0.00001.

I could go on. You compute the scaled correlation coefficient score:

score = correlation_coefficient(treatment, outcome)*np.sqrt(sample_size)

And look this score up in a table to find your p-value.

I’m belaboring this because it’s so silly to collapse all of the information of your experiment into this one number and assume it tells you anything. It’s also silly because blindly scaling the coefficient by the sample size means you can lower your p-values just by moving away from in-person experiments to online Mechanical Turk experiments.

It’s also obviously silly to set this score as a target for all experiments. The treatment-outcome correlation can mean completely different things in different contexts. Correlations need stories! Trying to pretend you can do science without the stories isn’t going to advance anything.

Because we can tell ourselves all sorts of stories about what small and large effects might look like here. How correlations should scale depends on the problem you are studying. If you are conducting a vaccine study, you expect almost no one to actually contract the disease. Therefore, the correlation between the treatment and outcome will be nearly zero, as the outcome “not sick” is almost always positive.

For example, of the 43 thousand participants in the Pfizer COVID vaccine trial, only ten developed “severe COVID.” Nine participants were in the control group, and one was in the treatment group. That seems to be a big effect! The correlation between the treatment and severe-COVID outcome was 0.01. This value is small because the severe COVID condition is exceptionally rare. Scaled by the root sample size gives a score of 2.5. Looking it up in a table, the p-value is 0.012.

Now suppose you are studying some small effect in an A/B test. You think that some new widget will increase everyone’s time on a website by 30 seconds a week. The correlation between your widget and time on site is close to zero because your defined outcome is inherently noisy, and your population of website addicts is very heterogeneous. But you’ll get your code shipped if the correlation between time on the website and your widget is large enough. So you run the test on a million people and cross your fingers.

I mean, I get it. We need some rules for pushing code and shipping drugs. We can move p-value thresholds around, and people will adjust their practices to meet these thresholds. But thinking that you can study the statistics of these scores and infer something about the validity of knowledge is a fool’s errand. You can make a strong case that drug discovery needs formal rules to promote patient safety. But logic devolves into absurdity pretty quickly if you try to make the same case for scientific expertise.

Subscribe now

By Ben Recht

A week ago I attended LessOnline, a rationalist blogging conference featuring many people I’ve known for years—Scott Alexander, Eliezer Yudkowsky, Zvi Mowshowitz, Sarah Constantin, Carl Feynman—as well as people I’ve known only online and was delighted to meet in person, like Joe Carlsmith and Jacob Falkovich and Daniel Reeves. The conference was at Lighthaven, a bewildering maze of passageways, meeting-rooms, sleeping quarters, gardens, and vines off Telegraph Avenue in Berkeley, which has recently emerged as the nerd Shangri-La, or Galt’s Gulch, or Shire, or whatever. I did two events at this year’s LessOnline: a conversation with Nate Soares about the Orthogonality Thesis, and an ask-me-anything session about quantum computing and theoretical computer science (no new ground there for regular consumers of my content).

What I’ll remember most from LessOnline is not the sessions, mine or others’, but the unending conversation among hundreds of people all over the grounds, which took place in parallel with the sessions and before and after them, from morning till night (and through the night, apparently, though I’ve gotten too old for that). It felt like a single conversational archipelago, the largest in which I’ve ever taken part, and the conference’s real point. (Attendees were exhorted, in the opening session, to skip as many sessions as possible in favor of intense small-group conversations—not only because it was better but also because the session rooms were too small.)

Within the conversational blob, just making my way from one building to another could take hours. My mean free path was approximately five feet, before someone would notice my nametag and stop me with a question. Here was my favorite opener:

“You’re Scott Aaronson?! The quantum physicist who’s always getting into arguments on the Internet, and who’s essentially always right, but who sustains an unreasonable amount of psychic damage in the process?”

“Yes,” I replied, not bothering to correct the “physicist” part.

One night, I walked up to Scott Alexander, who sitting on the ground, with his large bald head and a blanket he was using as a robe, resembled a monk. “Are you enjoying yourself?” he asked.

I replied, “you know, after all these years of being coy about it, I think I’m finally ready to become a Rationalist. Is there, like, an initiation ritual or something?”

Scott said, “Oh, you were already initiated a decade ago; you just didn’t realize it at the time.” Then he corrected himself: “two decades ago.”

The first thing I did, after coming out as a Rationalist, was to get into a heated argument with Other Scott A., Joe Carlsmith, and other fellow-Rationalists about the ideas I set out twelve years ago in my Ghost in the Quantum Turing Machine essay. Briefly, my argument was that the irreversibility and ephemerality of biological life, which contrasts with the copyability, rewindability, etc. of programs running on digital computers, and which can ultimately be traced back to microscopic details of the universe’s initial state, subject to the No-Cloning Theorem of quantum mechanics, which then get chaotically amplified during brain activity … might be a clue to a deeper layer of the world, one that we understand about as well as the ancient Greeks understood Newtonian physics, but which is the layer where mysteries like free will and consciousness will ultimately need to be addressed.

I got into this argument partly because it came up, but partly also because this seemed like the biggest conflict between my beliefs and the consensus of my fellow Rationalists. Maybe part of me wanted to demonstrate that my intellectual independence remained intact—sort of like a newspaper that gets bought out by a tycoon, and then immediately runs an investigation into the tycoon’s corruption, as well as his diaper fetish, just to prove it can.

The funny thing, though, is that all my beliefs are the same as they were before. I’m still a computer scientist, an academic, a straight-ticket Democratic voter, a liberal Zionist, a Jew, etc. (all identities, incidentally, well-enough represented at LessOnline that I don’t even think I was the unique attendee in the intersection of them all).

Given how much I resonate with what the Rationalists are trying to do, why did it take me so long to identify as one?

Firstly, while 15 years ago I shared the Rationalists’ interests, sensibility, and outlook, and their stances on most issues, I also found them bizarrely, inexplicably obsessed with the question of whether AI would soon become superhumanly powerful and change the basic conditions of life on earth, and with how to make the AI transition go well. Why that, as opposed to all the other sci-fi scenarios one could worry about, not to mention all the nearer-term risks to humanity?

Suffice it to say that empirical developments have since caused me to withdraw my objection. Sometimes weird people are weird merely because they see the future sooner than others. Indeed, it seems to me that the biggest thing the Rationalists got wrong about AI was to underestimate how soon the revolution would happen, and to overestimate how many new ideas would be needed for it (mostly, as we now know, it just took lots more compute and training data). Now that I, too, spend some of my time working on AI alignment, I was able to use LessOnline in part for research meetings with colleagues.

A second reason I didn’t identify with the Rationalists was cultural: they were, and are, centrally a bunch of twentysomethings who “work” at an ever-changing list of Berkeley- and San-Francisco-based “orgs” of their own invention, and who live in group houses where they explore their exotic sexualities, gender identities, and fetishes, sometimes with the aid of psychedelics. I, by contrast, am a straight, monogamous, middle-aged tenured professor, married to another such professor and raising two kids who go to normal schools. Hanging out with the Rationalists always makes me feel older and younger at the same time.

So what changed? For one thing, with the march of time, a significant fraction of Rationalists now have marriages, children, or both—indeed, a highlight of LessOnline was the many adorable toddlers running around the Lighthaven campus. Rationalists are successfully reproducing! Some because of explicit pronatalist ideology, or because they were persuaded by Bryan Caplan’s arguments in Selfish Reasons to Have More Kids. But others simply because of the same impulses that led their ancestors to do the same for eons. And perhaps because, like the Mormons or Amish or Orthodox Jews, but unlike typical secular urbanites, the Rationalists believe in something. For all their fears around AI, they don’t act doomy, but buzz with ideas about how to build a better world for the next generation.

At a LessOnline parenting session, hosted by Julia Wise, I was surrounded by parents who worry about the same things I do: how do we raise our kids to be independent and agentic yet socialized and reasonably well-behaved, technologically savvy yet not droolingly addicted to iPad games? What schooling options will let them accelerate in math, save them from the crushing monotony that we experienced? How much of our own lives should we sacrifice on the altar of our kids’ “enrichment,” versus trusting Judith Rich Harris that such efforts quickly hit a point of diminishing returns?

A third reason I didn’t identify with the Rationalists was, frankly, that they gave off some (not all) of the vibes of a cult, with Eliezer as guru. Eliezer writes in parables and koans. He teaches that the fate of life on earth hangs in the balance, that the select few who understand the stakes have the terrible burden of steering the future. Taking what Rationalists call the “outside view,” how good is the track record for this sort of thing?

OK, but what did I actually see at Lighthaven? I saw something that seemed to resemble a cult only insofar as the Beatniks, the Bloomsbury Group, the early Royal Society, or any other community that believed in something did. When Eliezer himself—the bearded, cap-wearing Moses who led the nerds from bondage to their Promised Land in Berkeley—showed up, he was argued with like anyone else. Eliezer has in any case largely passed his staff to a new generation: Nate Soares and Zvi Mowshowitz have found new and, in various ways, better ways of talking about AI risk; Scott Alexander has for the last decade written the blog that’s the community’s intellectual center; figures from Kelsey Piper to Jacob Falkovich to Aella have taken Rationalism in new directions, from mainstream political engagement to the … err … statistical analysis of orgies.

I’ll say this, though, on the naysayers’ side: it’s really hard to make dancing to AI-generated pop songs about Bayes’ theorem and Tarski’s definition of truth not feel cringe, as I can now attest from experience.

The cult thing brings me to the deepest reason I hesitated for so long to identify as a Rationalist: namely, I was scared that if I did, people whose approval I craved (including my academic colleagues, but also just randos on the Internet) would sneer at me. For years, I searched of some way of explaining this community’s appeal so reasonable that it would silence the sneers.

It took years of psychological struggle, and (frankly) solidifying my own place in the world, to follow the true path, which of course is not to give a shit what some haters think of my life choices. Consider: five years ago, it felt obvious to me that the entire Rationalist community might be about to implode, under existential threat from Cade Metz’s New York Times article, as well as RationalWiki and SneerClub and all the others laughing at the Rationalists and accusing them of every evil. Yet last week at LessOnline, I saw a community that’s never been thriving more, with a beautiful real-world campus, excellent writers on every topic who felt like this was the place to be, and even a crop of kids. How many of the sneerers are living such fulfilled lives? To judge from their own angry, depressed self-disclosures, probably not many.

But are the sneerers right that, even if the Rationalists are enjoying their own lives, they’re making other people’s lives miserable? Are they closet far-right monarchists, like Curtis Yarvin? I liked how The New Yorker put it in its recent, long and (to my mind) devastating profile of Yarvin:

The most generous engagement with Yarvin’s ideas has come from bloggers associated with the rationalist movement, which prides itself on weighing evidence for even seemingly far-fetched claims. Their formidable patience, however, has also worn thin. “He never addressed me as an equal, only as a brainwashed person,” Scott Aaronson, an eminent computer scientist, said of their conversations. “He seemed to think that if he just gave me one more reading assignment about happy slaves singing or one more monologue about F.D.R., I’d finally see the light.”

The closest to right-wing politics that I witnessed at LessOnline was a session, with Kelsey Piper and current and former congressional staffers, about the prospects for moderate Democrats to articulate a moderate, pro-abundance agenda that would resonate with the public and finally defeat MAGA.

But surely the Rationalists are incels, bitter that they can’t get laid? Again, the closest I saw was a session where Jacob Falkovich helped a standing-room-only crowd of mostly male nerds confront their fears around dating and understand women better, with Rationalist women eagerly volunteering to answer questions about their perspective. Gross, right? (Also, for those already in relationships, Eliezer’s primary consort and former couples therapist Gretta Duleba did a session on relationship conflict.)

So, yes, when it comes to the Rationalists, I’m going to believe my own lying eyes over the charges of the sneerers. The sneerers can even say about me, in their favorite formulation, that I’ve “gone mask off,” confirmed the horrible things they’ve always suspected. Yes, the mask is off—and beneath the mask is the same person I always was, who has an inordinate fondness for the Busy Beaver function and the complexity class BQP/qpoly, and who uses too many filler words and moves his hands too much, and who strongly supports the Enlightenment, and who once feared that his best shot at happiness in life would be to earn women’s pity rather than their contempt. Incorrectly, as I’m glad to report. From my nebbishy nadir to the present, a central thing that’s changed is that, from my family to my academic colleagues to the Rationalist community to my blog readers, I finally found some people who want what I have to sell.

---

Unrelated Announcements:

My replies to comments on this post might be light, as I’ll be accompanying my daughter on a school trip to the Galapagos Islands!

A few weeks ago, I was “ambushed” into leading a session on philosophy and theoretical computer science at UT Austin. (I.e., asked to show up for the session, but thought I’d just be a participant rather than the main event.) The session was then recorded and placed on YouTube—and surprisingly, given the circumstances, some people seemed to like it!

Friend-of-the-blog Alon Rosen has asked me to announce a call for nominations for a new theoretical computer science prize, in memory of my former professor (and fellow TCS blogger) Luca Trevisan, who was lost to the world too soon.

And one more: Mahdi Cheraghchi has asked me to announce the STOC’2025 online poster session, registration deadline June 12; see here for more. Incidentally, I’ll be at STOC in Prague to give a plenary on quantum algorithms; I look forward to meeting any readers who are there!

By Scott

Authors: Ari Biswas, Rajko Nenadov

This work studies the complexity of refuting the existence of a perfect matching in spectral expanders with an odd number of vertices, in the Polynomial Calculus (PC) and Sum of Squares (SoS) proof system. Austrin and Risse [SODA, 2021] showed that refuting perfect matchings in sparse $d$-regular \emph{random} graphs, in the above proof systems, with high probability requires proofs with degree $\Omega(n/\log n)$. We extend their result by showing the same lower bound holds for \emph{all} $d$-regular graphs with a mild spectral gap.

Authors: Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d'Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Jukka Suomela

In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm $\mathcal{A}$ that finds an $\alpha$-approximation of some linear optimization problem $\Pi$ in $T$ communication rounds, we can construct a classical, deterministic LOCAL algorithm $\mathcal{A}'$ that finds an $\alpha$-approximation of $\Pi$ in $T$ rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. Second, using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL also to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.

Authors: Ricardo Rivera Cardoso, Alex Meiburg, Daniel Nagaj

Previously, all known variants of the Quantum Satisfiability (QSAT) problem, i.e. deciding whether a $k$-local ($k$-body) Hamiltonian is frustration-free, could be classified as being either in $\mathsf{P}$; or complete for $\mathsf{NP}$, $\mathsf{MA}$, or $\mathsf{QMA_1}$. Here, we demonstrate new qubit variants of this problem that are complete for $\mathsf{BQP_1}$, $\mathsf{coRP}$, $\mathsf{QCMA}$, $\mathsf{PI(coRP,NP)}$, $\mathsf{PI(BQP_1,NP)}$, $\mathsf{PI(BQP_1,MA)}$, $\mathsf{SoPU(coRP,NP)}$, $\mathsf{SoPU(BQP_1,NP)}$, and $\mathsf{SoPU(BQP_1,MA)}$. Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer's dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial $\mathsf{BQP_1}$-complete problem. We first prove there are qudit QSAT problems that are complete for $\mathsf{BQP_1}$, $\mathsf{coRP}$, and $\mathsf{QCMA}$ by re-defining elements of the circuit-to-Hamiltonian transformation. We then show that any QCSP can be reduced to a problem in qubits while maintaining the same complexity - something believed not to be possible classically. The remaining six problems are obtained by considering "sums" and "products" of the first seven QSAT problems. Before this work, the QSAT problems generated in this way resulted in complete problems for $\mathsf{PI}$ and $\mathsf{SoPU}$ classes that were trivially equal to other known classes. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for the first three classes, we note that his constructions are flawed. Here, we rework them and obtain improvements on the required qudit dimensionality.

Authors: Kim Calabrese, David Doty, Mina Latifi

We initiate the study of rate-constant-independent computation of Boolean predicates and numerical functions in the continuous model of chemical reaction networks (CRNs), which model the amount of a chemical species as a nonnegative, real-valued *concentration*. Real-valued numerical functions have previously been studied, finding that exactly the continuous, piecewise rational linear functions $f: \mathbb{R}_{> 0}^k \to \mathbb{R}_{> 0}$ can be computed *stably*, a.k.a., *rate-independently*, meaning that the CRN gets the answer correct no matter the rate at which reactions occur. We show that, contrary to functions, continuous CRNs are severely limited in the Boolean predicates they can stably decide, reporting an answer based only on which inputs are 0 or positive. This limitation motivates a slightly relaxed notion of rate-independent computation in CRNs that we call *robust computation*. The standard mass-action rate model is used, in which each reaction is assigned a rate equal to the product of its reactant concentrations and its rate constant. The computation is correct in this model if it converges to the correct output for any positive choice of rate constants. This adversary is weaker than the stable computation adversary, the latter being able to run reactions at non-mass-action rates. We show that CRNs can robustly decide every finite Boolean combination of *threshold predicates*: those predicates defined by taking a rational weighted sum of the inputs $\mathbf{x} \in \mathbb{R}^k_{\ge 0}$ and comparing to a constant, answering the question ``Is $\sum_{i=1}^k w_i \cdot \mathbf{x}(i) > h$?'', for rational weights $w_i$ and real threshold $h$. Turning to function computation, we show that CRNs can robustly compute any piecewise affine function with rational coefficients, where threshold predicates determine which affine piece to evaluate for a given input.

Authors: Mark de Berg, Sergio Cabello

We prove that the single-source shortest-path problem on disk graphs can be solved in $O(n\log n)$ time, and that it can be solved on intersection graphs of fat triangles in $O(n\log^2 n)$ time.

Authors: Therese Biedl, Philipp Kindermann, Jonathan Klawitter

A rectangular dual of a plane graph $G$ is a contact representation of $G$ by interior-disjoint rectangles such that (i) no four rectangles share a point, and (ii) the union of all rectangles is a rectangle. In this paper, we study rectangular duals of graphs that are embedded in surfaces other than the plane. In particular, we fully characterize when a graph embedded on a cylinder admits a cylindrical rectangular dual. For graphs embedded on the flat torus, we can test whether the graph has a toroidal rectangular dual if we are additionally given a \textit{regular edge labeling}, i.e. a combinatorial description of rectangle adjacencies. Furthermore we can test whether there exists a toroidal rectangular dual that respects the embedding and that resides on a flat torus for which the sides are axis-aligned. Testing and constructing the rectangular dual, if applicable, can be done efficiently.

Authors: Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo Silveira, Tyler Tuttle

Let $ \Pi(n) $ be the largest number such that for every set $ S $ of $ n $ points in a polygon~$ P $, there always exist two points $ x, y \in S $, where every geodesic disk containing $ x $ and $ y $ contains $ \Pi(n) $ points of~$ S $. We establish upper and lower bounds for $ \Pi(n)$, and show that $ \left\lceil \frac{n}{5}\right\rceil+1 \leq \Pi(n) \leq \left\lceil \frac{n}{4} \right\rceil +1 $. We also show that there always exist two points $x, y\in S$ such that every geodesic disk with $x$ and $y$ on its boundary contains at least $ \frac{n}{3+\sqrt{5}} \approx \left\lceil \frac{n}{5.2} \right\rceil$ points both inside and outside the disk. For the special case where the points of $ S $ are restricted to be the vertices of a geodesically convex polygon we give a tight bound of $\left\lceil \frac{n}{3} \right\rceil + 1$. We provide the same tight bound when we only consider geodesic disks having $ x $ and $ y $ as diametral endpoints. We give upper and lower bounds of $\left\lceil \frac{n}{5} \right\rceil + 1 $ and $\frac{n}{6+\sqrt{26}} \approx \left\lceil \frac{n}{11.1} \right\rceil$, respectively, for the two-colored version of the problem. Finally, for the two-colored variant we show that there always exist two points $x, y\in S$ where $x$ and $y$ have different colors and every geodesic disk with $x$ and $y$ on its boundary contains at least $\lceil \frac{n}{11.3}\rceil+1$ points both inside and outside the disk.

Authors: Max Bannach, Erik D. Demaine, Timothy Gomez, Markus Hecher

The canonical class in the realm of counting complexity is #P. It is well known that the problem of counting the models of a propositional formula in disjunctive normal form (#DNF) is complete for #P under Turing reductions. On the other hand, #DNF $\in$ spanL and spanL $\not\subseteq$ #P unless NL = NP. Hence, the class of functions logspace-reducible to #DNF is a strict subset of #P under plausible complexity-theoretic assumptions. By contrast, we show that two calls to a (restricted) #2DNF oracle suffice to capture gapP, namely, that the logspace many-one closure of the subtraction between the results of two #2DNF calls is gapP. Because #P $\not\subseteq$ gapP, #P is strictly contained between one and two #2DNF oracle calls. Surprisingly, the propositional formulas needed in both calls are linear-time computable, and the reduction preserves interesting structural as well as symmetry properties, leading to algorithmic applications. We show that a single subtraction suffices to compensate for the absence of negation while still capturing gapP, i.e., our results carry over to the monotone fragments of #2SAT and #2DNF. Since our reduction is linear-time, it preserves sparsity and, as a consequence we obtain a sparsification lemma for both #2SAT and #2DNF. This has only been known for kSAT with k $\geq$ 3 and respective counting versions. We further show that both #2DNF calls can be combined into a single call if we allow a little postprocessing (computable by AC0- or TC0-circuits). Consequently, we derive refined versions of Toda's Theorem: PH $\subseteq$ [#MON2SAT]$^{log}_{TC0}$ = [#MON2DNF]$^{log}_{TC0}$ and PH $\subseteq$ [#IMPL2SAT]$^{log}_{AC0}$. Our route to these results is via structure-aware reductions that preserve parameters like treewidth up to an additive overhead. The absence of multiplicative overhead indeed yields parameterized SETH-tight lower bounds.

Authors: George Orfanides, Tim Hoheisel, Marwa El Halabi

Submodular functions, defined on continuous or discrete domains, arise in numerous applications. We study the minimization of the difference of two submodular (DS) functions, over both domains, extending prior work restricted to set functions. We show that all functions on discrete domains and all smooth functions on continuous domains are DS. For discrete domains, we observe that DS minimization is equivalent to minimizing the difference of two convex (DC) functions, as in the set function case. We propose a novel variant of the DC Algorithm (DCA) and apply it to the resulting DC Program, obtaining comparable theoretical guarantees as in the set function case. The algorithm can be applied to continuous domains via discretization. Experiments demonstrate that our method outperforms baselines in integer compressive sensing and integer least squares.

Authors: Ziv Oznovich, Ben Lee Volk

We give a deterministic algorithm that, given a composite number $N$ and a target order $D \ge N^{1/6}$, runs in time $D^{1/2+o(1)}$ and finds either an element $a \in \mathbb{Z}_N^*$ of multiplicative order at least $D$, or a nontrivial factor of $N$. Our algorithm improves upon an algorithm of Hittmeir (arXiv:1608.08766), who designed a similar algorithm under the stronger assumption $D \ge N^{2/5}$. Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (arXiv:2006.16729, arXiv:2010.05450, arXiv:2105.11105). When $N$ is assumed to have an $r$-power divisor with $r\ge 2$, our algorithm provides the same guarantees assuming $D \ge N^{1/6r}$.

Authors: Honghao Lin, Hoai-An Nguyen, David P. Woodruff

We present space-efficient linear sketches for estimating trimmed statistics of an $n$-dimensional frequency vector $x$, e.g., the sum of $p$-th powers of the largest $k$ frequencies (i.e., entries) in absolute value, or the $k$-trimmed vector, which excludes the top and bottom $k$ frequencies. This is called the $F_p$ moment of the trimmed vector. Trimmed measures are used in robust estimation, as seen in the R programming language's `trim.var' function and the `trim' parameter in the mean function. Linear sketches improve time and memory efficiency and are applicable to streaming and distributed settings. We initiate the study of sketching these statistics and give a new condition for capturing their space complexity. When $k \ge n/poly\log n$, we give a linear sketch using $poly(1/\varepsilon, \log n)$ space which provides a $(1 \pm \varepsilon)$ approximation to the top-$k$ $F_p$ moment for $p \in [0,2]$. For general $k$, we give a sketch with the same guarantees under a condition relating the $k$-th largest frequency to the tail mass, and show this condition is necessary. For the $k$-trimmed version, our sketch achieves optimal error guarantees under the same condition. We extend our methods to $p > 2$ and also address related problems such as computing the $F_p$ moment of frequencies above a threshold, finding the largest $k$ such that the $F_p$ moment of the top $k$ exceeds $k^{p+1}$, and the $F_p$ moment of the top $k$ frequencies such that each entry is at least $k$. Notably, our algorithm for this third application improves upon the space bounds of the algorithm of Govindan, Monemizadeh, and Muthukrishnan (PODS '17) for computing the $h$-index. We show empirically that our top $k$ algorithm uses much less space compared to Count-Sketch while achieving the same error.

Authors: L. Sunil Chandran, Rishikesh Gajjala, Kuldeep S. Meel

Model counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in probabilistic reasoning, network reliability, statistical physics, and formal verification. A common approach for solving weighted model counting is to reduce it to unweighted model counting, which raises an important question: {\em What is the minimum number of terms (or clauses) required to construct a DNF (or CNF) formula with exactly $k$ satisfying assignments?} In this paper, we establish both upper and lower bounds on this question. We prove that for any natural number $k$, one can construct a monotone DNF formula with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k}\log\log k)$ terms. This construction represents the first $o(\log k)$ upper bound for this problem. We complement this result by showing that there exist infinitely many values of $k$ for which any DNF or CNF representation requires at least $\Omega(\log\log k)$ terms or clauses. These results have significant implications for the efficiency of model counting algorithms based on formula transformations.