[Proof Complexity] MIAO seminar Thu Oct 19 14:00 with Bruno Pasqualotto Cavalar: Constant-depth circuits vs. monotone circuits

[Jakob Nordström]

Dear all,

With apologies for the somewhat short notice, we are happy to announce that on Thursday October 19 at 14:00 we will have the opportunity to enjoy a seminar with Bruno Pasqualotto Cavalar from the University of Warwick, who will give a talk titled "Constant-depth circuits vs. monotone circuits". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are warmly welcome to room N116A at Universitetsparken 1. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can usually be found with somewhat better forward notice at http://www.jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Thursday Oct 19 14:00 in room N116A, Universitetsparken 1, and on Zoom
Constant-depth circuits vs. monotone circuits
(Bruno Pasqualotto Cavalar, University of Warwick)

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

- For every k ≥ 1, there is a monotone function in AC0 (constant-depth poly-size circuits) that requires monotone circuits of depth Ω(logkn). This significantly extends a classical result of Okol’nishnikova (1982) and Ajtai and Gurevich (1987).
- For every k ≥ 1, there is a monotone function in AC0[⊕] (constant-depth poly-size circuits extended with parity gates) that requires monotone circuits of size exp (Ω(logkn)). This makes progress towards a question posed by Grigni and Sipser (1992).

In the opposite direction, we observe that non-trivial simulations are possible in the absence of parity gates: every monotone function computed by an AC0 circuit of size s and depth d can be computed by a monotone circuit of size 2n − n/O(log s)d − 1. We show that the existence of significantly faster monotone simulations would lead to breakthrough circuit lower bounds. In particular, if every monotone function in AC0 admits a polynomial size monotone circuit, then NC2 is not contained in NC1.

Finally, we revisit our separation result against monotone circuit size and investigate the limits of our approach, which is based on a monotone lower bound for constraint satisfaction problems established by Göös et al. (2019) via lifting techniques. Adapting results of Schaefer (1978) and Allender et al. (2009), we obtain an unconditional classification of the monotone circuit complexity of Boolean-valued CSPs via their polymorphisms. This result and the consequences we derive from it might be of independent interest.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se