\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage[titles]{tocloft}
\setlength{\cftbeforesecskip}{0.25em}
\setlength{\cftbeforetoctitleskip}{0pt}
\setlength{\cftaftertoctitleskip}{0.8em}
\usepackage{enumitem}
\usepackage{booktabs}
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
\usepackage{graphicx}
\usepackage{xcolor}
\definecolor{citewarm}{HTML}{B5403B}
\definecolor{refcool}{HTML}{2C5AA0}
\definecolor{easy}{HTML}{1B9E77}
\definecolor{open}{HTML}{9A9A9A}
\definecolor{hard}{HTML}{D95F02}
\usepackage{tikz}
\usetikzlibrary{positioning,decorations.pathreplacing,calc}
\usepackage[colorlinks=true,linkcolor=refcool,citecolor=citewarm,urlcolor=refcool]{hyperref}
\usepackage[capitalise,nameinlink]{cleveref}
\usepackage{environ}

\setlist{itemsep=1pt,parsep=0pt,topsep=3pt,partopsep=0pt}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Imported Theorem}
\newtheorem{headline}{Theorem}
\renewcommand{\theheadline}{\Alph{headline}}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{hypothesis}[theorem]{Hypothesis}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Open Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\crefname{fact}{Imported Theorem}{Imported Theorems}

