The seminal Satisfiability Coding Lemma of Paturi, Pudlák, and Zane is a coding scheme for satisfying assignments of k-CNF formulas. We generalize it to give a coding scheme for implicants and use this generalized scheme to establish new structural and algorithmic properties of prime implicants of k-CNF formulas. Our first application is a near-optimal bound of n⋅ 3^{n(1-Ω(1/k))} on the number of prime implicants of any n-variable k-CNF formula. This resolves an open problem from the Ph.D. thesis of Talebanfard, who proved such a bound for the special case of constant-read k-CNF formulas. Our proof is algorithmic in nature, yielding an algorithm for computing the set of all prime implicants - the Blake Canonical Form - of a given k-CNF formula. The problem of computing the Blake Canonical Form of a given function is a classic one, dating back to Quine, and our work gives the first non-trivial algorithm for k-CNF formulas.

The integer complexity of a natural number n, denoted by ‖n‖, is the smallest number of 1’s needed to express n using an arbitrary combination of addition and multiplication (and parentheses). For example, ‖6‖ = 5 since the expression 6 = (1+1)⋅ (1+1+1) contains five 1’s and there are no such expressions containing at most four 1’s. The investigation of this cute complexity measure was originated by Mahler and Popken in the 1950s. It is easy to see that ‖n‖/(log₃ n) ∈ [3, 3 log₂ 3] (∼ [3,4.755]) for every n, but the distribution of ‖n‖ is largely unknown. In this work, we focus on the restricted expressions obtained by applying Horner’s schema to a mixed binary-ternary representation of a given number in which we can arrange base-two and base-three digits in an arbitrary order. Let f(n) denote the minimum number of 1’s needed to express n in this way. Apparently, f(n) ≥ ‖n‖ for every n. We extensively investigate on f(n) via the combination of computer experiments and theoretical analysis and obtain the following set of results: (i) Computer experiments supporting the hypothesis that f(n)/log₃ n < 3.483 on average and f(n)/log₃ n < 4.212 for all n, (ii) For almost all natural numbers n, 3.120 < f(n)/log₃ n < 3.587, and (iii) There are infinitely many n’s such that f(n)/log₃ n > 3.934. Several new bounds on the original integer complexity are also presented in the paper.

