Anurag Ajay, Seungwook Han, et al.
NeurIPS 2023
In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula P(P) is (semantically) monotone in a predicate symbol P on finite structures. Is P(P) necessarily equivalent on finite structures to a first-order formula with only positive occurrences of P? In this paper, this question is answered negatively. Moreover, the counterexample naturally gives a uniform sequence of constant-depth, polynomial-size, monotone Boolean circuits that is not equivalent to any (however nonuniform) sequence of constant-depth, polynomial-size, positive Boolean circuits. © 1987, ACM. All rights reserved.
Anurag Ajay, Seungwook Han, et al.
NeurIPS 2023
Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008
Jihun Yun, Peng Zheng, et al.
ICML 2019