Conceptio › Archive › arXiv CS

arXiv CSopen access

Fitting and Learning Basis-Restricted Propositional Formulas

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Fitting and Learning Basis-Restricted Propositional Formulas Balder ten Cate September 9, 2026

arXiv:2609.08961v1 [cs.LO] 8 Sep 2026

Abstract For a finite set O of Boolean functions, we consider the class of propositional formulas built using the functions in O as connectives. We determine, for each possible choice of O, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.

Introduction

Fix a finite set O of Boolean functions and let PLO be the class of propositional formulas that can be built using the functions in O as connectives. Varying O gives a family of concept classes, and a natural question is how the difficulty of the standard learning-theoretic tasks depends on the choice of O. Several such classifications are either known or implied by known results, but they are scattered across the literature. We put them side by side, focusing on four problems. • Fitting. Given a labeled sample, decide whether some PLO -formula agrees with all of it, and if so produce one. • Occam algorithms. If the sample is realizable, find a fitting formula of near-minimal size. • Empirical risk minimization. When the sample need not be realizable, find a PLO -formula minimizing the number of mistakes. • PAC learning. Is PLO efficiently learnable in (variants of) the PAC model? The four problems are not independent. Fitting is the special case of empirical risk minimization in which the sample is realizable, so an ERM algorithm is in particular a fitting algorithm. An Occam algorithm is a fitting algorithm that compresses, and compression yields a PAC learner, so hardness of PAC learning rules out Occam algorithms as well. These questions can be studied also for CIRO , that is, the family of circuits using functions from O as gates. Note that PLO and CIRO have the same expressive power, but may differ in succinctness. In addition, in Section 9 we discuss other fragments, such as monotone CNF and Horn CNF, that do not fall under the above basis-generated regime. Our contributions are partly organizational: we give a uniform presentation and we provide written-out proofs for results that are only sketched in the literature. Our main novel contributions are an algorithm for constructing fitting formulas efficiently based on a refinement of the classic Baker–Pixley construction, and a trichotomy theorem for empirical risk minimization, building on known results for hypergraph vertex-cover problems. We also fill a small gap, showing that the PAC-learnability dichotomy in [16] holds not only for circuits but also for formulas. The picture that arises is as follows. 1

Fitting and Occam algorithms.

The basic fitting problem turns out to be uniformly easy:

Theorem 1.1 (Fitting). Let O be a fixed finite basis. Then PLO has a polynomial-time fitting algorithm: given a labeled sample it decides whether the sample is realizable, and if so returns a fitting PLO -formula of polynomial size. The same holds for CIRO . Here, by a labeled sample we mean a finite list of labeled examples (a, b) with a ∈ {0, 1}n and b ∈ {0, 1}; a formula fits the sample if it takes the value b at a for each of its examples, and the sample is realizable for PLO if some PLO -formula fits it. The tractability of testing existence was already observed in [40]. We give a proof in Section 3, which also shows how to construct fitting formulas efficiently, using a refinement of the Baker–Pixley theorem. One may ask for a short fitting formula. An Occam algorithm for PLO is a polynomialtime fitting algorithm that, on every realizable sample, returns a fitting formula of size at most p sopt , n · mβ for some fixed polynomial p and some fixed β < 1, where m is the number of examples, n is the number of Boolean variables, and sopt is the least size of a fitting PLO formula. An Occam algorithm compresses, as it returns something sublinear in m. One may ask for more, namely an attribute-efficient Occam algorithm, whose size bound does not depend on n: a fitting formula of size at most p(sopt ) · mβ . Theorem 1.2 (Occam algorithms, from [16]). Let O be a finite basis of Boolean functions. (a) If O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {¬, ⊤, ⊥}, then PLO has an attribute-efficient Occam algorithm. (b) If {⊕3 } ⪯ O ⪯ {⊕, ⊤, ⊥}, then PLO has an Occam algorithm, but we do not know whether it has an attribute-efficient one. (c) Otherwise PLO does not have an Occam algorithm, under the cryptographic assumptions of Section 6. The same holds for CIRO . The proof is given in Section 7; the negative part is a consequence of the classification of PAC learnability, Theorem 1.5 below, since an Occam algorithm yields a proper PAC learner [11]. Empirical risk minimization. The next problem drops the assumption that the sample is realizable and asks for a hypothesis that minimizes the empirical risk, that is, the fraction of misclassified examples. This is empirical risk minimization (ERM). Unlike the fitting problem, ERM is not always solvable in polynomial time. When it is hard, one may ask for an approximation algorithm. We say that an algorithm is a weak approximator for PLO if there are δ, ε > 0 such that, on every sample whose optimal hypothesis has empirical risk ≤ ε, the algorithm produces a PLO -hypothesis of empirical risk ≤ 1/2 − δ. This is, in some sense, the lowest bar. Note that, if O includes the truth constants ⊤ and ⊥, then there is always a trivial solution that achieves an error fraction ≤ 1/2. Every k-approximation algorithm for a constant factor k is a weak approximator: it suffices to pick ε = 1/(4k) and δ = 1/4. To state the classification, for r > j ≥ 1 let thrj denote the r-ary threshold operation “at least j of r”, that is, thrj (x1 , . . . , xr ) = 1

⇐⇒

x1 + · · · + xr ≥ j.

Thus thrj and thrr−j+1 are dual, and th32 = maj. Furthermore, in what follows, O ⪯ O′ means that every function in O is term-definable from O′ , and O ≡ O′ that the two are interdefinable. Theorem 1.3 (Empirical risk minimization). Let O be a finite basis of Boolean functions. The ERM problem for PLO falls into one of the following three regimes. 2

(i) If {∧} ⪯ O ⪯ {∧, ⊤, ⊥},

{∨} ⪯ O ⪯ {∨, ⊤, ⊥},

{⊕3 } ⪯ O ⪯ {⊕, ⊤, ⊥},

then, unless P = NP, there is no polynomial-time weak approximator for PLO , whatever its constants δ, ε > 0. In particular ERM for PLO is NP-hard and has no polynomial-time constant-factor approximation. (ii) If, for some k ≥ 2, k+1 {thk+1 2 } ⪯ O ⪯ {→, th2 }

k+1 {thk+1 k } ⪯ O ⪯ {x ∧ ¬y, thk },

then ERM for PLO is NP-hard; it admits a polynomial-time k-approximation; and, under the Unique Games Conjecture, it admits no polynomial-time (k − ε)-approximation for any ε > 0. The factor k is therefore optimal under that conjecture. (iii) In all other cases, ERM for PLO is solvable in polynomial time. The same holds for CIRO . The proof is given in Section 4. Note that, in light of Theorem 1.1, ERM may be equivalently viewed as the problem, given a labeled sample, of finding a relabeling that is realizable and disagrees on as few examples as possible. Learning from random examples. We now turn to learning, beginning with the combinatorial parameter that governs how many examples are needed. Proposition 1.4 (VC dimension). Let O be a finite basis of Boolean functions and let n ≥ 1. If O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {⊕, ⊤, ⊥}, then the VC dimension of PLO in n variables is at most n + 1. Otherwise it is 2Ω(n) . We now consider two notions of learnability. Both are representation-sensitive: the learner is told a bound s on the size of a representation of the target, and may use a number of examples polynomial in 1/ε, 1/δ, n and s. By a proper PAC learner for PLO we mean an algorithm that, given ε, δ > 0, the bound s, and sufficiently many examples drawn from an arbitrary distribution and labeled by a target in PLO of size at most s, outputs in polynomial time a hypothesis from the class whose error is at most ε with probability at least 1 − δ. A PAC predictor need not output a hypothesis: after seeing the examples it is given one further point and must predict its label, with error bounded away from 1/2 by an inverse polynomial, and it may in addition ask membership queries, that is, ask for the value of the target at points of its own choosing. PAC prediction is easier than producing a hypothesis, and membership queries only help, so hardness of PAC prediction with queries is the stronger statement.1 Both notions, and the cryptographic assumptions, are given precisely in Section 6. Theorem 1.5 (PAC learning and PAC prediction [16]). Let O be a finite basis. The following are equivalent. (a) O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {⊕, ⊤, ⊥}; (b) PLO is polynomially properly PAC learnable; (c) PLO is polynomially PAC predictable with membership queries. 1

This relies on the fact that, in the concept classes we consider here, the label of a given example for a given concept can be computed in polynomial time.

The implications (a) ⇒ (b) ⇒ (c) are unconditional; the remaining implication (c) ⇒ (a) holds under cryptographic assumptions described in Section 6. The same equivalence holds with CIRO in place of PLO . Dalmau [16] states the above result for formulas and for circuits but the proof establishes it only for circuits. We supply the missing step in Section 6. Other models of learning are considered in [16] as well, namely exact learnability from membership and equivalence queries. We omit them here, but note that our proof shows that the corresponding results of [16] also hold for formulas, and not just for circuits. A finer question is whether, in the positive cases, the number of examples can be made attribute-efficient [39]: polynomial in s, 1/ε, 1/δ and log n rather than in n (note that log n is the information theoretic content in bits of a single propositional variable). For the conjunctive and disjunctive bases this holds, as follows from Theorem 1.2 above. For the affine bases the target is a parity of at most s variables, and whether such parities can be learned attributeefficiently in polynomial time is a well-known open problem [36, 13]. The above results also yield a complete picture for agnostic learning [31], where we don’t assume that the labels are given by a target in the class: here, the examples are drawn from an arbitrary distribution D on {0, 1}n × {0, 1}, and the learner must output a hypothesis whose error under D exceeds the least error optD of any n-ary PLO -formula by at most ε. Note that, since there is no target, the bound for the running time and sample size is in n, 1/ε and 1/δ. The learner is proper if the hypothesis is a PLO -formula, and it is a weak agnostic learner if it is required to work only when optD ≤ ε, and then only to reach error ≤ 1/2 − δ, for some fixed ε, δ > 0. Every weak agnostic learner yields a randomized weak approximator for ERM, by running it on the uniform distribution over a given sample. Conversely, when the VC dimension of PLO is polynomial in n, every polynomial-time ERM algorithm yields a proper agnostic learner, by uniform convergence; and polynomial VC dimension is in fact necessary for weak agnostic learning, even improper [47]. It follows from Theorem 1.3 and Proposition 1.4 that PLO is properly agnostically learnable in polynomial time when O ⪯ {¬, ⊤, ⊥}; that in the three intervals of regime (i) of Theorem 1.3 it is not properly weak agnostically learnable in polynomial time, unless NP = RP; and that for every other basis it is not weak agnostically learnable at all, properly or not, for VC dimension reasons (cf. Proposition 1.4). Finally, a further variant of the PAC model deserves discussion. Under random classification noise each label shown to the learner is flipped independently with a fixed probability η < 1/2 [6]. The usual route to learning algorithms that are tolerant to such noise is Kearns’s statistical query model, in which the learner sees no examples at all but may ask for the probability, under the example distribution, of any polynomial-time predicate of an example and its label, and receives it to within a tolerance of its choosing. A class learnable from polynomially many such queries of inverse-polynomial tolerance is PAC learnable under random classification noise of any rate η < 1/2 [28]. Both notions are made precise in Section 8. Theorem 1.6 (Statistical queries, from [28, 9]). Let O be a finite basis. Under the cryptographic assumptions of Section 6, PLO is efficiently learnable from statistical queries if and only if O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {¬, ⊤, ⊥}. The same holds for CIRO . For random classification noise itself the picture is incomplete. Specifically, for the affine cases {⊕3 } ⪯ O ⪯ {⊕, ⊤, ⊥} the question is open — it is known as the learning parity with noise problem [10]. Figure 1 collects these classifications. It depicts Post’s lattice. Its elements are all Boolean clones, which we can think of as the equivalence classes of the pre-order ⪯. They are colored to reflect the status of the clones in question with respect to the classifications above. In this paper we focus on problems where a formula is to be derived from examples. For the converse direction, where a formula is given and a meaningful sample is to be generated for

it — for instance one that characterizes the formula up to equivalence within the fragment — dichotomy results over Post’s lattice exist as well, cf. [8]. The above results apply to fragments that are generated by sets of connectives, and that are for that reason closed under substitution. This excludes fragments such as Horn CNF, obtained by restricting the shape of clauses rather than the supply of connectives. Section 9 recalls Boolean constraint languages as the standard way of defining such fragments and records what becomes of the questions above when fragments are defined this way.

Organization Section 2 fixes notation, including the two size measures and the table of clones. Section 3 treats fitting and Section 4 empirical risk minimization. Section 5 then treats the VC dimension, Section 6 PAC learning, Section 7 Occam algorithms, and Section 8 learning under random classification noise and from statistical queries. Section 9 compares this picture with the one obtained when fragments are given by constraint languages instead.

Acknowledgements I am grateful to Victor Dalmau and Peter Mayr for fruitful discussions. Claude Fable was used in the process of writing this paper, both editorially and as a tool in the creative process. Several of the technical results were obtained with its help.

Preliminaries: Formulas, Circuits, Clones