% ---------- restatable results: \begin{restatable}[title]{env}{name} ... \end{restatable},
% restated later by \name* with the same number and without labels ----------
\makeatletter
\theoremstyle{plain}
\newcommand{\rst@thename}{}
\newtheorem*{rst@plain}{\rst@thename}
\def\rst@name@theorem{Theorem}
\def\rst@name@lemma{Lemma}
\def\rst@name@corollary{Corollary}
\def\rst@name@proposition{Proposition}
\NewEnviron{restatable}[3][]{%
  \def\rst@tmptitle{#1}%
  \ifx\rst@tmptitle\@empty\begin{#2}\BODY\end{#2}\else\begin{#2}[#1]\BODY\end{#2}\fi
  \expandafter\xdef\csname rst@num@#3\endcsname{\csname the#2\endcsname}%
  \expandafter\global\expandafter\let\csname rst@body@#3\endcsname\BODY
  \expandafter\gdef\csname rst@title@#3\endcsname{#1}%
  \expandafter\xdef\csname rst@env@#3\endcsname{#2}%
  \expandafter\gdef\csname #3\endcsname{\@ifstar{\rst@do{#3}}{\rst@do{#3}}}}
\newcommand{\rst@do}[1]{%
  \begingroup
  \edef\rst@tmpenv{\csname rst@env@#1\endcsname}%
  \edef\rst@thename{\csname rst@name@\rst@tmpenv\endcsname\space\csname rst@num@#1\endcsname}%
  \renewcommand{\label}[2][]{}%
  \expandafter\let\expandafter\rst@b\csname rst@body@#1\endcsname
  \expandafter\let\expandafter\rst@t\csname rst@title@#1\endcsname
  \ifx\rst@t\@empty\begin{rst@plain}\rst@b\end{rst@plain}%
  \else\begin{rst@plain}[\rst@t]\rst@b\end{rst@plain}\fi
  \endgroup}
\makeatother
\crefname{hypothesis}{Hypothesis}{Hypotheses}
\crefname{problem}{Open Problem}{Open Problems}
\crefname{claim}{Claim}{Claims}
\crefname{headline}{Theorem}{Theorems}

% ---------- Lamport-style structured proofs (L. Lamport, "How to Write a Proof", 1995) ----------
\newcommand{\pflab}[2]{\ensuremath{\langle#1\rangle}#2}
\newenvironment{steps}{\begin{list}{}{%
    \setlength{\leftmargin}{2.1em}\setlength{\labelwidth}{1.9em}\setlength{\labelsep}{0.2em}%
    \setlength{\itemsep}{2pt}\setlength{\parsep}{1pt}\setlength{\topsep}{2pt}\setlength{\partopsep}{0pt}%
    \renewcommand{\makelabel}[1]{##1\hfil}}}{\end{list}}
\newcommand{\step}[2]{\item[\pflab{#1}{#2}.]}
\newcommand{\qedstep}[2]{\item[\pflab{#1}{#2}.]\textsc{q.e.d.}}
\newcommand{\pf}{\par\textsc{Proof:}\ }
\newcommand{\sref}[2]{\pflab{#1}{#2}}
\newcommand{\xsref}[2]{\pflab{#1}{#2}}
\newcommand{\Assume}{\textsc{Assume:}\ }
\newcommand{\Prove}{\textsc{Prove:}\ }
\newcommand{\Let}{\textsc{Let:}\ }
\newcommand{\Suffices}{\textsc{Suffices:}\ }
\newcommand{\Case}{\textsc{Case:}\ }

% ---------- macros ----------
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\VS}{\mathrm{VS}}
\newcommand{\err}{\mathrm{err}}
\newcommand{\opt}{\mathrm{OPT}}
\newcommand{\tw}{\mathrm{tw}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\LD}{\mathsf{LD}}
\newcommand{\BP}{\mathsf{BP}}
\newcommand{\Ring}{\mathcal{B}}
\newcommand{\ind}{\mathbf{1}}
\newcommand{\SAT}{\mathsf{SAT}}
\newcommand{\eps}{\varepsilon}
\newcommand{\epsdp}{\varepsilon_{\mathrm{dp}}}
\newcommand{\lenETH}[1]{\mathrm{ETH}^{\mathrm{len}}_{#1}}
\newcommand{\mOcc}{m_{\mathrm{Occ}}}
\newcommand{\mVC}{m_{\mathrm{VC}}}
\newcommand{\mUC}{m_{\mathrm{UC}}}
\DeclareMathOperator*{\argmin}{arg\,min}

\title{What Does the Refutation of the Exponential Time Hypothesis\\ Mean for Learning Theory?}
\hypersetup{pdftitle={What Does the Refutation of the Exponential Time Hypothesis Mean for Learning Theory?},
  pdfauthor={Xiaoyu Li}}
\author{Xiaoyu Li\thanks{University of New South Wales, \texttt{xiaoyulics@gmail.com}}}
\date{}

\begin{document}
\maketitle

\begin{abstract}
Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying
assignments of a $k$-CNF on $n$ variables in time $2^{n/(\log n)^{1/2-o(1)}}$. Many fine-grained lower
bounds in learning theory rest on ETH and its relatives. We determine what the refutation changes for
learning.

The answer is a \emph{locality principle}: the new algorithms speed up learning when each labeled
example constrains few bits of the hypothesis, and under the CNF form of the Strong Exponential Time
Hypothesis, which survives, the speed-up ends at $\Theta(\log N)$ bits. Three transitions make the
principle precise.
\begin{itemize}[leftmargin=1.2em]
\item \textbf{Locality.} Call a class with $N$-bit descriptions \emph{$\kappa$-local} if each label
depends on at most $\kappa$ description bits, as for quantized models on sparse data. Then proper PAC
learning, exact version-space counting and sampling, and the halving algorithm run in time
$\poly(m)\cdot2^{o(N)}$ on samples of size $m$ for $\kappa=o((\log N)^{1/4}/\sqrt{\log\log N})$, and proper
PAC learning at constant accuracy does so for $\kappa=o(\sqrt{\log N})$. At inverse-polynomial accuracy,
proper learning of $\kappa$-local classes is equivalent to $\kappa$-SAT, up to a factor $2$ in the locality.
Under CNF-SETH, consistency for binarized perceptrons on $O(\log N)$-sparse data needs time
$2^{(1-\gamma)N}$ for every $\gamma>0$.
\item \textbf{Accuracy.} Exact empirical risk minimization, proper agnostic learning and the
exponential mechanism reduce to tensor contractions over a truncated polynomial ring. As a consequence,
the Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams are false. At constant accuracy, proper
learning is SAT parameterized by formula length. With quasi-linear PCPs this gives a $2^{N/\polylog N}$
lower bound under a length form of ETH, which replaces Gap-ETH for reductions of quasi-linear size. At
accuracy $N^{-3}/8$, the Max-3-SAT Hypothesis forces time $2^{(1-o(1))N}$.
\item \textbf{Treewidth.} Exact inference in graphical models of bounded degree and arity takes time
$2^{O(n/\sqrt{\log n})}$. On expanders this beats every elimination order and every structured DNNF.
Under \#CNF-SETH, time $2^{(1-\gamma)\tw}$ is again necessary once a model may have $\tw^{O(1)}$
variables.
\end{itemize}
We also take stock of the conditional lower bounds of learning theory: which ones fall, and which
ones survive on which hypothesis. The next obstacle is a permutation problem. On difference vectors
$e_i-e_j$, empirical risk minimization for real-valued halfspaces is weighted Feedback Arc Set, which
the new algorithms do not reach.
\end{abstract}

\newpage
\setcounter{tocdepth}{2}
\enlargethispage{\baselineskip}
{\small\tableofcontents}
\newpage

\input{sec1_intro}
\input{sec2_prelim}
\input{sec3_locality}
\input{sec4_accuracy}
\input{sec5_treewidth}
\input{sec6_ledger}
\input{sec_related}
\input{sec7_outlook}

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{CAdMRR18}

\bibitem[AA22]{AA22}
Amol Aggarwal and Josh Alman.
\newblock Optimal-degree polynomial approximations for exponentials and
  {G}aussian kernel density estimation.
\newblock In {\em 37th Computational Complexity Conference (CCC)}, volume 234
  of {\em LIPIcs}, pages 22:1--22:23, 2022.

\bibitem[Aar26]{Aar26}
Scott Aaronson.
\newblock Podcasts about the topic: {P}art {II}.
\newblock Shtetl-Optimized, October 26, 2026, comment \#31 of October 27, 2026.
  \url{https://scottaaronson.blog/?p=10239}, 2026.

\bibitem[ABF{\etalchar{+}}08]{ABF+08}
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam~R. Klivans, and Toniann
  Pitassi.
\newblock The complexity of properly learning simple concept classes.
\newblock {\em Journal of Computer and System Sciences}, 74(1):16--34, 2008.

\bibitem[ACAH19]{ACH19}
Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge.
\newblock Subquadratic high-dimensional hierarchical clustering.
\newblock In {\em Advances in Neural Information Processing Systems 32
  (NeurIPS)}, 2019.

\bibitem[ACMS20]{ACMS20}
Antoine Amarilli, Florent Capelli, Mika{\"e}l Monet, and Pierre Senellart.
\newblock Connecting knowledge compilation classes and width parameters.
\newblock {\em Theory of Computing Systems}, 64(5):861--914, 2020.

\bibitem[ACSS20]{ACSS20}
Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song.
\newblock Algorithms and hardness for linear algebra on geometric graphs.
\newblock In {\em 61st IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 541--552, 2020.

\bibitem[ACW16]{ACW16}
Josh Alman, Timothy~M. Chan, and Ryan Williams.
\newblock Polynomial representations of threshold functions and algorithmic
  applications.
\newblock In {\em 57th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 467--476, 2016.

\bibitem[AGKM12]{AGKM12}
Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra.
\newblock Computing a nonnegative matrix factorization -- provably.
\newblock In {\em Proceedings of the 44th Annual ACM Symposium on Theory of
  Computing (STOC)}, 2012.

\bibitem[AKK22]{AKK22}
Per Austrin, Petteri Kaski, and Kaie Kubjas.
\newblock Tensor network complexity of multilinear maps.
\newblock {\em Theory of Computing}, 18(16):1--54, 2022.

\bibitem[AKL07]{AKL07}
Vikraman Arvind, Johannes K{\"o}bler, and Wolfgang Lindner.
\newblock Parameterized learnability of $k$-juntas and related problems.
\newblock In {\em Algorithmic Learning Theory (ALT)}, Lecture Notes in Computer
  Science, pages 120--134, 2007.

\bibitem[AKM21]{AKM21}
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow.
\newblock Training neural networks is {ER}-complete.
\newblock In {\em Advances in Neural Information Processing Systems 34
  (NeurIPS)}, pages 18293--18306, 2021.

\bibitem[ALS22]{ALS22}
Emmanuel Abbe, Shuangping Li, and Allan Sly.
\newblock Binary perceptron: efficient algorithms can find solutions in a rare
  well-connected cluster.
\newblock In {\em Proceedings of the 54th Annual ACM Symposium on Theory of
  Computing (STOC)}, pages 860--873, 2022.

\bibitem[ARW17]{ARW17}
Amir Abboud, Aviad Rubinstein, and Ryan Williams.
\newblock Distributed {PCP} theorems for hardness of approximation in {P}.
\newblock In {\em 58th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 25--36, 2017.

\bibitem[AS23]{AS23}
Josh Alman and Zhao Song.
\newblock Fast attention requires bounded entries.
\newblock In {\em Advances in Neural Information Processing Systems 36
  (NeurIPS)}, pages 63117--63135, 2023.

\bibitem[AS24a]{AS24grad}
Josh Alman and Zhao Song.
\newblock The fine-grained complexity of gradient computation for training
  large language models.
\newblock In {\em Advances in Neural Information Processing Systems 37
  (NeurIPS)}, pages 61419--61454, 2024.

\bibitem[AS24b]{AS24tensor}
Josh Alman and Zhao Song.
\newblock How to capture higher-order correlations? {G}eneralizing matrix
  softmax attention to {K}ronecker computation.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 4306--4333, 2024.

\bibitem[AV20]{AVW20}
Josh Alman and Virginia {Vassilevska Williams}.
\newblock {OV} graphs are (probably) hard instances.
\newblock In {\em 11th Innovations in Theoretical Computer Science Conference
  (ITCS)}, volume 151 of {\em LIPIcs}, pages 83:1--83:18, 2020.

\bibitem[AVW16]{AVW16}
Amir Abboud, Virginia {Vassilevska Williams}, and Joshua Wang.
\newblock Approximation and fixed parameter subquadratic algorithms for radius
  and diameter in sparse graphs.
\newblock In {\em Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 377--391, 2016.

\bibitem[AY25]{AY25}
Josh Alman and Hantao Yu.
\newblock Fundamental limitations on subquadratic alternatives to transformers.
\newblock In {\em International Conference on Learning Representations (ICLR)},
  pages 47475--47498, 2025.

\bibitem[BCFK22]{BCFK22}
Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin K{\"u}nnemann.
\newblock A structural investigation of the approximability of polynomial-time
  problems.
\newblock In {\em 49th International Colloquium on Automata, Languages, and
  Programming (ICALP)}, volume 229 of {\em LIPIcs}, pages 30:1--30:20, 2022.

\bibitem[BCMS14]{BCMS14}
Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky.
\newblock A strongly exponential separation of {DNNF}s from {CNF} formulas.
\newblock arXiv:1411.1995, 2014.

\bibitem[BCMS16]{BCMS16}
Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky.
\newblock Knowledge compilation meets communication complexity.
\newblock In {\em Proceedings of the 25th International Joint Conference on
  Artificial Intelligence (IJCAI)}, pages 1008--1013, 2016.

\bibitem[BEHW87]{BEHW87}
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred~K. Warmuth.
\newblock Occam's razor.
\newblock {\em Information Processing Letters}, 24(6):377--380, 1987.

\bibitem[BEHW89]{BEHW89}
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred~K. Warmuth.
\newblock Learnability and the {V}apnik--{C}hervonenkis dimension.
\newblock {\em Journal of the ACM}, 36(4):929--965, 1989.

\bibitem[BF72]{BF72}
J.~M. Barzdin and R.~V. Freivald.
\newblock On the prediction of general recursive functions.
\newblock {\em Doklady Akademii Nauk SSSR}, 206(3):521--524, 1972.
\newblock English translation in Soviet Mathematics Doklady 13:1224--1228.

\bibitem[BFIS25]{BFIS25}
Matthias Bentert, Fedor~V. Fomin, Tanmay Inamdar, and Saket Saurabh.
\newblock Exponential-time approximation (schemes) for vertex-ordering
  problems.
\newblock In {\em 16th Innovations in Theoretical Computer Science Conference
  (ITCS)}, volume 325 of {\em LIPIcs}, pages 15:1--15:18, 2025.

\bibitem[BFK{\etalchar{+}}12]{BFK+12}
Hans~L. Bodlaender, Fedor~V. Fomin, Arie M. C.~A. Koster, Dieter Kratsch, and
  Dimitrios~M. Thilikos.
\newblock A note on exact algorithms for vertex ordering problems on graphs.
\newblock {\em Theory of Computing Systems}, 50(3):420--432, 2012.

\bibitem[BGS23]{BGS23}
Cornelius Brand, Robert Ganian, and Kirill Simonov.
\newblock A parameterized theory of {PAC} learning.
\newblock In {\em Proceedings of the 37th AAAI Conference on Artificial
  Intelligence}, volume~37, pages 6834--6841, 2023.

\bibitem[BHJ{\etalchar{+}}23]{BHJ+23}
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and
  Simon Weber.
\newblock Training fully connected neural networks is
  $\exists\mathbb{R}$-complete.
\newblock In {\em Advances in Neural Information Processing Systems 36
  (NeurIPS)}, pages 36222--36237, 2023.

\bibitem[BHKK12]{BHKK12}
Andreas Bj{\"o}rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.
\newblock The traveling salesman problem in bounded degree graphs.
\newblock {\em ACM Transactions on Algorithms}, 8(2):18:1--18:13, 2012.

\bibitem[BIS17]{BIS17}
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt.
\newblock On the fine-grained complexity of empirical risk minimization: Kernel
  methods and neural networks.
\newblock In {\em Advances in Neural Information Processing Systems 30 (NIPS)},
  pages 4308--4318, 2017.

\bibitem[Bj{\"o}14]{Bjo14}
Andreas Bj{\"o}rklund.
\newblock Determinant sums for undirected {H}amiltonicity.
\newblock {\em SIAM Journal on Computing}, 43(1):280--299, 2014.

\bibitem[BKST25]{BKST25}
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan.
\newblock Computational-statistical tradeoffs from {NP}-hardness.
\newblock In {\em 66th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 512--530, 2025.

\bibitem[BLQT21]{BLQT21}
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan.
\newblock Properly learning decision trees in almost polynomial time.
\newblock In {\em 62nd IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 920--929, 2021.

\bibitem[BLRS13]{BLRS13}
Paul Beame, Jerry Li, Sudeepa Roy, and Dan Suciu.
\newblock Lower bounds for exact model counting and applications in
  probabilistic databases.
\newblock In {\em Proceedings of the 29th Conference on Uncertainty in
  Artificial Intelligence (UAI)}, pages 52--61, 2013.

\bibitem[BMVY25]{BMVY25}
Mitali Bafna, Dor Minzer, Nikhil Vyas, and Zhiwei Yun.
\newblock Quasi-linear size {PCPs} with small soundness from {HDX}.
\newblock In {\em Proceedings of the 57th Annual ACM Symposium on Theory of
  Computing (STOC)}, pages 45--53, 2025.

\bibitem[BNS13]{BNS13}
Amos Beimel, Kobbi Nissim, and Uri Stemmer.
\newblock Characterizing the sample complexity of private learners.
\newblock In {\em Proceedings of the 4th Conference on Innovations in
  Theoretical Computer Science (ITCS)}, pages 97--110, 2013.

\bibitem[BR92]{BR92}
Avrim Blum and Ronald~L. Rivest.
\newblock Training a 3-node neural network is {NP}-complete.
\newblock {\em Neural Networks}, 5(1):117--127, 1992.

\bibitem[BSS08]{BS08}
Eli Ben-Sasson and Madhu Sudan.
\newblock Short {PCPs} with polylog query complexity.
\newblock {\em SIAM Journal on Computing}, 38(2):551--607, 2008.

\bibitem[BSS{\etalchar{+}}19]{BSS+19}
Teodora Baluta, Shiqi Shen, Shweta Shinde, Kuldeep~S. Meel, and Prateek Saxena.
\newblock Quantitative verification of neural networks and its security
  applications.
\newblock In {\em Proceedings of the 2019 ACM SIGSAC Conference on Computer and
  Communications Security (CCS)}, pages 1249--1264, 2019.

\bibitem[BT17]{BT17}
Arturs Backurs and Christos Tzamos.
\newblock Improving {V}iterbi is hard: better runtimes imply faster clique
  algorithms.
\newblock In {\em Proceedings of the 34th International Conference on Machine
  Learning (ICML)}, volume~70 of {\em PMLR}, pages 311--321, 2017.

\bibitem[BZ16]{BZ16}
Mark Bun and Mark Zhandry.
\newblock Order-revealing encryption and the hardness of private learning.
\newblock In {\em Theory of Cryptography (TCC)}, Lecture Notes in Computer
  Science, pages 176--206, 2016.

\bibitem[CACSS26]{CKSS26}
Vincent Cohen-Addad, Karthik {C. S.}, David Saulpic, and Chris Schwiegelshohn.
\newblock Almost-optimal upper and lower bounds for clustering in low
  dimensional {E}uclidean spaces.
\newblock In {\em 42nd International Symposium on Computational Geometry
  (SoCG)}, volume 367 of {\em LIPIcs}, pages 34:1--34:16, 2026.

\bibitem[CAdMRR18]{CdMRR18}
Vincent Cohen-Addad, Arnaud de~Mesmay, Eva Rotenberg, and Alan Roytman.
\newblock The bane of low-dimensionality clustering.
\newblock In {\em Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, 2018.

\bibitem[CC16]{CC16}
Chandra Chekuri and Julia Chuzhoy.
\newblock Polynomial bounds for the grid-minor theorem.
\newblock {\em Journal of the ACM}, 63(5):40:1--40:65, 2016.

\bibitem[CCK{\etalchar{+}}20]{CCK+20}
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin
  Manurangsi, Danupon Nanongkai, and Luca Trevisan.
\newblock From {Gap-Exponential Time Hypothesis} to fixed parameter tractable
  inapproximability: {C}lique, {D}ominating {S}et, and more.
\newblock {\em SIAM Journal on Computing}, 49(4):772--810, 2020.

\bibitem[CDL{\etalchar{+}}16]{CDL+16}
Marek Cygan, Holger Dell, Daniel Lokshtanov, D{\'a}niel Marx, Jesper Nederlof,
  Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlstr{\"o}m.
\newblock On problems as hard as {CNF-SAT}.
\newblock {\em ACM Transactions on Algorithms}, 12(3):41:1--41:24, 2016.

\bibitem[CFG{\etalchar{+}}17]{CFG+17}
Marek Cygan, Fedor~V. Fomin, Alexander Golovnev, Alexander~S. Kulikov, Ivan
  Mihajlin, Jakub Pachocki, and Arkadiusz Soca{\l}a.
\newblock Tight lower bounds on graph embedding problems.
\newblock {\em Journal of the ACM}, 64(3):18:1--18:22, 2017.

\bibitem[CGI{\etalchar{+}}16]{CGI+16}
Marco~L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan
  Paturi, and Stefan Schneider.
\newblock Nondeterministic extensions of the strong exponential time hypothesis
  and consequences for non-reducibility.
\newblock In {\em Proceedings of the 2016 ACM Conference on Innovations in
  Theoretical Computer Science (ITCS)}, pages 261--270, 2016.

\bibitem[Che26]{Che26}
Xiangle Chen.
\newblock Exact algorithms and complexity of the smallest grammar problem.
\newblock arXiv:2610.32298v2, October 27, 2026, 2026.

\bibitem[CIP06]{CIP06}
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi.
\newblock A duality between clause width and clause density for {SAT}.
\newblock In {\em 21st Annual IEEE Conference on Computational Complexity
  (CCC)}, pages 252--260, 2006.

\bibitem[CKN18]{CKN18}
Marek Cygan, Stefan Kratsch, and Jesper Nederlof.
\newblock Fast {H}amiltonicity checking via bases of perfect matchings.
\newblock {\em Journal of the ACM}, 65(3):12:1--12:46, 2018.

\bibitem[CKS20]{CKS20}
Cl{\'e}ment~L. Canonne, Gautam Kamath, and Thomas Steinke.
\newblock The discrete {G}aussian for differential privacy.
\newblock In {\em Advances in Neural Information Processing Systems 33
  (NeurIPS)}, pages 15676--15688, 2020.

\bibitem[CL09]{CL09}
Jianer Chen and Yang Liu.
\newblock An improved {SAT} algorithm in terms of formula length.
\newblock In {\em Algorithms and Data Structures (WADS)}, volume 5664 of {\em
  Lecture Notes in Computer Science}, pages 144--155, 2009.

\bibitem[{Cla}26]{Cla26}
{Claude (Anthropic)}.
\newblock A $2^{o(n)}$ time algorithm for 3-{SAT}.
\newblock Hexagon preprint hexagon:2610.00577v1, dated October 26, 2026.
  \url{https://hexagonmath.org/2610.00577v1}. Lean development at
  \url{https://github.com/anthropics/formal-math/tree/main/eth}, 2026.

\bibitem[CRTY23]{CRTY23}
Lijie Chen, Ron~D. Rothblum, Roei Tell, and Eylon Yogev.
\newblock On exponential-time hypotheses, derandomization, and circuit lower
  bounds.
\newblock {\em Journal of the ACM}, 70(4):1--62, 2023.

\bibitem[CSH08]{CSH08}
Venkat Chandrasekaran, Nathan Srebro, and Prahladh Harsha.
\newblock Complexity of inference in graphical models.
\newblock In {\em Proceedings of the 24th Conference on Uncertainty in
  Artificial Intelligence (UAI)}, pages 70--78, 2008.

\bibitem[CSS99]{CSS99}
William~W. Cohen, Robert~E. Schapire, and Yoram Singer.
\newblock Learning to order things.
\newblock {\em Journal of Artificial Intelligence Research}, 10:243--270, 1999.

\bibitem[CW21]{CW21}
Timothy~M. Chan and R.~Ryan Williams.
\newblock Deterministic {APSP}, orthogonal vectors, and more: quickly
  derandomizing {R}azborov--{S}molensky.
\newblock {\em ACM Transactions on Algorithms}, 17(1):2:1--2:14, 2021.

\bibitem[CXZ21]{CXZ21}
Huairui Chu, Mingyu Xiao, and Zhe Zhang.
\newblock An improved upper bound for {SAT}.
\newblock In {\em Proceedings of the 35th AAAI Conference on Artificial
  Intelligence}, volume~35, pages 3707--3714, 2021.

\bibitem[DDOV19]{DDV19}
Jeffrey~M. Dudek, Leonardo Due{\~n}as-Osorio, and Moshe~Y. Vardi.
\newblock Efficient contraction of large tensor networks for weighted model
  counting through graph decompositions.
\newblock arXiv:1908.04381, 2019.

\bibitem[DHM{\etalchar{+}}14]{DHM+14}
Holger Dell, Thore Husfeldt, D{\'a}niel Marx, Nina Taslaman, and Martin
  Wahl{\'e}n.
\newblock Exponential time complexity of the permanent and the {T}utte
  polynomial.
\newblock {\em ACM Transactions on Algorithms}, 10(4):21:1--21:32, 2014.

\bibitem[Din07]{Din07}
Irit Dinur.
\newblock The {PCP} theorem by gap amplification.
\newblock {\em Journal of the ACM}, 54(3):12:1--12:44, 2007.

\bibitem[Din16]{Din16}
Irit Dinur.
\newblock Mildly exponential reduction from gap {3SAT} to polynomial-gap
  label-cover.
\newblock Electronic Colloquium on Computational Complexity (ECCC), TR16-128,
  2016.

\bibitem[DKM19]{DKM19}
Ilias Diakonikolas, Daniel~M. Kane, and Pasin Manurangsi.
\newblock Nearly tight bounds for robust proper learning of halfspaces with a
  margin.
\newblock In {\em Advances in Neural Information Processing Systems 32
  (NeurIPS)}, 2019.

\bibitem[DKM20]{DKM20}
Ilias Diakonikolas, Daniel~M. Kane, and Pasin Manurangsi.
\newblock The complexity of adversarially robust proper learning of halfspaces
  with agnostic noise.
\newblock In {\em Advances in Neural Information Processing Systems 33
  (NeurIPS)}, pages 20449--20461, 2020.

\bibitem[DLSS13]{DLSS13}
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz.
\newblock More data speeds up training time in learning halfspaces over sparse
  vectors.
\newblock In {\em Advances in Neural Information Processing Systems 26 (NIPS)},
  2013.

\bibitem[DNR{\etalchar{+}}09]{DNR+09}
Cynthia Dwork, Moni Naor, Omer Reingold, Guy~N. Rothblum, and Salil Vadhan.
\newblock On the complexity of differentially private data release: efficient
  algorithms and hardness results.
\newblock In {\em Proceedings of the 41st Annual ACM Symposium on Theory of
  Computing (STOC)}, pages 381--390, 2009.

\bibitem[FGMT25]{FGMT25}
Florent Foucaud, Harmender Gahlawat, Fionn {Mc Inerney}, and Prafullkumar Tale.
\newblock The parameterized complexity of computing the {VC}-dimension.
\newblock Advances in Neural Information Processing Systems 38 (NeurIPS);
  arXiv:2510.17451, 2025.

\bibitem[FHN22]{FHN22}
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier.
\newblock The computational complexity of {ReLU} network training parameterized
  by data dimensionality.
\newblock {\em Journal of Artificial Intelligence Research}, 74:1775--1790,
  2022.

\bibitem[FMR22]{FMR22}
Jacob Focke, D{\'a}niel Marx, and Pawe{\l} Rz{\k{a}}{\.z}ewski.
\newblock Counting list homomorphisms from graphs of bounded treewidth: tight
  complexity bounds.
\newblock In {\em Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, 2022.

\bibitem[FSST97]{FSST97}
Yoav Freund, H.~Sebastian Seung, Eli Shamir, and Naftali Tishby.
\newblock Selective sampling using the query by committee algorithm.
\newblock {\em Machine Learning}, 28(2--3):133--168, 1997.

\bibitem[GBNT05]{GNT05}
Ran Gilad-Bachrach, Amir Navot, and Naftali Tishby.
\newblock Query by committee made real.
\newblock In {\em Advances in Neural Information Processing Systems 18 (NIPS)},
  2005.

\bibitem[GIKW19]{GIKW19}
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams.
\newblock Completeness for first-order properties on sparse structures with
  algorithmic applications.
\newblock {\em ACM Transactions on Algorithms}, 15(2), 2019.

\bibitem[GKMR21]{GKMR21}
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman.
\newblock Tight hardness results for training depth-2 {ReLU} networks.
\newblock In {\em 12th Innovations in Theoretical Computer Science Conference
  (ITCS)}, volume 185 of {\em LIPIcs}, pages 22:1--22:14, 2021.

\bibitem[GM09]{GM09}
Martin Grohe and D{\'a}niel Marx.
\newblock On tree width, bramble size, and expansion.
\newblock {\em Journal of Combinatorial Theory, Series B}, 99(1):218--228,
  2009.

\bibitem[GRS93]{GRS93}
Sally~A. Goldman, Ronald~L. Rivest, and Robert~E. Schapire.
\newblock Learning binary relations and total orders.
\newblock {\em SIAM Journal on Computing}, 22(5):1006--1034, 1993.

\bibitem[Gy{\"o}90]{Gyo90}
G{\'e}za Gy{\"o}rgyi.
\newblock First-order transition to perfect generalization in a neural network
  with binary synapses.
\newblock {\em Physical Review A}, 41(12):7097--7100, 1990.

\bibitem[Hir00]{Hir00}
Edward~A. Hirsch.
\newblock New worst-case upper bounds for {SAT}.
\newblock {\em Journal of Automated Reasoning}, 24(4):397--420, 2000.

\bibitem[Hir22]{Hir22}
Shuichi Hirahara.
\newblock {NP}-hardness of learning programs and partial {MCSP}.
\newblock In {\em 63rd IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 968--979, 2022.

\bibitem[HMP04]{HMP04}
Haym Hirsh, Nina Mishra, and Leonard Pitt.
\newblock Version spaces and the consistency problem.
\newblock {\em Artificial Intelligence}, 156(2):115--138, 2004.

\bibitem[Ila20]{Ila20}
Rahul Ilango.
\newblock Constant depth formula and partial function versions of {MCSP} are
  hard.
\newblock In {\em 61st IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 424--433, 2020.

\bibitem[Ila21]{Ila21}
Rahul Ilango.
\newblock The minimum formula size problem is ({ETH}) hard.
\newblock In {\em 62nd IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 427--432, 2021.

\bibitem[Ilv20]{Ilv20}
Christina Ilvento.
\newblock Implementing the exponential mechanism with base-2 differential
  privacy.
\newblock In {\em Proceedings of the 2020 ACM SIGSAC Conference on Computer and
  Communications Security (CCS)}, pages 717--742, 2020.

\bibitem[IMP12]{IMP12}
Russell Impagliazzo, William Matthews, and Ramamohan Paturi.
\newblock A satisfiability algorithm for {AC}$^0$.
\newblock In {\em Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 961--972, 2012.

\bibitem[IP01]{IP01}
Russell Impagliazzo and Ramamohan Paturi.
\newblock On the complexity of $k$-{SAT}.
\newblock {\em Journal of Computer and System Sciences}, 62(2):367--375, 2001.

\bibitem[IPZ01]{IPZ01}
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.
\newblock Which problems have strongly exponential complexity?
\newblock {\em Journal of Computer and System Sciences}, 63(4):512--530, 2001.

\bibitem[JVV86]{JVV86}
Mark~R. Jerrum, Leslie~G. Valiant, and Vijay~V. Vazirani.
\newblock Random generation of combinatorial structures from a uniform
  distribution.
\newblock {\em Theoretical Computer Science}, 43:169--188, 1986.

\bibitem[KB09]{KB09}
Johan Kwisthout and Hans~L. Bodlaender.
\newblock Conditional lower bounds on the complexity of probabilistic
  inference.
\newblock Technical Report UU-CS-2009-018, Department of Information and
  Computing Sciences, Utrecht University, 2009.

\bibitem[KBvdG10]{KBG10}
Johan Kwisthout, Hans~L. Bodlaender, and Linda~C. van~der Gaag.
\newblock The necessity of bounded treewidth for efficient inference in
  {B}ayesian networks.
\newblock In {\em Proceedings of the 19th European Conference on Artificial
  Intelligence (ECAI)}, pages 237--242, 2010.

\bibitem[KCMR19]{KCMR19}
Stefanos Kourtis, Claudio Chamon, Eduardo Mucciolo, and Andrei~E. Ruckenstein.
\newblock Fast counting with tensor networks.
\newblock {\em SciPost Physics}, 7(5):060, 2019.

\bibitem[KLN{\etalchar{+}}11]{KLN+11}
Shiva~Prasad Kasiviswanathan, Homin~K. Lee, Kobbi Nissim, Sofya Raskhodnikova,
  and Adam Smith.
\newblock What can we learn privately?
\newblock {\em SIAM Journal on Computing}, 40(3):793--826, 2011.

\bibitem[KS04]{KS04}
Adam~R. Klivans and Rocco~A. Servedio.
\newblock Learning {DNF} in time $2^{\tilde{o}(n^{1/3})}$.
\newblock {\em Journal of Computer and System Sciences}, 68(2):303--318, 2004.

\bibitem[KS10]{KaSc10}
Marek Karpinski and Warren Schudy.
\newblock Faster algorithms for feedback arc set tournament, {K}emeny rank
  aggregation and betweenness tournament.
\newblock In {\em Algorithms and Computation (ISAAC)}, Lecture Notes in
  Computer Science, pages 3--14, 2010.

\bibitem[KST23a]{KST23focs}
Caleb Koch, Carmen Strassle, and Li-Yang Tan.
\newblock Properly learning decision trees with queries is {NP}-hard.
\newblock In {\em 64th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 2383--2407, 2023.

\bibitem[KST23b]{KST23soda}
Caleb Koch, Carmen Strassle, and Li-Yang Tan.
\newblock Superpolynomial lower bounds for decision tree learning and testing.
\newblock In {\em Proceedings of the 2023 ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 1962--1994, 2023.

\bibitem[KST24]{KST24focs}
Caleb Koch, Carmen Strassle, and Li-Yang Tan.
\newblock Fast decision tree learning solves hard coding-theoretic problems.
\newblock In {\em 65th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 1893--1910, 2024.

\bibitem[KWH23]{KWH23}
Feyza~Duman Keles, Pruthuvi~Mahesakya Wijewardena, and Chinmay Hegde.
\newblock On the computational complexity of self-attention.
\newblock In {\em International Conference on Algorithmic Learning Theory
  (ALT)}, volume 201 of {\em PMLR}, pages 597--619, 2023.

\bibitem[Lam95]{Lam95}
Leslie Lamport.
\newblock How to write a proof.
\newblock {\em The American Mathematical Monthly}, 102(7):600--608, 1995.

\bibitem[Lam12]{Lam12}
Leslie Lamport.
\newblock How to write a 21st century proof.
\newblock {\em Journal of Fixed Point Theory and Applications}, 11(1):43--63,
  2012.

\bibitem[Lit88]{Lit88}
Nick Littlestone.
\newblock Learning quickly when irrelevant attributes abound: A new
  linear-threshold algorithm.
\newblock {\em Machine Learning}, 2(4):285--318, 1988.

\bibitem[LMS18a]{LMS18tw}
Daniel Lokshtanov, D{\'a}niel Marx, and Saket Saurabh.
\newblock Known algorithms on graphs of bounded treewidth are probably optimal.
\newblock {\em ACM Transactions on Algorithms}, 14(2):13:1--13:30, 2018.

\bibitem[LMS18b]{LMS18s}
Daniel Lokshtanov, D{\'a}niel Marx, and Saket Saurabh.
\newblock Slightly superexponential parameterized problems.
\newblock {\em SIAM Journal on Computing}, 47(3):675--702, 2018.

\bibitem[LVW18]{LVWW18}
Andrea Lincoln, Virginia {Vassilevska Williams}, and Ryan Williams.
\newblock Tight hardness for shortest cycles and paths in sparse graphs.
\newblock In {\em Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 1236--1252, 2018.

\bibitem[Man23]{Man23}
Pasin Manurangsi.
\newblock Improved inapproximability of {VC} dimension and {L}ittlestone's
  dimension via (unbalanced) biclique.
\newblock In {\em 14th Innovations in Theoretical Computer Science Conference
  (ITCS)}, volume 251 of {\em LIPIcs}, pages 85:1--85:18, 2023.

\bibitem[Man26]{Man26}
Pasin Manurangsi.
\newblock Almost-polynomial ratio {Almost-ETH}-hardness of approximating
  densest $k$-subgraph.
\newblock arXiv:1611.05991v3, version of October 27, 2026, 2026.

\bibitem[Mar10]{Mar10}
D{\'a}niel Marx.
\newblock Can you beat treewidth?
\newblock {\em Theory of Computing}, 6:85--112, 2010.

\bibitem[MR17a]{MRa17}
Pasin Manurangsi and Prasad Raghavendra.
\newblock A birthday repetition theorem and complexity of approximating dense
  {CSPs}.
\newblock In {\em 44th International Colloquium on Automata, Languages, and
  Programming (ICALP)}, volume~80 of {\em LIPIcs}, pages 78:1--78:15, 2017.

\bibitem[MR17b]{MR17}
Pasin Manurangsi and Aviad Rubinstein.
\newblock Inapproximability of {VC} dimension and {L}ittlestone's dimension.
\newblock In {\em Proceedings of the 30th Conference on Learning Theory
  (COLT)}, volume~65 of {\em PMLR}, pages 1432--1460, 2017.

\bibitem[MS08]{MS08}
Igor~L. Markov and Yaoyun Shi.
\newblock Simulating quantum computation by contracting tensor networks.
\newblock {\em SIAM Journal on Computing}, 38(3):963--981, 2008.

\bibitem[MT07]{MT07}
Frank McSherry and Kunal Talwar.
\newblock Mechanism design via differential privacy.
\newblock In {\em 48th IEEE Symposium on Foundations of Computer Science
  (FOCS)}, pages 94--103, 2007.

\bibitem[NKR{\etalchar{+}}18]{NKR+18}
Nina Narodytska, Shiva Kasiviswanathan, Leonid Ryzhyk, Mooly Sagiv, and Toby
  Walsh.
\newblock Verifying properties of binarized deep neural networks.
\newblock In {\em Proceedings of the 32nd AAAI Conference on Artificial
  Intelligence}, 2018.

\bibitem[{Ope}26a]{OAI26}
{OpenAI}.
\newblock The {E}xponential {T}ime {H}ypothesis is false.
\newblock OpenAI Math Release preprint, dated October 17, 2026, revised October
  25, 2026, released October 26, 2026.
  \url{https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf},
  2026.

\bibitem[{Ope}26b]{OAI26lean}
{OpenAI}.
\newblock Scope of the {L}ean formalization for ``{T}he {E}xponential {T}ime
  {H}ypothesis is false''.
\newblock \url{https://github.com/openai/math/blob/main/lean/docs/378.md},
  2026.

\bibitem[PV88]{PV88}
Leonard Pitt and Leslie~G. Valiant.
\newblock Computational limitations on learning from examples.
\newblock {\em Journal of the ACM}, 35(4):965--984, 1988.

\bibitem[PW10]{PW10}
Mihai P{\u{a}}tra{\c{s}}cu and Ryan Williams.
\newblock On the possibility of faster {SAT} algorithms.
\newblock In {\em Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete
  Algorithms (SODA)}, pages 1065--1075, 2010.

\bibitem[PX23]{PX23}
Junqiang Peng and Mingyu Xiao.
\newblock Further improvements for {SAT} in terms of formula length.
\newblock {\em Information and Computation}, 294:105085, 2023.

\bibitem[Rub18]{Rub18}
Aviad Rubinstein.
\newblock Hardness of approximate nearest neighbor search.
\newblock In {\em Proceedings of the 50th Annual ACM Symposium on Theory of
  Computing (STOC)}, pages 1260--1268, 2018.

\bibitem[Sch05]{Sch05}
Rainer Schuler.
\newblock An algorithm for the satisfiability problem of formulas in
  conjunctive normal form.
\newblock {\em Journal of Algorithms}, 54(1):40--44, 2005.

\bibitem[SH90]{SH90}
Richard~E. Stearns and Harry~B. {Hunt III}.
\newblock Power indices and easier hard problems.
\newblock {\em Mathematical Systems Theory}, 23:209--225, 1990.

\bibitem[SOS92]{SOS92}
H.~Sebastian Seung, Manfred Opper, and Haim Sompolinsky.
\newblock Query by committee.
\newblock In {\em Proceedings of the Fifth Annual Workshop on Computational
  Learning Theory (COLT)}, pages 287--294, 1992.

\bibitem[SS10]{SS10}
Marko Samer and Stefan Szeider.
\newblock Algorithms for propositional model counting.
\newblock {\em Journal of Discrete Algorithms}, 8(1):50--64, 2010.

\bibitem[SSBD14]{SSBD14}
Shai Shalev-Shwartz and Shai Ben-David.
\newblock {\em Understanding Machine Learning: From Theory to Algorithms}.
\newblock Cambridge University Press, 2014.

\bibitem[SST92]{SST92}
H.~Sebastian Seung, Haim Sompolinsky, and Naftali Tishby.
\newblock Statistical mechanics of learning from examples.
\newblock {\em Physical Review A}, 45(8):6056--6091, 1992.

\bibitem[TIC{\etalchar{+}}19]{TIC+19}
Rodrigo {Toro Icarte}, Le{\'o}n Illanes, Margarita~P. Castro, Andre~A. Cire,
  Sheila~A. McIlraith, and J.~Christopher Beck.
\newblock Training binarized neural networks using {MIP} and {CP}.
\newblock In {\em Principles and Practice of Constraint Programming (CP)},
  Lecture Notes in Computer Science, pages 401--417, 2019.

\bibitem[Ull16]{Ull16}
Jonathan Ullman.
\newblock Answering $n^{2+o(1)}$ counting queries with differential privacy is
  hard.
\newblock {\em SIAM Journal on Computing}, 45(2):473--496, 2016.

\bibitem[VW21]{VW21}
Nikhil Vyas and Ryan Williams.
\newblock On super strong {ETH}.
\newblock {\em Journal of Artificial Intelligence Research}, 70:473--495, 2021.

\bibitem[Wah05]{Wah05}
Magnus Wahlstr{\"o}m.
\newblock An algorithm for the {SAT} problem for formulae of linear length.
\newblock In {\em Algorithms -- ESA 2005}, volume 3669 of {\em Lecture Notes in
  Computer Science}, pages 107--118, 2005.

\bibitem[WFS15]{WFS15}
Yu-Xiang Wang, Stephen Fienberg, and Alex Smola.
\newblock Privacy for free: posterior sampling and stochastic gradient {M}onte
  {C}arlo.
\newblock In {\em Proceedings of the 32nd International Conference on Machine
  Learning (ICML)}, volume~37 of {\em PMLR}, pages 2493--2502, 2015.

\bibitem[Wil05]{Wil05}
Ryan Williams.
\newblock A new algorithm for optimal 2-constraint satisfaction and its
  implications.
\newblock {\em Theoretical Computer Science}, 348(2--3):357--365, 2005.

\end{thebibliography}

\clearpage
\appendix
\input{app_a_roadmap}
\input{app_b_engine}
\input{app_c_locality}
\input{app_d_accuracy}
\input{app_e_treewidth}
\input{app_f_ledger}
\input{app_g_notation}

\end{document}