Let MAJ_n denote the Boolean majority function of n input variables. In this paper, we study the construction of depth two circuits computing MAJ_n where each gate in a circuit computes MAJ_m for m < n. We first give an explicit construction of depth two MAJ_{floor[n/2]+2} o MAJ_{<= n-2} circuits computing MAJ_n for every n >= 7 such that n congruent 3 (mod 4) where MAJ_m and MAJ_{<= m} denote the majority gates that take m and at most m distinct inputs, respectively. A graph theoretic argument developed by Kulikov and Podolskii (STACS '17, Article No. 49) shows that there is no MAJ_{<= n-2} o MAJ_{n-2} circuit computing MAJ_n. Hence, our construction reveals that the use of a smaller fan-in gates at the bottom level is essential for the existence of such a circuit. Some computational results are also provided. We then show that the construction of depth two MAJ_m o MAJ_m circuits computing MAJ_n for m<n can be translated into the construction of a newly introduced version of bipartite expander graphs which we call a list expander. Intuitively, a list expander is a c-leftregular bipartite graph such that for a given d < c, every d-leftregular subgraph of the original graph has a certain expansion property. We formalize this connection and verify that, with high probability, a random bipartite graph is a list expander of certain parameters. However, the parameters obtained are not sufficient to give us a MAJ_{n-c} o MAJ_{n-c} circuit computing MAJ_n for a large constant c.

A plane tiling by the copies of a polyomino is called isohedral if every pair of copies in the tiling has a symmetry of the tiling that maps one copy to the other. We show that, for every $n$-omino (i.e., polyomino consisting of n cells), the number of non-equivalent isohedral tilings generated by 90 degree rotations, so called p4-tilings or quarter-turn tilings, is bounded by a constant (independent of n). The proof relies on the analysis of the factorization of the boundary word of a polyomino.

The sensitivity of a Boolean function is the maximum, over all inputs, of the number of input bits which when flipped change the output of the function. We enumerate all Boolean functions of sensitivity at most three and investigate their properties with the aid of computers. The number of NPN equivalence classes of nondegenerate n-variable Boolean functions of sensitivity three is 7, 80,4215,190221, 65694, 8873, 848, 64 and 8 for n = 3,4,..., 11 and zero for n ≥ 12. We verify that, over all these functions, the maximum of block sensitivity, certificate complexity, decision tree complexity and degree is 6, 6, 9 and 9, respectively. A key to making this enumeration possible is the fact that, for every nondegenerate Boolean function f, a subfunction f |xi=0 or f |xi=1 is nondegenerate for some variable xi, which was recently shown by Lee, Lokam, Tsai and Yang [in Proc. ISIT'15, pages 501-505]. We extend this result by showing that, the minimum number of nondegenerate subfunctions in {f|x i=0, f|x i=1}1 ≤ i ≤ nis, in fact, four.

We investigate the deterministic and the randomized decision tree complexities of Boolean functions, denoted by D(f) and R(f), respectively. A long standing conjecture is that, for every Boolean function f, R(f) = Ω(D(f)α) where [Saks-Wigderson, FOCS ‘86]. In this paper, we concentrate on the class of read-once Boolean functions and propose a promising approach to attack the conjecture for this class. Precisely, we give a statement about a property of a real-valued function whose correctness implies the conjecture for all read-once Boolean functions. So far we have not succeeded to prove this statement; however, we verified by computer calculation that the statement is “at least approximately true” that implies a lower bound of R(f) = Ω(D(f)0.99α) = Ω(D(f)0.746). This improves the best known lower bound of Ω(D(f)0.51) by Heiman and Wigderson [Comput. Complexity, 1991].

Recently, Rossman [STOC '08] established a lower bound of omega(nk/4) on the size of constant-depth circuits for the k-clique function on n-vertex graphs, which is the first lower bound that does not depend on the depth of circuits in the exponent of n. He showed, in fact, a stronger statement: Suppose fn: {0, 1}(n/2)rarr {0,1} is a sequence of functions computed by constant-depth circuits of size O(nt). For any positive integer k and 0-alpha) be an Erdos-Renyi random graph with edge probability n-alphaand let KAbe a k-clique on a uniformly chosen k vertices of G. Then fn(G) = fn(G cup KA) asymptotically almost surely. In this paper, we prove that this bound is essentially tight by showing that there exists a sequence of Boolean functions fn: {0, 1}(n/2)rarr {0, 1} that can be computed by constant-depth circuits of size O(nt) such that fn(G) ne fn(G cup KA) asymptotically almost surely for the same distributions with alpha = 1/(2t - 5.5) and k = 4t - c (where c is a small constant independent of k). This means that there are constant-depth circuits of size O(n(k/4+c)) that correctly compute the k-clique function with high probability when the input is a random graph with independent edge probability around n-2/(k-1). Several extensions of his lower bound method to the problem of detecting general patterns as well as some upper bounds are also described. In addition, we provide an explicit construction of DNF formulas that are almost incompressible by any constant-depth circuits.

In this paper, we investigate the lower bound on the number of gates in a Boolean circuit that computes the clique function with a limited number of negation gates. To derive strong lower bounds on the size of such a circuit we develop a new approach by combining three approaches: the restriction applied to constant depth circuits due to Håstad, the approximation method applied to monotone circuits due to Razborov, and the boundary covering developed in the present paper. We prove that if a circuit C with at most $\floor{(1/6) \log \log m}$ negation gates detects cliques of size $(\log m)^{3(\log m)^{1/2}}$ in a graph with m vertices, then C contains at least $2^{(1/5)(\log m)^{(\log m)^{1/2}}}$ gates. No nontrivial lower bounds on the size of such circuits were previously known, even if we restrict the number of negation gates to be a constant. Moreover, it follows from a result of Fischer [{\it Lect. Notes Comput. Sci.,} 33 (1974), pp. 71--82] that ifone can improve the number of negation gates from $\floor{(1/6)\log\log m}$ to $\floor{2\log m}$ in the statement, then we have P $\neq$ NP. We also show that the problem of lower bounding the negation-limited circuit complexity can be reduced to the one of lower bounding the maximum of the monotone circuit complexity of the functions in a certain class of monotone functions.

Developing certain techniques for the approximation method, we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of size s in a graph with m vertices: For $5 \leq s \leq m/4$, a monotone circuit computing CLIQUE$(m,s)$ contains at least $(1/2)1.8^{\min(\sqrt{s-1}/2, m/(4s))}$ gates: If a nonmonotone circuit computes CLIQUE using a "small" amount of negation, then the circuit contains an exponential number of gates. The former is proved by using so-called bottleneck counting argument within the framework of approximation, and the latter is verified by introducing a notion of restricting negation in circuits and generalizing these arguments to nonmonotone cases.

Developing some techniques for the approximation method, we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of size s in a graph with m vertices. For 5/spl les/s/spl les/m/4, a monotone circuit computing CLIQUE(m, s) contains at least (1/2) 1.8/sup min(/spl radic/s-1/2,m/(4s))/ gates. If a non-monotone circuit computes CLIQUE using a "small" amount of negation, then the circuit contains an exponential number of gates. The former is proved very simply using so called bottleneck counting argument within the framework of approximation, whereas the latter is verified introducing a notion of restricting negation and generalizing the sunflower contraction.