A basis is a finite set O of Boolean functions, each of fixed arity. A PLO -formula over the variables x1 , . . . , xn is a finite tree whose leaves are labeled by variables and whose internal nodes of arity r are labeled by r-ary members of O; we write PLO for the class of these formulas, and [φ] for the Boolean function computed by φ. A CIRO -circuit is the same object with fan-out allowed to exceed one, so that a subcomputation may be shared; we write CIRO for this class. A clone is a set of Boolean functions that contains all projections (x1 , . . . , xn ) 7→ xi and is closed under composition. For a set O of Boolean functions, [O] denotes the clone generated by O, the least clone containing O; it consists of the functions computed by PLO -formulas, or equivalently by CIRO -circuits. A finite set O with [O] = C is a basis of the clone C. Post [43] determined all Boolean clones: there are countably many, each has a finite basis, and ordered by inclusion they form Post’s lattice, drawn in Figure 1. For finite bases O, O′ , write O ⪯ O′

⇐⇒

[O] ⊆ [O′ ],

and write O ≡ O′ when the two generated clones are equal. Order {0, 1}n coordinatewise, so that a ≤ a′ means ai ≤ a′i for every i. Write 0 and 1 for the all-zero and the all-one tuple, and ā for the bitwise complement of a, that is, āi = 1 − ai . The upward closure of a set A ⊆ {0, 1}n consists of the points above some member of A; a set equal to its upward closure is an upset, and downward closure and downset are defined dually. We write ⊕3 for the ternary parity operation ⊕3 (x, y, z) = x ⊕ y ⊕ z, and f d for the dual of a function f , defined by f d (a) = ¬f (ā), and a function equal to its own dual is self-dual. We use the standard notation for Post’s lattice, as in [12, 38]. Table 1 lists the clones, with a description and a basis for each. The list is complete [43, 38]. An asterisk abbreviates a family of clones sharing a letter: R∗ denotes R0 , R1 , R2 , and M∗ , L∗ , E∗ , V∗ , N∗ , I∗ and D∗ likewise denote the clone named by the letter together with all of its subscripted variants, so that M∗ is M, M0 , M1 , M2 and L∗ is L, L0 , L1 , L2 , L3 . On the separating side S0∗ denotes S0 , S02 , S01 , S00 and S1∗ denotes S1 , S12 , S11 , S10 , with Sk0∗ and Sk1∗ the corresponding degree-k families. 5

BF R1

R0 R2

M M1 M2

S20 S30

S202

S201

Sn0

S302

S301

S200

Sn02

Sn01

S300

S02

S01

S21

D D1

Sn00

S211

S212

S31

S210

S311

S312

Sn1

S310

Sn11

Sn12

S11

S12

Sn10

S00

S10 V

L V0

E L0

region I

region II

E0 E2

region III region IV region V I I1

I0 I2

I II III IV V

Clones

ERM

VC dim.

PAC

Occam

N∗ , I∗ E∗ , V∗ L∗ Sk0∗ , Sk1∗ (k ≥ 2), D2 BF, R∗ , M∗ , S0∗ , S1∗ , D, D1

P no weak approximator no weak approximator NP-hard, k-approximable P

linear linear linear exponential exponential

yes yes yes no no

yes yes yes none none

yes yes no no no

Figure 1: Post’s lattice, coloured by the regions the classifications cut it into, with the status of each problem per region. Fitting is omitted from the table because it is in P for every basis, with a fitting formula of polynomial size (Theorem 1.1). The Occam algorithms of regions I and II are attribute-efficient, that of region III is not known to be. Under random classification noise the last column is unchanged except in region III, where the question is open (Section 8). In region IV the k-approximation is optimal under the Unique Games Conjecture. The negative entries in the last three columns hold under the cryptographic assumptions of Section 6, except that in region III the entry of the last column is unconditional. Dashed edges abbreviate the infinite ascending families Sk0∗ and Sk1∗ .

Clone

Description

Representative basis

BF R0 R1 R2

all Boolean functions 0-preserving, i.e. f (0) = 0 1-preserving, i.e. f (1) = 1 R0 ∩ R 1

{∧, ¬} {∧, ⊕} {→, ∧} {∨, x ∧ (y ↔ z)}

M M0 M1 M2

monotone M ∩ R0 M ∩ R1 M ∩ R2

{∧, ∨, ⊥, ⊤} {∧, ∨, ⊥} {∧, ∨, ⊤} {∧, ∨}

S0 S02 S01 S00 Sk0 Sk02 Sk01 Sk00

0-separating S0 ∩ R2 S0 ∩ M S0 ∩ R2 ∩ M 0-separating of degree k Sk0 ∩ R2 Sk0 ∩ M Sk0 ∩ R2 ∩ M

{→} {x ∨ (y ∧ ¬z)} {x ∨ (y ∧ z), ⊤} {x ∨ (y ∧ z)} {→, thk+1 } 2 {x ∨ (y ∧ ¬z), thk+1 } 2 k+1 {x ∨ (y ∧ z), ⊤, th2 } {x ∨ (y ∧ z), thk+1 } 2

S1 S12 S11 S10 Sk1 Sk12 Sk11 Sk10

1-separating S1 ∩ R2 S1 ∩ M S1 ∩ R2 ∩ M 1-separating of degree k Sk1 ∩ R2 Sk1 ∩ M Sk1 ∩ R2 ∩ M

