We show the following hardness results for monotone learning and approximation of monotone circuit size: 1) Under the Randomised Exponential-Time Hypothesis (rETH), it requires time n^{Ω(log n)} to PAC-learn monotone formulas with n input bits and size s(n) = n by monotone circuits of size n^{(log n)^{1-ε}}, for every ε > 0. 2) Under the Randomised Exponential-Time Hypothesis (rETH), for any δ > 0, there is a polynomially bounded function m such that m^{1-δ}-multiplicatively approximating the minimum monotone circuit size of a monotone function consistent with a sequence of m(n) labelled examples {(x_i, b_i)} over n-bit inputs requires time m^{Ω(log(m))}. Our results are shown by a novel application of lifting arguments in proof and communication complexity to hardness of monotone learning, by building on the seminal result of Atserias and Müller [Atserias and Müller, 2020] on hardness of automating Resolution proofs.

We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.

We study the power of negation in the Boolean and algebraic settings and show the following results.

We show that the perfect matching function on n-vertex graphs requires monotone circuits of size 2nΩ(1). This improves on the nΩ(logn) lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.

We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone in monadic predicates but not definable in FO+. This provides a simple proof that Lyndon's preservation theorem fails on finite structures. We lift this example language to finite graphs, thereby providing a new result of independent interest for FO-definable graph classes: negation might be needed even when the class is closed under addition of edges. We finally show that the problem of whether a given regular language of finite words is definable in FO+ is undecidable.

Abstract In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among them, we show Average-case Lower Bounds For every $$k = k(n)$$ k = k ( n ) with $$k \geqslant \log n$$ k ⩾ log n , there exists a polynomial-time computable function $$f_k$$ f k on n bits such that, for every comparator circuit C with at most $$n^{1.5}/O\!\left( k\cdot \sqrt{\log n}\right) $$ n 1.5 / O k · log n gates, we have $$\begin{aligned} \mathop {{{\,\mathrm{\textbf{Pr}}\,}}}\limits _{x\in \left\{ 0,1\right\} ^n}\left[ C(x)=f_k(x)\right] \leqslant \frac{1}{2} + \frac{1}{2^{\Omega (k)}}. \end{aligned}$$ Pr x ∈ 0 , 1 n C ( x ) = f k ( x ) ⩽ 1 2 + 1 2 Ω ( k ) . This average-case lower bound matches the worst-case lower bound of Gál and Robere by letting $$k=O\!\left( \log n\right) $$ k = O log n . $$\#$$ # SAT Algorithms There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most $$n^{1.5}/O\!\left( k\cdot \sqrt{\log n}\right) $$ n 1.5 / O k · log n gates, in time $$2^{n-k}\cdot {{\,\textrm{poly}\,}}(n)$$ 2 n - k · poly

Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite having been studied for nearly three decades, the first superlinear lower bound against comparator circuits was proved only recently by Gál and Robere (ITCS 2020), who established a Ω((n/log n)^{1.5}) lower bound on the size of comparator circuits computing an explicit function of n bits. In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among them, we show - Average-case Lower Bounds. For every k = k(n) with k ≥ log n, there exists a polynomial-time computable function f_k on n bits such that, for every comparator circuit C with at most n^{1.5}/O(k⋅ √{log n}) gates, we have Pr_{x ∈ {0,1}ⁿ} [C(x) = f_k(x)] ≤ 1/2 + 1/{2^{Ω(k)}}. This average-case lower bound matches the worst-case lower bound of Gál and Robere by letting k = O(log n). - #SAT Algorithms. There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n^{1.5}/O (k⋅ √{log n}) gates, in time 2^{n-k} · poly(n), for any k ≤ n/4. The running time is non-trivial (i.e., 2ⁿ/n^{ω(1)}) when k = ω(log n). - Pseudorandom Generators and MCSP Lower Bounds. There is a pseudorandom generator of seed length s^{2/3+o(1)} that fools comparator circuits with s gates. Also, using this PRG, we obtain an n^{1.5-o(1)} lower bound for MCSP against comparator circuits.

Abstract Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275–310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51:1–13, 2018), and recent advances on the Erdős-Rado sunflower conjecture Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a w-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $$\exp (n^{1/2-o(1)})$$ exp ( n 1 / 2 - o ( 1 ) ) lower bound on the monotone circuit size of an explicit n-variate monotone function, improving the previous best known $$\exp (n^{1/3-o(1)})$$ exp ( n 1 / 3 - o ( 1 ) ) due to Andreev (Algebra and Logic, 26:1–18, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an $$\exp (\varOmega (n))$$ exp ( Ω ( n ) ) lower bound on the monotone arithmetic circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $$n^{\varOmega (k)}$$ n Ω ( k ) lower bound on the monotone circuit size of the CLIQUE function for all $$k \leqslant n^{1/3-o(1)}$$ k ⩽ n 1 / 3 - o ( 1 ) , strengthening the bound of Alon and Boppana (Combinatorica, 7:1–22, 1987).

For graphs $G$ and $H$, let $G \overset{\mathrm{rb}}{\longrightarrow} H$ denote the property that for every proper edge colouring of $G$ there is a rainbow copy of $H$ in $G$. Extending a result of Nenadov, Person, Škorić and Steger [J. Combin. Theory Ser. B 124 (2017),1-38], we determine the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} C_\ell$ for cycles $C_\ell$ of any given length $\ell \geq 4$.

If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec H$ to say that every orientation of the edges of $G$ contains $\vec H$ as a subdigraph. We consider the case in which $G$ is the binomial random graph $G(n,p)$, establishing the threshold $p_{\vec H}=p_{\vec H}(n)$ for the property $G(n,p)\to \vec H$ for the cases in which $\vec H$ is an acyclic orientation of a complete graph or of a cycle.