{x ∧ ¬y} {x ∧ (y ∨ ¬z)} {x ∧ (y ∨ z), ⊥} {x ∧ (y ∨ z)} {x ∧ ¬y, thk+1 } k {x ∧ (y ∨ ¬z), thk+1 } k {x ∧ (y ∨ z), ⊥, thk+1 } k } {x ∧ (y ∨ z), thk+1 k

D D1 D2

self-dual D ∩ R2 D∩M

{maj, ¬} {maj(x, y, ¬z)} {maj} = {th32 }

L L0 L1 L2 L3

affine L ∩ R0 L ∩ R1 L ∩ R2 L∩D

{⊕, ⊤} {⊕} {↔} {⊕3 } {x ⊕ y ⊕ z ⊕ ⊤}

E E0 E1 E2

conjunctions and constants E ∩ R0 E ∩ R1 E ∩ R2

{∧, ⊥, ⊤} {∧, ⊥} {∧, ⊤} {∧}

V V0 V1 V2

disjunctions and constants V ∩ R0 V ∩ R1 V ∩ R2

{∨, ⊥, ⊤} {∨, ⊥} {∨, ⊤} {∨}

N N2

projections, negations and constants projections and negations

{¬, ⊥, ⊤} {¬}

I I0 I1 I2

projections and constants I ∩ R0 : projections and ⊥ I ∩ R1 : projections and ⊤ projections only

{⊥, ⊤} {⊥} {⊤} ∅

Table 1: The Boolean clones, with a basis for each; k ranges over the integers k ≥ 2. The bases follow those tabulated by Böhler, Creignou, Reith and Vollmer [12], up to inessential variation, and each is one choice among many.

The convention for the S-families is the following. A Boolean function is 0-separating if the set f −1 (0) has a common zero coordinate; it is 0-separating of degree k if every list of k elements of f −1 (0), with repetitions allowed, has a common zero coordinate. Equivalently, every nonempty subset of at most k distinct zero inputs has a common zero coordinate. The 1-separating notions are dual. For a formula φ we write size(φ) for its number of nodes and depth(φ) for its depth, with a single leaf having depth 0. For a circuit C, size(C) is its number of gates and inputs. Unfolding a circuit into a formula can increase size exponentially — indeed for O = {∧, ∨, ⊤, ⊥}, CIRO circuits are super-polynomially more succinct than PLO -formulas [26, 44] — and no converse blow-up is possible, so circuit size is the more generous measure: a statement proved for it is weaker than the corresponding one for formula size when it asserts hardness, and stronger when it asserts an upper bound. In certain cases circuits can nevertheless be translated to formulas in polynomial time. If [O] ⊆ E, [O] ⊆ V or [O] ⊆ L, the n-ary functions of [O] are the conjunctions, the disjunctions or the affine functions of the variables, together with whichever truth constants the clone contains. Which of them a given CIRO -circuit computes is read off from its values at n + 1 points, and the corresponding PLO -formula has at most n + 2 leaves.

Fitting

Fix a finite set of propositional variables x1 , . . . , xn , identified with the coordinates [n] = {1, . . . , n}, and write x = (x1 , . . . , xn ) for the tuple of them. A labeled sample is a finite multiset E ⊆multi {0, 1}n × {0, 1}, which we also write as a list (a1 , b1 ), . . . , (am , bm ) of labeled examples. A formula φ ∈ PLO fits E if φ(aj ) = bj for j = 1, . . . , m, and E is realizable for PLO if some φ ∈ PLO fits it. The fitting problem for PLO asks, given E, to decide whether E is realizable and, if so, to return a fitting formula. The same definitions apply also to CIRO . Note that a labeled sample is realizable for PLO iff it is realizable for CIRO . Since this depends on O only through [O], we also say that E is realizable in the clone [O]. The fitting problem has an algebraic form that is well studied in the literature, and we lift our terminology to it. A finite algebra A = (A; F ) is a finite set A together with a finite set F of finitary operations on A. Terms over F are built from variables and the operations of F in the usual way, and a term τ (x1 , . . . , xn ) induces an n-ary term operation τ A on A; for A = ({0, 1}; O) the terms are the PLO -formulas and the term operations are the functions of [O]. A labeled sample over A consists of examples (aj , bj ) ∈ An × A, a term τ fits it if τ A (aj ) = bj for every j, and it is realizable if some term fits it. Read columnwise, fitting asks whether the column of labels lies in the subalgebra of Am generated by the columns of the variables. This is the subpower membership problem for A, the subject of [40, 14], whose complexity is open in general. A near-unanimity operation of arity d ≥ 3 is one returning x whenever at least d − 1 of its arguments are x, and a near-unanimity term of A is a term inducing such an operation; on {0, 1} the majority operation and the thresholds thk+1 and thk+1 are examples 2 k of near-unanimity operations. The Baker–Pixley theorem [7] solves the subpower membership problem for algebras with a near-unanimity term. We need a slight strengthening of this result. Proposition 3.1 (Efficient Baker–Pixley interpolation). Fix a finite algebra A with a nearunanimity term ν of arity d ≥ 3, and let k = d − 1. 1. A labeled sample E over A is realizable if and only if every E ′ ⊆ E with |E ′ | ≤ k is, which can be tested in polynomial time. 2. From a realizable labeled sample E one can moreover compute in polynomial time a fitting term of depth logarithmic in |E|. 8

Proof. Item 1 is the content of the classic Baker–Pixley theorem [7]. We prove both items here, with a slight refinement of the classic argument: we use a divide-and-conquer strategy to control the size and depth of the constructed term. Let E be a labeled sample over A, consisting of the labeled examples (a1 , b1 ), . . . , (am , bm ) ∈ An × A. By a window we mean a subset S ⊆ [m], and we write E|S for the sub-sample {(aj , bj ) : j ∈ S}, so that the sub-samples E ′ ⊆ E of item 1 are the E|S with |S| ≤ k. If E is realizable then so is every sub-sample, by the same term; this is the easy direction of item 1. Fix a window S with |S| ≤ k. Every term induces a labeling of the points aj , j ∈ S, that is, an element of AS , and the labelings so induced are obtained from those induced by the variables x1 , . . . , xn by closing under the operations of F , applied pointwise. There are at most |A|k labelings of these points altogether, so at most |A|k of the variables induce distinct ones, the closure is reached in a bounded number of rounds, and every labeling in it is induced by a term of bounded size, the bound depending only on A. Hence, in time O(n) plus a constant depending on A, we can test whether a term fitting E|S exists and, if so, compute one of bounded size, which we call τS . There are O(mk ) windows with |S| ≤ k, so all of this takes O(mk n) time. Suppose now that for every window S with |S| ≤ k a fitting term τS exists. We extend the definition of τS to every window S ⊆ [m] by recursion on |S|, in such a way that τS fits E|S . If |S| > k then |S| ≥ d. Partition S into d nonempty blocks B1 , . . . , Bd whose sizes differ by at most one, and let τS := ν τS\B1 , . . . , τS\Bd . Each S \ Bi is a proper subset of S, so the recursion terminates, and by induction τS fits E|S : an index j ∈ S lies in exactly one block Bi , so the d − 1 arguments τS\Bi′ with i′ ̸= i take the value bj at aj , and the near-unanimity operation ν A returns that value whatever the remaining argument computes there. Hence τ[m] fits E. In particular a sample all of whose sub-samples of at most k examples are realizable is realizable, which completes the proof of item 1. It remains to show that the construction runs in polynomial time and that τ[m] has depth logarithmic in m. If |S| = s > k then every block has at least ⌊s/d⌋ elements, so |S \ Bi | < (1 − 1/d)s + 1, which is at most (1 − 1/2d) s once s ≥ 2d. The recursion therefore has depth O(log m), with a constant depending only on d. Each level of the recursion contributes the depth of ν, and the terms at the bottom have bounded depth, so τ[m] has depth O(log m). The recursion tree has dO(log m) = mO(1) nodes, and the term built at a node has size at most size(ν) times one plus the sizes of its arguments, so sizes grow by at most a factor (d + 1) size(ν) per level and every term involved, τ[m] included, has size mO(1) . The construction therefore runs in polynomial time. Theorem 1.1 (Fitting). Let O be a fixed finite basis. Then PLO has a polynomial-time fitting algorithm: given a labeled sample it decides whether the sample is realizable, and if so returns a fitting PLO -formula of polynomial size. The same holds for CIRO . Proof of Theorem 1.1. Let C = [O]. Since O is fixed, we may freely replace a fixed operation of C by a fixed PLO -formula defining it. The following table places every clone of Post’s lattice in one of five cases; a clone may satisfy several, and only coverage is needed. Case

Clones

(1) (2) (3) (4) (5)

BF, R∗ , M∗ , D∗ , and Sk0∗ , Sk1∗ for every k ≥ 2 L∗ N∗ , I∗ E∗ , V∗ S0∗ , S1∗ 9

(1) C has a near-unanimity term. This includes BF, R∗ , M∗ , D, D1 and D2 , all of which contain maj = th32 , and the clones Sk0∗ and Sk1∗ , which contain thk+1 respectively thk+1 2 k . Proposition 3.1, applied to the algebra ({0, 1}; O), decides fitting and in the positive case returns a fitting PLO -formula of polynomial size and logarithmic depth. L (2) C ⊆ L. The n-ary functions of C are the affine functions c ⊕ j∈J xj whose constant c and support J satisfy the at most two linear conditions over F2 that single out C among L, L0 , L1 , L2 and L3 : that c = 0, that c ⊕ |J| ≡ 1, or that |J| be odd. Fitting is therefore a system of linear equations over F2 in the unknowns c and the indicator vector of J, with one equation per example and those conditions, which Gaussian elimination solves in polynomial time. A solution is written as a chain of connectives of O over the variables of J, a PLO -formula with at most n + 2 leaves. (3) O ⪯ {¬, ⊤, ⊥}. This is the essentially unary case. One tries the finitely many available unary functions on each variable, together with the available truth constants. (4) O ⪯ {∧, ⊤, ⊥} or O ⪯ {∨, ⊤, ⊥}. This is the semilattice case. For conjunctions the standard greedy construction applies: keep exactly those variables whose columns are compatible with all positive labels and take their conjunction, with the appropriate truthconstant side conditions for proper subclones. Disjunctions are dual. (5) It remains to handle the ordinary separating clones. We give the argument for the 1separating side; the 0-separating side follows by duality. For C ∈ S1∗ , let KC be given by C S1 S12 S11 S10 KC BF R1 M M ∩ R1 . Write gi ∈ {0, 1}m for the column of values of the variable xi on the sample and b = (b1 , . . . , bm ) for the column of labels. Every f ∈ C is bounded above by one of its inputs. Hence a necessary condition for fitting is that some variable column gi dominates the label column b. If no such column exists, reject. Otherwise, choose any such i, discard the rows on which gi = 0, and set xi = 1 in the remaining rows. If the original sample has a C-fit f , then f |xi =1 belongs to KC and fits this residual sample. Conversely, if u ∈ KC fits the residual sample, then xi ∧ u belongs to C and fits the original sample. All four clones KC contain the majority operation, so item (1) decides the residual problem and constructs a residual formula of polynomial size and logarithmic depth. To translate this formula back to the original basis, fix a basis BC of KC and, for each γ ∈ BC , use the guarded gate γ b(x, z) = x∧γ(z). This operation belongs to C and therefore has a fixed PLO -formula. Replacing each residual connective by this fixed formula, and each variable y by a fixed PLO -formula for xi ∧y, maintains the invariant that the translated node computes xi ∧ u. Each substitution multiplies size by at most a constant per level, and the depth is logarithmic, so the result is a PLO -formula of polynomial size. For the canonical basis f∧∨ (x, y, z) = x ∧ (y ∨ z) of S10 , the gadgets for a guarded leaf, disjunction, and conjunction are respectively f∧∨ (xi , y, y), f∧∨ (xi , u, v) and f∧∨ (u, v, v), where u, v are already guarded. For f∧→ (x, y, z) = x ∧ (y → z), a basis of S12 , the corresponding gadgets are f∧→ (xi , xi , y), f∧→ (xi , u, v) for implication and f∧→ (u, u, v) for conjunction. The bases of the four residual clones also contain truth constants, and these need guarded gates of their own. We have KS10 = M ∩ R1 = M1 , with basis {∨, ∧, ⊤}, and KS11 = M = [{∨, ∧, ⊥, ⊤}]. The guarded gates for the constants are b ⊤(x) = x ∧ ⊤ = x,

b ⊥(x) = x ∧ ⊥ = ⊥,

both of which lie in C and satisfy the invariant. For KS12 = R1 the two gadgets above suffice, {→, ∧} being the basis of R1 in Table 1. For KS1 = BF take the basis {∧, ¬}, whose guarded gates are x ∧ (y ∧ z) and x ∧ ¬y, both of which lie in S1 . The dual construction handles the ordinary 0-separating clones. With dual cases folded in, the table above shows these cases to be exhaustive, giving a polynomial-time construction of a fitting PLO -formula of polynomial size whenever fitting is possible. A formula is a circuit of the same size, so the statement for CIRO follows.

Empirical risk minimization

The empirical risk of a formula φ on a labeled sample E is the fraction of misclassified examples, errE (φ) =

|{(a, b) ∈ E : φ(a) ̸= b}| , |E|

and the empirical risk minimization problem for PLO , ERM for PLO for short, asks for a formula attaining the optimal value: given E, return a φ ∈ PLO with errE (φ) = optO (E) := min errE (ψ). ψ∈PLO

The sample size is fixed within an instance, so minimizing this fraction is the same as minimizing the number of mistakes, and the arguments below count mistakes where that is more convenient. The associated decision problem asks, given E and t, whether there exists φ ∈ PLO with at most t mistakes. Since the hypothesis is part of the output, the problem depends on how that hypothesis may be written, and we distinguish two versions: ERM for PLO , where the algorithm returns a PLO -formula, and ERM for CIRO , where it may return a CIRO -circuit. The optimum value optO (E) is the same in both, since PLO and CIRO define the same functions; only the output differs. The same distinction applies to the weak approximators of the introduction and to the approximation algorithms below. This section proves the classification from the introduction, which we restate. Theorem 1.3 (Empirical risk minimization). Let O be a finite basis of Boolean functions. The ERM problem for PLO falls into one of the following three regimes. (i) If {∧} ⪯ O ⪯ {∧, ⊤, ⊥},

{∨} ⪯ O ⪯ {∨, ⊤, ⊥},

{⊕3 } ⪯ O ⪯ {⊕, ⊤, ⊥},

k+1 {thk+1 k } ⪯ O ⪯ {x ∧ ¬y, thk },

For circuits it is clear that the problem depends on O only through the clone [O]: if [O] = [O′ ] then every member of O′ is computed by some fixed CIRO -circuit, so replacing each gate turns a CIRO′ -circuit into a CIRO -circuit of size larger by at most a constant factor, and symmetrically. For formulas no such translation is known in general, so the basis, and not merely the clone, could in principle matter. Nevertheless the theorem shows that the complexity of ERM for PLO too depends only on [O]. The explanation lies in Theorem 1.1, which shifts the algorithmic content of the problem from formulas to relabelings of the sample. A relabeling of a labeled sample E assigns a label to every point of {0, 1}n that occurs in E. It is realizable in a clone C if some function of C takes the assigned value at every sample point. Its mistakes on E are the examples (a, b) ∈ E whose label b differs from the label assigned to a, and its empirical risk is the fraction of mistakes, as for formulas. Every formula in PLO or circuit in CIRO induces, by evaluation at the sample points, a relabeling realizable in [O] with the same mistakes. Conversely, a relabeling realizable in [O], read as a labeled sample, is realizable for PLO , so Theorem 1.1 computes from it in polynomial time a PLO -formula, or a CIRO -circuit, with exactly those mistakes. Hence ERM for PLO and ERM for CIRO are both equivalent, in polynomial time and with every approximation ratio preserved, to what we call ERM for the clone C = [O]: given E, find a relabeling of E that is realizable in C and has the fewest mistakes. We write optC (E) for the least empirical risk of such a relabeling, so that optC (E) = optO (E) for every basis O of C, and the notions of α-approximation and of weak approximator carry over verbatim, with a realizable relabeling in place of the formula returned. The rest of the section treats ERM for clones: the algorithms return realizable relabelings, and the hardness results bound the mistakes of every function of the clone on the samples they construct. No basis appears anywhere, which is why the classification depends on O only through [O] and holds for formulas and circuits alike, as the final clause of the theorem asserts. We prove the theorem region by region, keeping algorithms, hardness results and approximation guarantees for a region together; the standard enumeration of Post’s lattice shows that the families considered below are exhaustive [43, 38]. In clone names, the interval in regime (ii) ∈ C ⊆ Sk1 , using the bases for Sk0 and Sk1 from Table 1; by ∈ C ⊆ Sk0 , or dually thk+1 is thk+1 2 k inspection of Post’s lattice [43, 38], the clones in these intervals are exactly the eight degree-k separating clones Sk0∗ and Sk1∗ , together with the majority clone D2 = [maj] = [th32 ] when k = 2. Two conventions are used throughout. First, we freely use weighted examples, that is, repeated ones. Given a labeled sample E, for each point a ∈ {0, 1}n let m+ (a) = #{(a, 1) ∈ E},

m− (a) = #{(a, 0) ∈ E}.

A relabeling that assigns 1 to a makes m− (a) mistakes there, and one that assigns 0 makes m+ (a), so ERM for a clone is a weighted labeling problem on the finite set of sample points. Conversely, weights can be imposed by repetition: if W > |E| and we add W copies of (a, b), then every optimal relabeling of the enlarged instance assigns b to a, provided some relabeling realizable in the clone satisfies all the imposed labels. Weight W always abbreviates W repeated copies, and this large-penalty forcing is how boundary conditions are imposed below. Second, an algorithm is an α-approximation for ERM for C if it returns a relabeling realizable in C of empirical risk at most α · optC (E). This multiplicative guarantee differs both from an additive one, optC (E)+ε, and from weak approximation. The trivial baseline behind weak approximation presumes the truth constants, which clones such as E2 = [∧] and L2 = [⊕3 ] lack. This weakens nothing, since the constant-adjunction reduction below supplies them without changing the sample size or the empirical risk. We begin with that reduction, which lets the truth constants be assumed available. For a clone C, let C± be the clone generated by C together with ⊤ and ⊥. Lemma 4.1. For every clone C, ERM for C± reduces in polynomial time to ERM for C. More precisely, from a sample E one constructs in polynomial time a sample E ′ with |E ′ | = |E| whose 12

relabelings realizable in C correspond bijectively, with the same mistakes, to the relabelings of E realizable in C± . Proof. Let E be a sample over the variables x1 , . . . , xn . Introduce two fresh variables z0 , z1 , and replace every labeled example (a, b) by the extended example (a′ , b) with a′ (xi ) = a(xi ),

a′ (z0 ) = 0,

a′ (z1 ) = 1.

Call the transformed sample E ′ . The map a 7→ a′ is a bijection between the points of E and those of E ′ , so relabelings of E correspond to relabelings of E ′ with the same mistakes, and it remains to see that this correspondence respects realizability. Every function of C± is obtained by composing functions of C, projections and the two constants. Replacing each occurrence of ⊥ and ⊤ by z0 and z1 turns an n-ary such function f into an (n + 2)-ary function g ∈ C with f (x) = g(x, 0, 1), and conversely every function of this form lies in C± . Since g(a′ ) = g(a, 0, 1), a relabeling of E is realized in C± by g(x, 0, 1) if and only if the corresponding relabeling of E ′ is realized in C by g. Thus, adjoining constants cannot make ERM harder. On the other hand, adjoining constants can make ERM easier: as we will see, ERM for D2 is NP-hard, while D± 2 = M is tractable by Proposition 4.10 — so the lemma transfers hardness only downward, from C± to C.

4.1

The inapproximable cases

Each of the two results below concerns the clone at the top of one of the three intervals of regime (i), which is where its source leaves it; the passage to the smaller clones of an interval is uniform and is deferred to Section 4.4. Theorem 4.2 (Håstad [23]). Unless P = NP, there is no polynomial-time weak approximator for the clone L = [⊕, ⊤, ⊥]. L The functions of L are those of the form h(x) = c ⊕ j∈J xj , and the theorem is Håstad’s gap hardness for Max-E3Lin read through the standard translation between linear systems and parity examples. His theorem says that, for every η > 0, it is NP-hard to distinguish systems of three-variable linear equations over F2 for which some assignment satisfies at least a 1 − η fraction of the equations from systems in which every assignment satisfies at most a 1/2 + η fraction [23]. Since the equations have odd arity, complementing all variables turns satisfied equations into unsatisfied ones, so in the second case every assignment also satisfies at least a 1/2 − η fraction. Translate such a system into labeled parity examples in the standard way: an equation a · z = b becomes the example with coordinate vector a and label b. An assignment z is then the linear parity h(x) = x · z, whose value on that example is a · z, and an optional affine offset corresponds to complementing all predictions. The translation therefore gives samples for which either some affine hypothesis has empirical risk at most η, or every affine hypothesis has empirical risk at least 1/2 − η. Given δ, ε > 0, choose η < min{δ, ε}: a weak approximator with these constants would separate the two cases. Theorem 4.3 (Feldman, Gopalan, Khot and Ponnuswami [21]). Unless P = NP, there is no polynomial-time weak approximator for the clone E = [∧, ⊤, ⊥], nor for the clone V = [∨, ⊤, ⊥]. For E = [∧, ⊤, ⊥] this is the monotone case of the agnostic-learning hardness of [21], whose proof does not pass through Håstad’s but goes back to the PCP theorem through Feige’s multiprover proof system for 3SAT-5, precisely in order to avoid an intermediate optimization problem. One point of care: their monomials are conjunctions of literals, whereas E contains only monotone conjunctions and the two truth constants. The result we need is therefore the monotone version, which they prove alongside the general one — it is their problem MMon-MA, 13

treated in [21, §4.2.2 and Theorem 15]. In the terminology used here it says that, unless P = NP, no polynomial-time algorithm is a weak approximator for the class of monotone conjunctions. The clone V = [∨, ⊤, ⊥] satisfies the same statement by Boolean duality: complement all coordinates and flip all labels.

4.2

Finite-degree separating clones and the majority clone

Regime (ii) consists of the finite-degree separating clones and, as the case k = 2, the majority clone. Fix k ≥ 2. The proofs treat the 0-separating side, and the 1-separating side follows by duality: each clone Sk1∗ consists of the duals f d of the functions f of the clone Sk0∗ with the same subscript, and f d makes on the sample E d = {(ā, 1−b) : (a, b) ∈ E} the same number of mistakes as f on E, so ERM for a 1-separating clone is ERM for its dual clone with all coordinates complemented and all labels flipped. By the zero set of a function f : {0, 1}n → {0, 1} we mean the set f −1 (0). Fact 4.4 (Zero-set criterion). For Z ⊆ {0, 1}n , some function of Sk0 has zero set exactly Z if and only if every nonempty subset of Z of size at most k has a common zero coordinate. This is a restatement of the separating condition of Section 2. The algorithm is obtained by the technique of Hochbaum [25] for weighted vertex cover: write the problem as an integer linear program, solve its linear relaxation, and round every variable of value at least 1/k up to 1 and every other variable down to 0. The following lemma will justify the rounding step. It is stated separately as it is used in two proofs. Lemma 4.5 (Rounding). Let k ≥ 2 be fixed. Consider an integer program with variables xv ∈ {0, 1} for v ∈ V , whose objective is to minimize X cv xv + dv (1 − xv ) v∈V

with P coefficients cv , dv ≥ 0, and whose constraints are of three kinds: covering constraints v∈T xv ≥ 1 for sets T ⊆ V with |T | ≤ k, precedence constraints xv ≤ xw , and fixed variables xv = 0 or xv = 1. If the program is feasible, then a feasible solution of cost at most k times the optimum can be found in polynomial time. Proof. Relax the integrality requirement to xv ∈ [0, 1], solve the resulting linear program in polynomial time, and let x be an optimal solution; its cost is at most the optimum of the integer program. Round x to the 0/1-assignment x̂ with x̂v = 1 if xv ≥ 1/k and x̂v = 0 otherwise. The rounded assignment satisfies all constraints. In a covering constraint, at most k variables sum to at least 1, so one of them has value at least 1/k and is rounded to 1. If xv ≤ xw then x̂v ≤ x̂w . And a fixed variable is unchanged by rounding. For the cost, compare termwise. If x̂v = 1 then xv ≥ 1/k, so x̂v ≤ k xv ; and if x̂v = 0 then k xv < 1/k, so 1 − x̂v = 1 ≤ k−1 (1 − xv ). Each inequality is trivial in the other case. Hence k the cost of x̂ is at most max{k, k−1 } times the cost of x, and that maximum is k for every k ≥ 2. Proposition 4.6 (k-approximation). Let k ≥ 2 and let C be one of the eight degree-k separating clones Sk0∗ and Sk1∗ , that is, Sk00 ⊆ C ⊆ Sk0 or Sk10 ⊆ C ⊆ Sk1 . Then ERM for C admits a polynomial-time k-approximation on arbitrary samples. Proof. By duality we may assume Sk00 ⊆ C ⊆ Sk0 . We write ERM for C as an integer program of the form in Lemma 4.5. For each distinct sample point a introduce a variable xa ∈ {0, 1}, with xa = 1 meaning that a is relabeled 1, so that the number of mistakes of the relabeling is X xa m− (a) + (1 − xa ) m+ (a) . a

P Impose a covering constraint a∈T xa ≥ 1 for every nonempty set T of at most k sample points without a common zero coordinate; when C ⊆ M, a precedence constraint xa ≤ xa′ for all sample points a ≤ a′ ; and when C ⊆ R2 , the fixed variable x0 = 0, if 0 is a sample point. Since k is fixed, the program has polynomial size. Note that x1 = 1 is among the covering constraints whenever 1 is a sample point, as 1 has no zero coordinate. The 0/1-assignments satisfying these constraints are exactly the relabelings of E realizable in C. If a relabeling is realized by f ∈ C, then its points relabeled 0 lie in the zero set of f , which satisfies the degree-k condition by the zero-set criterion, so no set T as above consists of points relabeled 0, and the covering constraints hold; when C ⊆ M, the zero set of the monotone f is a downset, which gives the precedence constraints; and when C ⊆ R2 , f (0) = 0 gives x0 = 0. Conversely, let x be a 0/1-assignment satisfying the constraints, and let Z be the set of sample points with xa = 0. Let Z ′ be Z itself, or its downward closure in {0, 1}n when C ⊆ M, in either case with 0 added when C ⊆ R2 . By the covering constraints every nonempty subset of Z of size at most k has a common zero coordinate, and this passes to Z ′ , since a coordinate that is zero on a point is zero on every point below it, and since 0 is zero in every coordinate; so by Fact 4.4 some function f of Sk0 has zero set exactly Z ′ . When C ⊆ M this f is monotone, its zero set being a downset, and when C ⊆ R2 it satisfies f (0) = 0 and f (1) = 1, as 0 ∈ Z ′ while 1, having no zero coordinate, is neither in Z nor below a point of Z; so f ∈ C. Finally f induces the relabeling x: it is 0 on Z, and a sample point a with xa = 1 lies outside Z ′ , since a∈ / Z, since a ≤ z with z ∈ Z would violate the precedence constraint xa ≤ xz = 0, and since a = 0 would violate x0 = 0. The program is feasible, because the projection onto the first coordinate lies in every clone and realizes some relabeling of E, and its optimum is |E| · optC (E). Lemma 4.5 therefore returns in polynomial time a 0/1-assignment satisfying the constraints, that is, a relabeling of E realizable in C, with at most k · |E| · optC (E) mistakes. We handle the majority clone D2 = [maj] separately, as the approach of Proposition 4.6 does not go through for it. In terms of variables xa for the labels of the sample points, membership in D2 imposes, besides precedence constraints, the constraints xa + xa′ ≤ 1 for all sample points with a′ ≤ ā: if f (a) = f (a′ ) = 1 for such points then monotonicity gives f (ā) = 1, contradicting self-duality. Such packing constraints do not survive the rounding of Lemma 4.5, which may round both variables up. We therefore change variables, and let a variable record whether the relabeling gives up the majority label at a sample point, that is, the label occurring more often there; in these variables the constraints are covering constraints. Proposition 4.7 (2-approximation, majority case). ERM for D2 admits a polynomial-time 2-approximation on arbitrary samples. Proof. For each distinct sample point a let its majority label ba be 1 if m+ (a) ≥ m− (a) and 0 otherwise, and let µ(a) = |m+ (a) − m− (a)|. A relabeling makes min{m− (a), m+ (a)} mistakes at a if it assigns ba there, and µ(a) more if it does not. Since DP 2 ⊆ R2 , a relabeling realizable in D2 assigns 0 to 0 and 1 to 1, so its number of mistakes is B + µ(a), where the sum ranges over the sample points a ∈ / {0, 1} to which it does not assign ba , and where X B = m+ (0) + m− (1) + min{m− (a), m+ (a)} a∈{0,1} /

does not depend on the relabeling. Call two sample points a, a′ ∈ / {0, 1} conflicting if no function of D2 takes the value ba at a and ba′ at a′ , that is, if the labeled sample {(a, ba ), (a′ , ba′ )} is not realizable in D2 ; this can be decided in polynomial time by Theorem 1.1. If P is a set of sample points outside {0, 1}, no two of which conflict, then the labeled sample {(a, ba ) : a ∈ P } is realizable in D2 . Indeed, its sub-samples of two examples are realizable by assumption, and those of one example by a 15

projection, as a point a ∈ / {0, 1} has a coordinate equal to ba ; since maj is a near-unanimity term of D2 of arity 3, Proposition 3.1 with k = 2 gives the claim. Now introduce, for each distinct sample point a ∈ / {0, 1}, a variable ya ∈ {0, 1}, with ya = 1 meaning that the majority label is given up at a; impose the covering constraint ya + ya′ ≥ 1 for P every conflicting pair; and minimize a µ(a) ya . This is a program of the form in Lemma 4.5 with k = 2, and it is feasible, since setting every variable to 1 satisfies all constraints. Every f ∈ D2 gives a feasible assignment, namely ya = 1 exactly when f (a) ̸= ba : it is feasible because f witnesses that two points with ya = ya′ = 0 do not conflict, and its cost is the number of mistakes of f minus B. So the optimum of the program is at most |E| · optD2 (E) − B. Conversely, let y be a feasible 0/1-assignment and P the set of points with ya = 0. No two points of P conflict, so by the claim the labeled sample {(a, ba ) : a ∈ P } is realizable in D2 . Theorem 1.1 fits it in polynomial time, and evaluating the fitting formula at all sample points givesP a relabeling of E realizable in D2 that assigns ba to every a ∈ P , hence makes at most B + a µ(a)ya mistakes. The algorithm applies Lemma 4.5 to the program and returns the relabeling just described for the assignment obtained. Its number of mistakes is at most B + 2 |E| · optD2 (E) − B ≤ 2 |E| · optD2 (E). The matching lower bounds for all clones of the regime come from vertex cover. A k-uniform hypergraph is a pair H = (V, E) consisting of a finite set V of vertices and a set E of hyperedges, which are k-element subsets of V ; a graph is a 2-uniform hypergraph. A vertex cover of H is a set of vertices that meets every hyperedge, and τ (H) denotes the least size of a vertex cover. Theorem 4.8 (Vertex cover in k-uniform hypergraphs). Let k ≥ 2 be fixed, and consider minimum vertex cover in k-uniform hypergraphs. (a) It can be approximated within a factor k in polynomial time [25]. (b) √ It is NP-hard to approximate within k − 1 − ε for every ε > 0 when k ≥ 3 [20], and within 2 − ε when k = 2 [33, 34]. (c) Under the Unique Games Conjecture it is NP-hard to approximate within k − ε for every ε > 0 [35]. Part (a) is the case of Lemma 4.5 in which all constraints are covering constraints; we use only the lower bounds (b) and (c). ∈ Proposition 4.9 (Vertex cover reduces to ERM). Let k ≥ 2 and let C be a clone with thk+1 2 k , that is, one of the eight degree-k separating clones Sk and Sk , ∈ C ⊆ S C ⊆ Sk0 or thk+1 1 0∗ 1∗ k or D2 when k = 2. Then minimum vertex cover in k-uniform hypergraphs reduces to ERM for C in polynomial time, by a reduction that preserves the objective value and produces samples consisting of negative examples only, or of positive examples only on the 1-separating side. The same sample serves all clones of one side. Proof. By duality we may assume thk+1 ∈ C ⊆ Sk0 . Let H = (V, E) be a k-uniform hypergraph. 2 Call a set X ⊆ V hyperedge-free if no hyperedge is a subset of X. Since every hyperedge has exactly k vertices, a set of at most k vertices is hyperedge-free exactly when it is not itself a hyperedge. We create one point pv for every vertex v ∈ V . For every hyperedge-free X ⊆ V with |X| ≤ k, introduce a coordinate cX , and define pv (cX ) = 0

⇐⇒

v ∈ X.

Since k is fixed, the number of coordinates is polynomial in |V |. The construction has the following property: for every nonempty Y ⊆ V with |Y | ≤ k, {pv : v ∈ Y } has a common zero coordinate 16

⇐⇒

Y is not a hyperedge of H.

Indeed, a common zero coordinate of these points is a coordinate cX with Y ⊆ X. If one exists then Y is hyperedge-free, being a subset of the hyperedge-free set X, and if Y is hyperedge-free then cY is such a coordinate. Label every pv negatively. The two directions of the reduction are established for different clones: from a hypothesis in the largest clone Sk0 we extract a vertex cover whose size is its number of mistakes, and from a vertex cover we build a hypothesis with at most that many mistakes in Sk00 and, when k = 2, also in D2 . Since C ⊆ Sk0 contains Sk00 or is D2 , both directions apply to C. From hypotheses to covers. Let f ∈ Sk0 misclassify the examples indexed by Sf ⊆ V , so that the correctly classified examples are indexed by If = V \ Sf . Since {pv : v ∈ If } ⊆ f −1 (0) and f is 0-separating of degree k, every k points among these have a common zero coordinate. If some hyperedge e ∈ E were contained in If , then the k points {pv : v ∈ e} would have a common zero coordinate, contradicting the property above. Thus Sf meets every hyperedge, so Sf is a vertex cover of H, of size equal to the number of mistakes of f . From covers to hypotheses. Let S ⊆ V be a vertex cover, and put I = V \ S, which is hyperedge-free. Let Z be the downset of {0, 1}n generated by the points pv with v ∈ I, together with 0: Z = {q : q ≤ pv for some v ∈ I} ∪ {0}, and let f be the function with zero set Z. We check that f ∈ Sk00 . First, Z satisfies the degree-k condition. Any k points of Z are 0 or lie below points pv1 , . . . , pvr with v1 , . . . , vr ∈ I and r ≤ k. The set {v1 , . . . , vr } is a hyperedge-free subset of I, so the coordinate c{v1 ,...,vr } is zero on each pvi , hence on every point below one of them, and on 0. Here we use that a coordinate that is zero on a point is zero on every point below it, so that the degree-k condition passes from a set of points to the downset it generates. By the zero-set criterion, Fact 4.4, f ∈ Sk0 . Second, f is monotone, because its zero set is a downset. Third, f (0) = 0 because 0 ∈ Z, and f (1) = 1 because 1 ∈ / Z: every pv has the zero coordinate c{v} , a single vertex being hyperedge-free as k ≥ 2, and no point below a point with a zero coordinate is 1. So f ∈ Sk0 ∩ M ∩ R2 = Sk00 . Finally f (pv ) = 0 for every v ∈ I, so f makes at most |S| mistakes. It may make fewer, if some pv with v ∈ S happens to lie in Z, and that only helps. This direction produces a hypothesis in Sk00 , hence in each of the four clones Sk0∗ . From covers to hypotheses in D2 . Let k = 2, so that H is a graph, and let again S be a vertex cover and I = V \ S, which is now an independent set. We need f ∈ D2 with f (pv ) = 0 for all v ∈ I, that is, the labeled sample {(pv , 0) : v ∈ I} must be realizable in D2 . Its sub-samples of at most two examples are realizable by projections: for u, v ∈ I, distinct or not, the set {u, v} is a hyperedge-free subset of I, so c{u,v} is a common zero coordinate of pu and pv . Since maj is a near-unanimity term of D2 of arity 3, Proposition 3.1 with k = 2 gives f , and it makes at most |S| mistakes. Conclusion. By the first direction every hypothesis in C ⊆ Sk0 makes at least τ (H) mistakes, and by the second some hypothesis in C makes at most τ (H), so the optimum of the ERM instance is exactly τ (H), for each clone C of the interval. An objective-preserving reduction is in particular approximation-preserving, so parts (b) and (c) of Theorem 4.8 transfer to ERM for all clones of Proposition 4.9. The factor k is therefore optimal under the Unique Games Conjecture.

4.3

The tractable cases

Every clone outside the two hard regimes admits a polynomial-time ERM algorithm. Two elementary algorithms do all the work — pointwise majority for BF, minimum cut for M — and the remaining cases reduce to them by forcing labels or enumerating a coordinate. Proposition 4.10 (Base ERM algorithms). ERM for BF and ERM for M are solvable in polynomial time. 17

Proof. For BF, every relabeling of the sample is realizable, and the values at distinct sample points are independent. Hence the relabeling that assigns to each sample point the label occurring more often at it is optimal. For M, the positive region of a monotone function is an upset in the coordinatewise order on {0, 1}n . After merging duplicate examples, choosing an upset U has cost X X m+ (a). m− (a) + a∈U

a∈U /

Thus the problem is the minimum-cost upset problem on the finite poset induced by the sample points. Equivalently, its complement is a minimum-cost downset, which is a standard minimumcost closure problem [41] and can be solved by one s–t min-cut computation. Every upset of the induced sample poset extends to an upset of the full Boolean cube by taking its upward closure, so the computed relabeling of the sample is realizable by a monotone Boolean function. Theorem 4.11 (The tractable regime). ERM for C is solvable in polynomial time whenever C is one of BF, R∗ , M∗ , S0∗ , S1∗ , D, D1 , N∗ or I∗ . Proof. The clones BF and M are Proposition 4.10. Every other case reduces to one of these two, except the unary clones, which are solved by enumeration. Boundary clones. For R∗ , reduce to ERM for BF by boundary forcing: add W copies of (0, 0) for R0 , of (1, 1) for R1 , and of both for R2 . Every optimum of the enlarged sample then satisfies the required boundary condition, and conversely Ri consists of exactly the Boolean functions satisfying that condition, so the two instances have the same optimum value. The same argument reduces M0 , M1 , M2 to ERM for M. Ordinary separating clones. A function f lies in S0 precisely when its zero set is contained in {a : ai = 0} for some coordinate i, that is, when setting xi to 1 forces the value 1. For a fixed i, add W positive copies of every sample point a with ai = 1, run the BF algorithm, let h be a Boolean function realizing the relabeling it returns, and put f (x) = xi ∨ h(x). On the sample points a with ai = 0 the two agree, and on the remaining ones both predict 1 because of the forcing. Moreover the zero set of f is contained in {a : ai = 0}, so f ∈ S0 and the relabeling is realizable in S0 . Trying all i ∈ [n] and keeping the best solution puts ERM for S0 in P. Dually, for S1 , force every sample point a with ai = 0 to be negative and replace h by xi ∧ h(x). The six remaining clones combine this coordinate enumeration with the boundary forcing. For S02 and S12 , add the R2 boundary copies to the enlarged BF-instance. For the monotone ones, reduce to ERM for M instead: for S01 = S0 ∩ M, fix i, force the points a with ai = 1 positive and solve the resulting M-instance; for S00 = S0 ∩ R2 ∩ M, add the boundary labels 0 7→ 0 and 1 7→ 1 as well; and S11 , S10 are dual. The same extensions apply, since xi ∨ h is monotone and 0-separating, and xi ∧ h monotone and 1-separating, whenever h is monotone. The self-dual clones D and D1 . Let ρ choose a canonical representative of each complement pair, say the lexicographically smaller of a and ā, so that ρ(a) ∈ {a, ā} and ρ(a) = ρ(ā), and let σ(a) = 0 if a = ρ(a) and σ(a) = 1 otherwise. A self-dual function is determined by its values on the representatives: writing g for its restriction to them, f (a) = g(ρ(a)) ⊕ σ(a), and g ranges over all Boolean functions on the representatives as f ranges over D. Transform each labeled example (a, b) into ρ(a), b⊕σ(a) and call the resulting sample E ρ . Since f (a) = b if and only if g(ρ(a)) = b ⊕ σ(a), mistakes are preserved example by example, so optD (E) = optBF (E ρ ). For D1 = D ∩ R2 , use the same normalization and force the pair {0, 1} to the orientation 0 7→ 0, 1 7→ 1. With the lexicographic representative this is the single forced normalized label (0, 0). Unary and projection clones. The clones N∗ and I∗ contain only constants, projections and negated projections, so there are O(n) candidate hypotheses — ⊥, ⊤, xi and ¬xi , the admissible subset depending on the clone — and enumerating them gives the optimum. 18

4.4

Putting the pieces together

The hardness results of regime (i) were stated for the clones E, V and L at the top of their intervals; the passage from there to the rest of each interval is the same in all three cases, and it is the only step that is not already in the sources. Suppose C = [O] is not the clone at the top of its interval. Adjoining the truth constants then generates that clone: C± is E, V or L respectively. By Lemma 4.1, ERM for C± reduces to ERM for C by a reduction that leaves the sample size unchanged and preserves the mistakes of every relabeling, so it preserves empirical risks and promises as well, and a weak approximator for C would give one for C± . Finally, an exact ERM algorithm is a weak approximator, since on the promised instances it returns a relabeling of empirical risk at most ε. So ERM for C is NP-hard in all of these cases, and by the observation in the introduction it has no constant-factor approximation either. Theorem 1.3 follows. Regime (i) is Theorems 4.2 and 4.3 together with the propagation just described; regime (ii) is Propositions 4.6 and 4.7 together with Proposition 4.9 applied to Theorem 4.8; and regime (iii) is Theorem 4.11, the enumeration of Post’s lattice showing that the three regimes leave no clone unaccounted for. All of this is proved for ERM for the clone [O], which by the discussion at the beginning of the section is equivalent, with approximation ratios preserved, to ERM for PLO and to ERM for CIRO , so the theorem holds in both forms.

VC dimension

In preparation for the next section, where we study PAC learnability, we clarify the VC dimension of each fragment. A set A ⊆ {0, 1}n is shattered by a class F of n-ary Boolean functions if every subset of A is of the form A ∩ f −1 (1) with f ∈ F, and the VC dimension of F is the largest size of a shattered set. The VC dimension of PLO (or, equivalently, of CIRO ) grows either linearly or exponentially in the number of variables, depending on O. More precisely, the dividing line is given by the clones E, V and L. Proposition 1.4 (VC dimension). Let O be a finite basis of Boolean functions and let n ≥ 1. If O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {⊕, ⊤, ⊥}, then the VC dimension of PLO in n variables is at most n + 1. Otherwise it is 2Ω(n) . The proof uses the following basic fact about Post’s lattice, which will also be used in the next section. Fact 5.1. For all clones C, the following are equivalent: 1. C ̸⊆ E, C ̸⊆ V and C ̸⊆ L; 2. D2 ⊆ C or S00 ⊆ C or S10 ⊆ C. Equivalently, C contains at least one of the three functions maj(x, y, z),

f∨∧ (x, y, z) = x ∨ (y ∧ z),

f∧∨ (x, y, z) = x ∧ (y ∨ z).

Moreover, if C contains maj but neither f∨∧ nor f∧∨ , then C ⊆ D. d memProof of Proposition 1.4. For the upper bound, a class of VC dimension d has at least 2V bers, so it suffices to count. The n-ary part of E = [∧, ⊤, ⊥] consists of the conjunctions i∈S xi for S ⊆ [n], with S = ∅ giving ⊤, together with ⊥, so it has 2n + 1 members and VC dimension L at most n; dually for V. The n-ary part of L = [⊕, ⊤, ⊥] consists of the functions c ⊕ j∈J xj with c ∈ {0, 1} and J ⊆ [n], so it has 2n+1 members and VC dimension at most n + 1. Subclones only shrink these classes. For the lower bound, VC dimension is monotone in the class, so by Fact 5.1 it suffices to exhibit, for n ≥ 2, a set of size 2Ω(n) shattered by each of D2 , S00 and S10 . We may assume

that n is even, since the n-ary part of a clone contains every (n − 1)-ary member with a dummy variable added, so that the VC dimension in n variables is at least that in n − 1 variables. Let m = (n − 2)/2 and let A consist of the 2m points (1, b, b̄, 0) ∈ {0, 1}n ,

b ∈ {0, 1}m .

Every point of A has first coordinate 1, last coordinate 0 and exactly m + 1 ones. The argument has three steps. First, A is shattered by M. Its members have the same number of ones, so none lies below another, and for T ⊆ A the indicator function of the upset generated by T is monotone and is 1 exactly on T within A. Second, on A the coordinates x1 and xn can stand in for the truth constants, since a1 = 1 and an = 0 for every a ∈ A. Precisely, let C be a clone and f ∈ C± . As in the proof of Lemma 4.1, f (x) = g(x, 0, 1) for some g ∈ C, and g(x, xn , x1 ) is again a function of C, which agrees with f on A. Hence A is shattered by C whenever it is shattered by C± . Third, C± = M for each of the three clones. Indeed, maj(⊥, x, y) = x ∧ y and maj(⊤, x, y) = x ∨ y for D2 , f∨∧ (⊥, y, z) = y ∧ z and f∨∧ (x, y, y) = x ∨ y for S00 , and dually for S10 . So A is shattered by all three.

PAC learning

We make the learnability notions of the introduction precise. For a formula or circuit φ over n variables, let K(φ) = [φ]−1 (1) ⊆ {0, 1}n be the concept it defines, and let size(φ) be the size of the representation. Polynomially properly PAC learnable is the first notion of the introduction with these conventions. In polynomially PAC predictable with membership queries, the weaker demand of [5], the predicted label must be wrong with probability at most 1/2 − 1/p(s, n) for a polynomial p, and the learner must run in time polynomial in s, n and 1/ε. The VC bounds of Section 5, with the fitting algorithm of Section 3, already give the stronger, representation-insensitive form of learnability: a single learner that handles every target in PLO , with a number of examples polynomial in n, 1/ε and 1/δ but not permitted to grow with the size of the target’s representation. Proposition 6.1 (Learning PLO uniformly). Let O be a finite basis. There is a polynomialtime learner for PLO using poly(n, 1/ε, log(1/δ)) examples if and only if O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {⊕, ⊤, ⊥}. The statement is unconditional, and in the positive cases the hypothesis returned is a PLO -formula with at most n + 2 leaves. Proof. In the three positive cases, Proposition 1.4 bounds the VC dimension by n + 1, so a sample of size O (n + log(1/δ))/ε suffices for uniform convergence, and the fitting algorithm of Theorem 1.1 — cases (2) and (4) of its proof — turns such a sample into a consistent PLO formula in polynomial time with at most n + 2 leaves, namely a conjunction, a disjunction or a parity of variables with at most two further leaves. A consistent learner for a class of polynomial VC dimension is a polynomial-time PAC learner. The hypothesis is a formula, so the positive half holds whether the learner must output a formula or may output a circuit, and in particular for proper learning. Conversely, outside the three cases Proposition 1.4 gives VC dimension 2Ω(n) , and any learner for a class of VC dimension d requires Ω(d/ε) examples, hence exponential running time. This holds however the learner represents its hypotheses. The positive half of Theorem 1.5 is contained in this proposition. Its negative half is not: the obstruction above is information-theoretic and evaporates once the running time and sample complexity are allowed to depend on the size of the target concept. The remainder of this section proves this direction. By the cryptographic assumptions we mean throughout the assumption that at least one of the following is intractable: testing quadratic residuosity modulo a composite, inverting RSA encryption, and factoring Blum integers. The starting point is the following theorem. 20

Theorem 6.2 ([30, 5]). Under the cryptographic assumptions, PL{∧,∨,¬} is not polynomially PAC predictable with membership queries. Every conditional lower bound proved in this paper — in this section and in Sections 7 and 8 — is obtained from Theorem 6.2 by reductions; the lower bounds of Section 4 rest instead on P ̸= NP or on the Unique Games Conjecture. The reductions are of a type due to Angluin and Kharitonov [5], a membership-query variant of the prediction-preserving reductions of Pitt and Warmuth [42]. Below F, F ′ are fragments such as PLO or CIRO , and φ ranges over the members of F. Definition 6.3 ([16, Definition 1], after [5, 42]). F ≤pwm F ′ if there are mappings g (formulas), ι (instances) and h, j (queries), with g(s, n, φ) ∈ F ′ , such that (1) there is a nondecreasing polynomial q with size(g(s, n, φ)) ≤ q(s, n, size(φ)) for all s, n and all φ with size(φ) ≤ s; (2) ι is computable in time polynomial in s, n, |w|, and w ∈ K(φ) iff ι(s, n, w) ∈ K(g(s, n, φ)) whenever size(φ) ≤ s and w ∈ {0, 1}n ; (3) h and j are computable in time polynomial in s, n, |w′ |, and for every tuple w′ : w′ ∈ K(g(s, n, φ)) iff j(s, n, w′ , b) = ⊤, where b := ⊤ if h(s, n, w′ ) ∈ K(φ) and b := ⊥ otherwise. The relevant property of these reductions is that if F ≤pwm F ′ and F ′ is polynomially PAC predictable with membership queries, then so is F (cf. [16, Lemmas 1 and 2]). We now prove Theorem 1.5, restated at the end of this section. Consider PLO where O falls under none of the three positive cases. In that case [O] contains one of f∨∧ (x, y, z) = x ∨ (y ∧ z),

f∧∨ (x, y, z) = x ∧ (y ∨ z),

maj(x, y, z),

by Fact 5.1 and the reductions to be constructed are those of Theorems 2–4 of [16]. Those reductions substitute a fixed gadget for each gate of the source formula. In a circuit this costs a constant factor, the gadget sharing its argument wires. In a formula it need not, since the substitution patterns duplicate arguments and the gadget may read each placeholder more than once, so size can grow by a constant factor per level. The published argument therefore yields PL{∧,∨,¬} ≤pwm CIRO , which is weaker than Theorem 1.5: for a fixed size bound the formularepresented concepts are a subclass of the circuit-represented ones, and hardness does not pass to subclasses. The missing step is to rebalance the source formula before substituting, since on a formula of logarithmic depth the substitution costs a polynomial factor overall. Balancing introduces the truth constants, which PLO need not have. They are carried instead by the auxiliary variables that the instance mapping already appends, at the cost of one further such variable in two of the three cases. We record Spira’s theorem in the form used. Fact 6.4 (Balancing, [49]). Let φ be a formula over a finite set of Boolean connectives. There is an equivalent PL{∧,∨,¬} -formula of depth O(log size(φ)) and of size polynomial in size(φ), computable from φ in polynomial time. The next lemma collects everything that happens while the truth constants are still available, and does so once and for all: its hypothesis is only that [O] contains the monotone clone M = [∧, ∨, ⊤, ⊥], which holds for every basis of M and, more to the point below, for O ∪ {⊤, ⊥} whenever [O] contains one of the three functions above. Since the basis is arbitrary, all the construction needs of O are fixed formulas for ∧, ∨ and the two truth constants. Lemma 6.5. Let O be a finite set of Boolean functions such that M ⊆ [O]. Then PL{∧,∨,¬} ≤pwm PLO .

Proof. Let φ be a PL{∧,∨,¬} -formula over the variables x1 , . . . , xn . By Fact 6.4 we may assume that depth(φ) is bounded logarithmically in size(φ), at the cost of replacing φ by an equivalent formula of size polynomial in size(φ), computable in polynomial time. The balanced formula may contain the truth constants, which costs nothing below, both lying in M. The remainder follows Lemma 3 of [16]. For the sake of completeness, we spell out the details. Pushing negations to the leaves by de Morgan’s laws turns φ into a monotone formula φ+ over {∧, ∨, ⊤, ⊥} and the 2n variables x1 , . . . , xn , y1 , . . . , yn , the variable yi taking the place of ¬xi , so that φ+ (a, ā) = φ(a) for every a ∈ {0, 1}n . The tree is unchanged, so φ+ has the same depth as φ. On its own φ+ is of no use, because condition (3) of Definition 6.3 ranges over all query tuples, including those in which the yi are not set to the complements of the xi , where the value of φ+ need not be determined by φ at all. Two guards repair this. Let ^ _ (xi ∨ yi ), ψ := A ∨ (φ+ ∧ B), (xi ∧ yi ), B := A := i≤n

i≤n

with A and B written as balanced trees, so that depth(A) and depth(B) are at most ⌈log n⌉ + 1. Then ψ is again a monotone formula over {∧, ∨, ⊤, ⊥}. Its depth is max{depth(φ+ ), ⌈log n⌉ + 1} + 2, hence still logarithmic in size(φ) + n, and its value is determined by φ at every point. Indeed, write ⟨a, a′ ⟩ for the setting that gives x1 , . . . , xn the values a and y1 , . . . , yn the values a′ . If ai = a′i = 1 for some i then A holds and ψ evaluates to 1; if ai = a′i = 0 for some i and the previous case does not apply then B fails and ψ evaluates to 0; and otherwise a′ = ā, where A fails, B holds, and ψ evaluates to φ(a). The four connectives of ψ lie in M ⊆ [O]. Fix a PLO -formula computing each of them, and let χ be the result of substituting these into ψ, so that χ ∈ PLO is equivalent to ψ. Substituting a fixed formula for each node multiplies depth by a constant, so depth(χ) too is logarithmic in size(φ) + n, and a formula of depth d whose connectives all have arity at most r has at most rd leaves, so size(χ) = (size(φ) + n)O(1) , with an exponent depending only on the four formulas just chosen. It remains to collect the mappings. They are: • g(s, n, φ) := χ; • ι(s, n, a) := ⟨a, ā⟩; • h(s, n, ⟨a, a′ ⟩) := a, and • j(s, n, ⟨a, a′ ⟩, b) := ⊤ if ai = a′i = 1 for some i, := ⊥ if not and ai = a′i = 0 for some i, and := b otherwise. Condition (1) of Definition 6.3 is the size bound just proved, condition (2) holds because χ(a, ā) = φ(a), and condition (3) is the case distinction of the previous paragraph. The remainder of the proof is exactly as in [16]. For completeness, we spell it out below. Lemma 6.6. Let O be a finite set of Boolean functions with f∨∧ ∈ [O] or f∧∨ ∈ [O]. Then PL{∧,∨,¬} ≤pwm PLO . Proof. We give the proof for the case f∨∧ ∈ [O]. The argument for the other case is dual. Since conjunction and disjunction are definable as f∨∧ (⊥, x, y) and f∨∧ (x, y, y), respectively, we have that M ⊆ [O ∪{⊤, ⊥}] and Lemma 6.5 gives PL{∧,∨,¬} ≤pwm PLO∪{⊤,⊥} . By transitivity it remains to remove the truth constants, that is, to show PLO∪{⊤,⊥} ≤pwm PLO . Recall that a pwm-reduction consists of mappings g (for concepts), ι (for instances) and h, j (for queries). The mappings in question are:

• g(s, n, χ) := φ∨∧ (z0 , z1 , χ′ (x, z0 , z1 )) where φ∨∧ is a PLO -formula defining f∨∧ , and where χ′ ∈ PLO is obtained from χ by replacing ⊥ by a fresh variable z0 and ⊤ by a fresh variable z1 . • ι(s, n, a) := ⟨a, 0, 1⟩. • h(s, n, ⟨a, c0 , c1 ⟩) := a, and • j(s, n, ⟨a, 0, 1⟩, b) := b j(s, n, ⟨a, 0, 0⟩, b) := ⊥ j(s, n, ⟨a, 1, 0⟩, b) := ⊤ j(s, n, ⟨a, 1, 1⟩, b) := ⊤ Here a ranges over {0, 1}n and c0 , c1 over {0, 1}, the query string ⟨a, c0 , c1 ⟩ giving x1 , . . . , xn the values a and z0 , z1 the values c0 , c1 . The conditions of Definition 6.3 are met: g(χ) computes z0 ∨ (z1 ∧ χ′ (x, z0 , z1 )), which takes the value χ(a) at ⟨a, 0, 1⟩, the value 0 at ⟨a, 0, 0⟩ and the value 1 whenever c0 = 1 — in every case but the first, independently of what χ′ computes there. The two formulas differ in size by the one copy of φ∨∧ . Lemma 6.7. Let O be a finite set of Boolean functions with maj ∈ [O], all of whose members are self-dual; that is, let D2 ⊆ [O] ⊆ D. Then PL{∧,∨,¬} ≤pwm PLO . Proof. Since conjunction and disjunction are definable as maj(⊥, x, y) and maj(⊤, x, y), respectively, we have that M ⊆ [O ∪ {⊤, ⊥}] and Lemma 6.5 gives PL{∧,∨,¬} ≤pwm PLO∪{⊤,⊥} . By transitivity it remains to remove the truth constants, that is, to show PLO∪{⊤,⊥} ≤pwm PLO . The mappings are: • g(s, n, χ) := φmaj (χ′ (x, z0 , z1 ), z0 , z1 ) where φmaj is a PLO -formula defining maj, and where χ′ ∈ PLO is obtained from χ by replacing ⊥ by a fresh variable z0 and ⊤ by a fresh variable z1 . • ι(s, n, a) := ⟨a, 0, 1⟩. • h(s, n, ⟨a, c0 , c1 ⟩) := a if (c0 , c1 ) ̸= (1, 0) and := ā otherwise, where ā is the bitwise complement of a, and • j(s, n, ⟨a, 0, 1⟩, b) := b j(s, n, ⟨a, 0, 0⟩, b) := ⊥ j(s, n, ⟨a, 1, 0⟩, b) := ¬b j(s, n, ⟨a, 1, 1⟩, b) := ⊤ Again the conditions of Definition 6.3 are met: g(χ) computes maj(χ′ (x, z0 , z1 ), z0 , z1 ), which is 0 at (c0 , c1 ) = (0, 0) and 1 at (1, 1) independently of what χ′ computes there, and which is the value of χ′ itself at the two remaining settings — at (0, 1) that value is χ(a), and at (1, 0) it is ¬χ(ā), since evaluating χ′ at (1, 0) evaluates χ with ⊤ and ⊥ interchanged, and a formula all of whose connectives are self-dual then computes the dual function. Theorem 1.5 (PAC learning and PAC prediction [16]). Let O be a finite basis. The following are equivalent. (a) O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {⊕, ⊤, ⊥}; (b) PLO is polynomially properly PAC learnable;

(c) PLO is polynomially PAC predictable with membership queries. The implications (a) ⇒ (b) ⇒ (c) are unconditional; the remaining implication (c) ⇒ (a) holds under cryptographic assumptions described in Section 6. The same equivalence holds with CIRO in place of PLO . Proof. That (a) implies (b) and (c) is Proposition 6.1 together with the remark after it: the learner there uses no promise on the target’s size, and it certainly yields both a PAC learner and a PAC predictor. That (b) implies (c) is immediate, PAC prediction being easier than producing a hypothesis and membership queries only adding power. It remains to show that (c) implies (a), which we do by contraposition. Suppose O satisfies none of the three conditions. By Fact 5.1 either [O] contains f∨∧ or f∧∨ , and then PL{∧,∨,¬} ≤pwm PLO by Lemma 6.6; or it contains neither, and then [O] ⊆ D while still containing one of the three generators, necessarily maj, so that PL{∧,∨,¬} ≤pwm PLO by Lemma 6.7. Either way, Theorem 6.2 shows that PLO is not polynomially PAC predictable with membership queries. Finally PLO ≤pwm CIRO by the identity reduction — a formula is a tree-shaped circuit of the same size — so the circuit class is not polynomially PAC predictable either, and the equivalence holds for it as well.

Occam algorithms

Recall from the introduction that an Occam algorithm for PLO is a polynomial-time fitting algorithm returning, on every realizable sample, a fitting formula of size at most p sopt (E), n · mβ for a fixed polynomial p and a fixed β < 1, attribute-efficient if the bound does not depend on n. Size may be read as formula or as circuit size, the positive results producing formulas and the negative one being proved for circuits. The negative direction is a corollary of Theorem 1.5: a sufficiently compressing fitting algorithm is a proper PAC learner, so a class that is not even polynomially PAC predictable cannot have one. Theorem 1.2 (Occam algorithms, from [16]). Let O be a finite basis of Boolean functions. (a) If O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {¬, ⊤, ⊥}, then PLO has an attribute-efficient Occam algorithm. (b) If {⊕3 } ⪯ O ⪯ {⊕, ⊤, ⊥}, then PLO has an Occam algorithm, but we do not know whether it has an attribute-efficient one. (c) Otherwise PLO does not have an Occam algorithm, under the cryptographic assumptions of Section 6. The same holds for CIRO . Proof. For (a), all three cases are handled by the standard greedy, set-cover-inspired fitting algorithm; see for instance [32]. If O ⪯ {∧, ⊤, ⊥}, the fitting hypotheses are the conjunctions V i∈S xi with S contained in the set T of coordinates that are 1 on every positive example and meeting, for every negative example, the set of coordinates of T on which it is 0. Minimizing |S| is a hitting set problem with at most m sets to hit, and greedy returns a set of size at most (1 + ln m) times the minimum, so the returned formula has size O(sopt (E) log m). When the empty conjunction ⊤ is unavailable, as for E2 = [∧], replace it by a single element of T , which is nonempty on a realizable sample. The case O ⪯ {∨, ⊤, ⊥} is dual, and if O ⪯ {¬, ⊤, ⊥} then every hypothesis is a constant, a variable or a negated variable, so any fitting hypothesis has size O(1) and the fitting algorithm of Section 3 returns one. In all three cases the bound is independent of n. For (b), case (2) L of the proof of Theorem 1.1 returns, by Gaussian elimination, a fitting affine function c ⊕ j∈J xj written as a PLO -formula with at most n + 2 leaves. That is a bound 24

of the required form, with β = 0, but it depends on n: what is not known is how to control |J|, and with it the size of the formula, in terms of sopt (E), and we leave that open. For (c), an Occam algorithm for PLO is a proper PAC learner [11], so PLO would be polynomially properly PAC learnable, which Theorem 1.5 excludes outside the regions of (a) and (b) under the cryptographic assumptions.

Random label noise and statistical queries

Fix a target f and a distribution D on {0, 1}n . Under random classification noise of rate η < 1/2 [6] the learner receives examples (a, b) with a ∼ D and b = f (a) flipped independently with probability η, and must reach error ε with probability 1 − δ in time polynomial in n, s, 1/ε, 1/δ and 1/(1 − 2ηb ), where ηb < 1/2 is a given upper bound on η. In the statistical query model [28] the learner sees no examples; it may ask, for any polynomial-time predicate χ(a, b) and any tolerance τ , for a number within τ of Pra∼D [χ(a, f (a)) = 1], and it is efficient if it uses polynomially many queries, each of tolerance at least 1/p(n, s, 1/ε) for a fixed polynomial p, and polynomial time. Kearns proved that such a learner can be simulated from examples, noisy or not: every class efficiently learnable from statistical queries is PAC learnable under random classification noise of any rate η < 1/2, in polynomial time [28]. Theorem 1.6 (Statistical queries, from [28, 9]). Let O be a finite basis. Under the cryptographic assumptions of Section 6, PLO is efficiently learnable from statistical queries if and only if O ⪯ {∧, ⊤, ⊥}, O ⪯ {∨, ⊤, ⊥} or O ⪯ {¬, ⊤, ⊥}. The same holds for CIRO . The positive direction is Kearns’s statistical-query algorithm for conjunctions [28]; disjunctions are dual, and for O ⪯ {¬, ⊤, ⊥} there are at most 2n + 2 hypotheses, whose errors can be estimated one by one. For the affine bases the negative direction is unconditional and holds already under the uniform distribution: [O] ⊇ L2 contains the 2n−1 parities of an odd number of variables, which are pairwise uncorrelated under that distribution, and a class with exponentially many pairwise uncorrelated members needs exponentially many statistical queries or exponentially small tolerance [28, 9]. For every other basis outside the three cases, a statistical-query learner would yield a PAC learner and hence a PAC predictor, so PLO would be polynomially PAC predictable with membership queries, which Theorem 1.5 excludes under the cryptographic assumptions. By Kearns’s simulation, the positive direction gives polynomial-time PAC learning under random classification noise of any rate η < 1/2 for the conjunctive, the disjunctive and the essentially unary bases. The negative direction transfers only in part. Outside the PAC-learnable region noise is beside the point: a learner that tolerates noise of rate up to ηb can be run on noise-free examples, so Theorem 1.5 excludes it under the cryptographic assumptions. For the affine clones, however, the statistical-query lower bound says nothing about noisy examples, and it is exactly here that the two models are known to part company: Blum, Kalai and Wasserman [10] learn parities under random classification noise in time 2O(n/ log n) , fewer than the 2Ω(n) statistical queries needed above, and whether polynomial time is possible — the learning parity with noise problem — is open.

Other kinds of fragments

Every fragment considered above is generated by a set of connectives, and is therefore closed under substitution. Several fragments of independent interest are not of this shape. These include monotone CNF, Horn CNF, and systems of linear equations over F2 . None of the classifications of the introduction applies to such fragments. In this section, we consider a few other types of fragments.

9.1

Fragments given by constraint languages

A constraint language (also known as a template) is a set Γ of Boolean relations. A CNFΓ -formula over x1 , . . . , xn is a conjunction of atoms R(xi1 , . . . , xik ) with R ∈ Γ of arity k; the concept it defines is its set of satisfying assignments in {0, 1}n , and its size is its number of atoms. Deciding whether a CNFΓ -formula has a model is the well-studied constraint satisfaction problem CSP(Γ), which was classified by Schaefer’s theorem [45]. Monotone CNF, Horn CNF and systems of linear equations can all be viewed as instances of CNFΓ for different choices of the constraint language Γ. For instance, Horn CNF is CNFΓ for Γ the set of all Horn clauses. In each of these cases, Γ is infinite, but there are also natural fragments CNFΓ where Γ is finite, such as k-CNF, for a fixed value of k, where Γ is the finite set of all k-ary relations over the Booleans. PL{∧,⊤} can also be cast as CNF{True} , where True is the unary Boolean relation containing only the tuple (1). For finite constraint languages Γ, results analogous to the classifications of the introduction hold, empirical risk minimization aside. In fact the situation here is simpler: for every finite Γ there is a fitting formula within a logarithmic factor of the smallest, and the VC dimension of CNFΓ is polynomial in the number of variables. Note that, since there are only finitely many Boolean relations of any given arity, every constraint language of bounded arity is finite, up to logical equivalence, and conversely a finite constraint language has bounded arity. Proposition 9.1. Fix a finite constraint language Γ and let r be the largest arity of a relation in Γ. Then (1) the existence of a fitting CNFΓ -formula for a given labeled sample is decidable in polynomial time, (2) given a realizable labeled sample E of size m, one may in addition compute in polynomial time a fitting CNFΓ -formula of size at most (1 + ln m) · sopt (E), where sopt (E) is the number of atoms of a smallest fitting formula, (3) the VC dimension of CNFΓ in n variables is at most |Γ| nr , and hence, together with (2), CNFΓ -formulas in n variables are polynomially properly PAC learnable. Proof. First, observe that there are at most |Γ| nr atoms over x1 , . . . , xn . For (1), let A be the set of atoms satisfied by every positive example of E. V Any CNFΓ -formula whose concept contains all positive examples uses only atoms from A, so A defines the ⊆-least concept of CNF them. The sample is realizable if and only if no negative example satisfies V Γ containing V A, and A is then a fitting formula. For (2), observe that a CNFΓ -formula fits E if and only if its atoms lie in A and every negative example violates at least one of them: this is a set cover instance with the negative examples as ground set and A as the family of sets, so the greedy set-cover algorithm [25] returns a fitting formula within a factor 1 + ln m of the smallest. r For (3), a concept of CNFΓ is determined by a set of atoms, so the class has at most 2|Γ|n members and its VC dimension is at most log2 of that. Finally, the polynomial VC dimension together with (2) gives proper PAC learning. Note also that the Occam bound in (2), measured in number of atoms, does not depend on n, so the algorithm can be said to be attribute-efficient in the sense of Section 7. The fitting problem for CNFΓ is the structure identification problem of Dechter and Pearl [19], studied for general Γ by Creignou, Kolaitis and Zanuttini [15]. Its variant in which only the positive examples are given, and the formula must define exactly their set, is the inverse satisfiability problem of Kavvadias and Sideri [27, 37]. When it comes to empirical risk minimization, hardness cases arise. Recall that PL{∧,⊤} coincides with CNFΓ for Γ = {True} as described above. Therefore, Theorem 1.3 (i) applies, and there is no polynomial-time weak approximator for CNF{True} unless P = NP. The lower bound 26

there is representation-independent, so it does not matter that the hypothesis is now written as a conjunction of atoms. However, we do not know where the dividing line runs, either for exact solvability or for approximability of ERM. For infinite constraint languages Γ, Proposition 9.1 fails as stated. Note that there are then relations of unbounded arity, and the atom count over n variables is no longer polynomial. Four examples show what can happen. Example 9.2 (Monotone CNF). The concepts of monotone CNF over n variables are exactly the upsets of {0, 1}n , since a monotone function is the conjunction of its prime implicates and these are positive clauses. Fitting is polynomial: the least concept containing the positive examples is the upset they generate, so the sample is realizable if and only ifno negative example n lies above a positive one. The VC dimension, on the other hand, is ⌊n/2⌋ , hence exponential, as follows from Sperner’s theorem [48]. Finally, without membership queries, PAC-learning is no easier for monotone CNF than for arbitrary CNF [29]. In particular, monotone CNF is not polynomially properly PAC learnable from random examples alone unless NP = RP [1]. Monotone CNF is polynomially properly PAC learnable with membership queries [3]. Example 9.3 (Horn CNF). Fitting is again polynomial, in both its decision and its construction form [19]. Since every monotone clause is a dual Horn clause, which can be turned into a Horn n clause by complementing all coordinates, the VC dimension ⌊n/2⌋ for monotone CNF is also a lower bound on the VC dimension of Horn CNF, and the hardness of proper PAC learning from random examples transfers from monotone CNF to Horn CNF as well. Horn CNF is polynomially properly PAC learnable with membership queries [4]. Example 9.4 (Systems of linear equations). Here Γlin consists of the relations xi1 ⊕· · ·⊕xik = c for k ≥ 0 and c ∈ {0, 1}, again an infinite template, and the concepts of CNFΓlin over n variables are the affine subspaces of Fn2 together with ∅. Unlike the previous two examples, this one is well behaved throughout. Fitting is polynomial in both its decision and its construction form: the least concept containing the positive examples is their affine hull, computed by Gaussian elimination, the sample is realizable exactly when no negative example lies in it, and at most n equations define it, so the fitting formula has at most n atoms. The VC dimension is n + 1, a set being shattered exactly when it is affinely independent. As a result, CNFΓlin is polynomially properly PAC learnable [24]. Example 9.5 (A simple infinite template that is hard for fitting). Let Γone = {Uniqk : k ≥ 1}, where Uniqk (x1 , . . . , xk ) holds when exactly one of its arguments is 1. Then fitting for CNFΓone is NP-hard, as can be shown by a reduction from exact cover by 3-sets [22]: given a set U and a family S of 3-element subsets of U , is there a subfamily covering each element of U exactly once? Take one variable xS for each S ∈ S, one positive example pu for each u ∈ U , namely the characteristic vector of {S ∈ S : u ∈ S}, and the single negative example 0. If S ′ = {S1 , . . . , Sk } is an exact cover of size k, the single-atom formula Uniqk (xS1 , . . . , xSk ) fits: exactly one argument is 1 under pu , since exactly one member of S ′ contains u, while none is 1 under 0. Conversely, suppose some formula fits. It has at least one atom, since the empty conjunction accepts 0. Let Uniqk (xS1 , . . . , xSk ) be an arbitrary atom in the conjunction. Its arguments are pairwise distinct: each S ∈ S is nonempty, so a repeated variable xS would give two true arguments under pu for any u ∈ S. As every pu satisfies the atom, each u ∈ U lies in exactly one of S1 , . . . , Sk , that is, {S1 , . . . , Sk } is an exact cover.

9.2

Adding existential quantification

A classification of CNFΓ indexed by Post’s lattice is not immediately available. The expressive power of CNFΓ depends on Γ up to definability by quantifier-free conjunctive formulas, which is strictly finer than primitive positive definability — definability by conjunctions of atoms 27

and equalities with existential quantification, the closure operation of the next paragraph — so that the usual Galois connection with the polymorphisms Pol(Γ) defined there does not apply.2 There is, therefore, no reason to believe that, for example, the complexity of ERM for finite-template CNFΓ would be determined by the polymorphisms of Γ. What does govern quantifier-free conjunctive definability is the partial polymorphisms of Γ [46], and the lattice of strong partial clones they give rise to is far more complicated than Post’s [2]. Allowing existential quantification fixes this and restores the connection to Post’s lattice. An ∃CNFΓ -formula over x1 , . . . , xn is a formula ∃z1 · · · ∃zℓ φ(x1 , . . . , xn , z1 , . . . , zℓ ), where φ is a conjunction of atoms R(·) with R ∈ Γ and of equalities between variables; the concept it defines is the set of a ∈ {0, 1}n that extend to a satisfying assignment of φ, and its size is the number of atoms of φ. The concepts so definable are exactly the n-ary relations of the co-clone ⟨Γ⟩ = Inv(Pol(Γ)) generated by Γ. Here an operation f of arity k preserves a relation R if applying f coordinatewise to k tuples of R again gives a tuple of R. Then Pol(Γ) is the clone of operations preserving every relation of Γ, and Inv(C) is the set of relations preserved by every operation of C. A set of relations of the form Inv(C) is a co-clone, and ⟨Γ⟩ is the least co-clone containing Γ, namely the closure of Γ under exactly the constructs used above: conjunction, existential quantification, equality and identification of variables. Co-clones are to conjunctive existential definability what clones are to substitution, and Pol and Inv match the two lattices antitonically. We briefly describe the situation for two of our main questions in this setting. Fitting. The existence of a fitting ∃CNFΓ -formula can be tested in polynomial time, regardless of the choice of Γ. The concepts of ∃CNFΓ over n variables are the subsets of {0, 1}n preserved by Pol(Γ), so the closure of the set P of positive examples under the operations of Pol(Γ), applied coordinatewise, is the least concept containing P , and the sample is realizable exactly when no negative example lies in that closure. That is again a two-element subpower membership problem in the algebraic form of Section 3, with the positive examples in place of the columns of the variables and a negative example in place of the column of labels, and it is therefore polynomial by the same case analysis over Post’s lattice as in the proof of Theorem 1.1, applied to Pol(Γ). Unlike there, this route does not provide a fitting ∃CNFΓ -formula of polynomial size: the witness it produces is a term of Pol(Γ), not an ∃CNFΓ -formula. PAC learning. For finite Γ the learnability of ∃CNFΓ was classified by Dalmau [17] and rederived from the polymorphisms of Γ by Dalmau and Jeavons [18, Theorem 15]. In the terminology of Section 6, exactly one of the following holds. (a) Pol(Γ) contains a near-unanimity operation or the affine operation x ⊕ y ⊕ z. Then ∃CNFΓ is polynomially PAC predictable, even without membership queries, and in the near-unanimity case it is polynomially properly PAC learnable [18, Corollary 1]. (b) Otherwise ∃CNFΓ is not polynomially PAC predictable with membership queries, under the cryptographic assumption of [18], the existence of public-key cryptosystems secure against chosen-ciphertext attack. Dalmau and Jeavons state the positive half as polynomial learnability from equivalence queries, with ∃CNFΓ -formulas as hypotheses in the near-unanimity case. A polynomial equivalencequery learner yields a polynomial PAC learner with the same hypotheses [3], which is proper when these are ∃CNFΓ -formulas and in any case a PAC predictor, the hypotheses being evaluable 2

The fact that the expressive power of CNFΓ does not solely depend on the polymorphisms of Γ, can be seen by taking Γ = {⊕3 (x, y, z) = 0} and Γ′ = Γ ∪ {=}. The two templates have the same polymorphisms, since every operation preserves equality. But the CNFΓ′ -formula x = y is not expressible in CNFΓ .

in polynomial time. In the affine case their learner is not proper, and proper PAC learnability is not addressed there. Some unbounded-arity CNFΓ can be recast as finite-arity ∃CNFΓ′ . In particular, Horn CNF is equivalent in expressive power to ∃CNFΓHorn for the finite template ΓHorn = {x ∧ y → z, x → y, x, ¬x}. To see this, note that for k ≥ 2 the Horn clause x1 ∧ · · · ∧ xk → y is equivalent to ∃z1 · · · ∃zk−1 (x1 ∧ x2 → z1 ) ∧

k−1 ^

(zi−1 ∧ xi+1 → zi ) ∧ (zk−1 → y),

i=2

the constraints on the zi being themselves Horn, so that the least choice of z1 , . . . , zk−1 makes zk−1 equal to x1 ∧ · · · ∧ xk and the last conjunct is then exactly the clause. Clauses with k ≤ 1 are already atoms, and a clause with no positive literal is treated the same way, with ¬zk−1 in place of zk−1 → y. Since ΓHorn contains the clause x̄ ∨ ȳ ∨ z, it falls under case (b) [18, Theorem 11]: ∃CNFΓHorn is not polynomially PAC predictable with membership queries under the cryptographic assumption above. Horn CNF itself, by contrast, is polynomially properly PAC learnable with membership queries [4], though from random examples alone it is not properly PAC learnable unless NP = RP [29, 1], as discussed above, and whether it is polynomially PAC predictable from random examples alone is open, a PAC predictor settling the DNF problem by the same reduction. There is no conflict between the two statements: a Horn CNF of m clauses translates into an ∃CNFΓHorn -formula of O(mn) atoms, but the converse translation can be exponential — existential quantification acts on Horn clauses as fan-out does on circuits — and hardness of the more succinct class says nothing about the less succinct one. A similar situation holds for monotone CNF.

Open questions Several questions are left open above. For the affine interval {⊕3 } ⪯ O ⪯ {⊕, ⊤, ⊥}, Theorem 1.2 gives an Occam algorithm whose bound depends on n, and we do not know whether the support of the fitted parity can be controlled in terms of the size of the smallest fitting formula, that is, whether the algorithm can be made attribute-efficient; nor, for the same interval, whether PLO is PAC learnable under random classification noise in polynomial time, which is the learning parity with noise problem (Section 8). And for fragments given by a finite constraint language we do not know where the line runs for empirical risk minimization, either for exact solvability or for approximability.

References [1] Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, and Toniann Pitassi. The complexity of properly learning simple concept classes. Journal of Computer and System Sciences, 74(1):16–34, 2008. [2] V. B. Alekseev and A. A. Voronenko. On some closed classes in partial two-valued logic. Discrete Mathematics and Applications, 4(5):401–419, 1994. [3] Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1988. [4] Dana Angluin, Michael Frazier, and Leonard Pitt. Learning conjunctions of Horn clauses. Machine Learning, 9(2):147–164, 1992. [5] Dana Angluin and Michael Kharitonov. When won’t membership queries help? Journal of Computer and System Sciences, 50(2):336–355, 1995.

[6] Dana Angluin and Philip Laird. 2(4):343–370, 1988.

Learning from noisy examples.

Machine Learning,

[7] Kirby A. Baker and Alden F. Pixley. Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Mathematische Zeitschrift, 143(2):165–174, 1975. [8] Nick Bezhanishvili, Balder ten Cate, Arunavo Ganguly, and Arne Meier. Modal fragments. arXiv:2603.05055, 2026. [9] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC 1994), pages 253–262. ACM, 1994. [10] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4):506–519, 2003. [11] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam’s razor. Information Processing Letters, 24(6):377–380, 1987. [12] Elmar Böhler, Nadia Creignou, Steffen Reith, and Heribert Vollmer. Playing with Boolean blocks, part I: Post’s lattice with applications to complexity theory. SIGACT News, 34(4):38–52, 2003. [13] Nader H. Bshouty and George Haddad. Approximating the number of relevant variables in a parity implies proper learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024), volume 317 of LIPIcs, pages 38:1–38:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. [14] Andrei Bulatov, Peter Mayr, and Ágnes Szendrei. The subpower membership problem for finite algebras with cube terms. Logical Methods in Computer Science, 15(1):11:1–11:48, 2019. [15] Nadia Creignou, Phokion G. Kolaitis, and Bruno Zanuttini. Structure identification of Boolean relations and plain bases for co-clones. Journal of Computer and System Sciences, 74(7):1103–1115, 2008. [16] Vı́ctor Dalmau. Boolean formulas are hard to learn for most gate bases. In Algorithmic Learning Theory (ALT 1999), volume 1720 of Lecture Notes in Computer Science, pages 301–312. Springer, 1999. [17] Vı́ctor Dalmau. A dichotomy theorem for learning quantified Boolean formulas. Machine Learning, 35(3):207–224, 1999. [18] Vı́ctor Dalmau and Peter Jeavons. Learnability of quantified formulas. Theoretical Computer Science, 306(1–3):485–511, 2003. [19] Rina Dechter and Judea Pearl. Structure identification in relational data. Artificial Intelligence, 58(1–3):237–270, 1992. [20] Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing, 34(5):1129–1146, 2005. [21] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing, 39(2):606–645, 2009. 30

[22] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [23] Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798– 859, 2001. [24] David Helmbold, Robert Sloan, and Manfred K. Warmuth. Learning nested differences of intersection-closed concept classes. Machine Learning, 5(2):165–196, 1990. [25] Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555–556, 1982. [26] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require superlogarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990. [27] Dimitris J. Kavvadias and Martha Sideri. The inverse satisfiability problem. SIAM Journal on Computing, 28(1):152–163, 1998. [28] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983–1006, 1998. [29] Michael Kearns, Ming Li, Leonard Pitt, and Leslie G. Valiant. On the learnability of Boolean formulae. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987), pages 285–295. ACM, 1987. [30] Michael Kearns and Leslie Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1):67–95, 1994. [31] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2):115–141, 1994. [32] Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994. [33] Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and Grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 576–589. ACM, 2017. [34] Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in Grassmann graph have near-perfect expansion. Annals of Mathematics, 198(1):1–92, 2023. [35] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2 − ε. Journal of Computer and System Sciences, 74(3):335–349, 2008. [36] Adam R. Klivans and Rocco A. Servedio. Toward attribute efficient learning of decision lists and parities. Journal of Machine Learning Research, 7:587–602, 2006. [37] Victor Lagerkvist and Magnus Wahlström. A dichotomy theorem for the inverse satisfiability problem. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), volume 93 of LIPIcs, pages 39:1–39:14, 2017. [38] Dietlinde Lau. Function Algebras on Finite Sets: A Basic Course on Many-Valued Logic and Clone Theory. Springer Monographs in Mathematics. Springer, 2006. [39] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linearthreshold algorithm. Machine Learning, 2(4):285–318, 1988. 31

[40] Peter Mayr. The subpower membership problem for Mal’cev algebras. International Journal of Algebra and Computation, 22(7):1250075, 2012. [41] Jean-Claude Picard. Maximal closure of a graph and applications to combinatorial problems. Management Science, 22(11):1268–1272, 1976. [42] Leonard Pitt and Manfred K. Warmuth. Prediction-preserving reducibility. Journal of Computer and System Sciences, 41(3):430–467, 1990. [43] Emil L. Post. The Two-Valued Iterative Systems of Mathematical Logic, volume 5 of Annals of Mathematics Studies. Princeton University Press, 1941. [44] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, 1999. [45] Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pages 216–226. ACM, 1978. [46] Henning Schnoor and Ilka Schnoor. Partial polymorphisms and constraint satisfaction problems. In Complexity of Constraints, volume 5250 of Lecture Notes in Computer Science, pages 229–254. Springer, 2008. [47] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. [48] Emanuel Sperner. Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27(1):544–548, 1928. [49] Philip M. Spira. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences, pages 525–527, 1971.

Record · ID 668042 · SHA-256 cf7e9bd2c7d6a14f
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.