No Access

Randomized feasible interpolation and monotone circuits with a local oracle

Jan Krajíček

Department of Algebra, Faculty of Mathematics and Physics, Charles University, Sokolovská 83, Prague 8, CZ 186 75, The Czech Republic

E-mail Address: krajicek@karlin.mff.cuni.cz

Search for more papers by this author

https://doi.org/10.1142/S0219061318500125Cited by:4 (Source: Crossref)

Abstract

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic62(2) (1997) 457–486] allows to derive from some short semantic derivations (e.g. in resolution) of the disjointness of two $NP$ sets $U$ and $V$ a small communication protocol (a general dag-like protocol in the sense of Krajíček (1997) computing the Karchmer–Wigderson multi-function $K W [U, V]$ associated with the sets, and such a protocol further yields a small circuit separating $U$ from $V$ . When $U$ is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function $K W^{m} [U, V]$ and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart.44(4) (1998) 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity (e.g. to the cutting planes proof system CP). In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle (CLOs), that does correspond to communication protocols for $K W^{m} [U, V]$ making errors. The new randomized feasible interpolation thus shows that a short semantic derivation (from a certain class of derivations larger than in the original method) of the disjointness of $U, V$ , $U$ closed upwards, yields a small randomized protocol for $K W^{m} [U, V]$ and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system $R(LIN / F_{2})$ operating with clauses formed by linear Boolean functions over $F_{2}$ . The new randomized feasible interpolation applies to this proof system and also to (the semantic versions of) cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic63(4) (1998) 1582–1596] (system R(CP)) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic79(2) (2014) 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs.

Keywords:

References

1. M. Alekhnovich, E. Ben-Sasson, A. A. Razborov and A. Wigderson, Pseudorandom generators in propositional proof complexity, SIAM J. Comput. 34(1) (2004) 67–88. Web of Science, Google Scholar
2. N. Alon and R. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica 7(1) (1987) 1–22. Web of Science, Google Scholar
3. R. Boppana and M. Sipser, The complexity of finite functions, in Handbook of Theoretical Computer Science (Elsevier Science Publishers, 1990), pp. 759–804. Google Scholar
4. S. R. Buss, R. Impagliazzo, J. Krajíček, P. Pudlák, A. A. Razborov and J. Sgall, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Comput. Complex. 6(3) (1996/1997) 256–298. Web of Science, Google Scholar
5. S. R. Buss, L. A. Kolodziejczyk and N. Thapen, Fragments of approximate counting, J. Symbolic Logic 79(2) (2014) 496–525. Web of Science, Google Scholar
6. S. R. Buss, L. A. Kolodziejczyk and K. Zdanowski, Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, Trans. Amer. Math. Soc. 367 (2015) 7517–7563. Web of Science, Google Scholar
7. M. Clegg, J. Edmonds and R. Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, in Proc. 28th Annual ACM Symp. on Theory of Computing (ACM Press, 1996), pp. 174–183. Google Scholar
8. E. Hirsch and A. Kojevnikov, Several notes on the power of Gomory-Chvatal cuts, Ann. Pure Appl. Logic 141 (2006) 429–436. Web of Science, Google Scholar
9. R. Impagliazzo, T. Pitassi and A. Urquhart, Upper and lower bounds for treelike cutting planes proofs, in Proc. 9th Annual IEEE Symp. on Logic in Computer Science (IEEE Computer Science Press, 1994), pp. 220–228. Google Scholar
10. D. Itsykson and D. Sokolov, Lower bounds for splittings by linear combinations, in Int. Symp. on Mathematical Foundations of Computer Science, eds. E. Csuhaj-Varju, M. Dietzfelbinger and Z. Esik, Lecture Notes in Computer Science (Springer, 2014), pp. 372–383. Google Scholar
11. S. Jukna, Monotone circuits and local computations, in Proc. of 31st Conf. of Lithuanian Math. Soc. (1990). Google Scholar
12. M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super — Logarithmic depth, in Proc. 20th Annual ACM Symp. on Theory of Computing (ACM Press, 1988), pp. 539–550. Google Scholar
13. A. Kojevnikov, Improved lower bounds for tree-like resolution over linear inequalities, in Proc. 10th Int. Conf. on Theory and Applications of Satisfiability Testing (SAT), eds. J. Marques-Silva and K. A. Sakallah, Lecture Notes in Computer Science, Vol. 4501 (Springer, 2007), pp. 70–79. Google Scholar
14. J. Krajíček, Bounded Arithmetic, Propositional Logic, and Complexity Theory, Encyclopedia of Mathematics and Its Applications, Vol. 60 (Cambridge University Press, 1995). Google Scholar
15. J. Krajíček, Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus, in 22nd Int. Symp. Mathematical Foundations of Computer Science, eds. I. Prívara and P. Ru̇žička, Lecture Notes in Computer Science, Vol. 1295 (Springer-Verlag, 1997), pp. 85–90. Google Scholar
16. J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62(2) (1997) 457–486. Web of Science, Google Scholar
17. J. Krajíček, Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63(4) (1998) 1582–1596. Web of Science, Google Scholar
18. J. Krajíček, Interpolation by a game, Math. Logic Quart. 44(4) (1998) 450–458. Web of Science, Google Scholar
19. J. Krajíček, On the weak pigeonhole principle, Fund. Math. 170(1–3) (2001) 123–140. Web of Science, Google Scholar
20. J. Krajíček, A feasible interpolation for random resolution, to appear in Logical Methods in Computer Science, preprint (2016), https://arxiv.org/abs/1604.06560. Google Scholar
21. J. Krajíček and I. C. Oliveira, On monotone circuits with local oracles and clique lower bounds, Chicago Journal of Theoretical Computer Science 2018, 1–18. https://doi.org/10.4086/cjtcs.2018.001 Google Scholar
22. N. Nisan, The communication complexity of the threshold gates, Combinatorics 1 (1993) 301–315. Google Scholar
23. P. Pudlák, Lower bounds for resolution and cutting planes proofs and monotone computations, J. Symbolic Logic 62 (1987) 981–998. Web of Science, Google Scholar
24. P. Pudlák, The lengths of proofs, in Handbook of Proof Theory, ed. S. R. Buss (Elsevier, 1998), pp. 547–637. Google Scholar
25. P. Pudlák and N. Thapen, Random resolution refutations, http://eccc.hpi-web.de/report/2016/175/. Google Scholar
26. R. Raz and I. Tzameret, Resolution over linear equations and multilinear proofs, Ann. Pure Appl. Logic 155(3) (2008) 194–224. Web of Science, Google Scholar
27. R. Raz and A. Wigderson, Probabilistic communication complexity of Boolean relations (extended abstract), in Proc. 30th Foundations of Computer Science (FOCS) (IEEE, 1989), pp. 562–567. Google Scholar
28. R. Raz and A. Wigderson, Monotone circuits for matching require linear depth, J. Assoc. Comput. Mach. 39(3) (1992) 736–744. Web of Science, Google Scholar
29. A. A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, Sov. Math. Dokl. 31 (1985) 354–357. Google Scholar
30. A. A. Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Mat. Zametki 41(4) (1987) 598–607. Google Scholar
31. A. A. Razborov, Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic, Izv. Ross. Akad. Nauk Ser. Mat. 59(1) (1995) 201–224. Google Scholar
32. A. A. Razborov, Lower bounds for the polynomial calculus, Comput. Complex. 7(4) (1998) 291–324. Web of Science, Google Scholar
33. R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. 19th Ann. ACM Symp. Theory of Computing (New York, 1987), pp. 77–82. Google Scholar
34. A. C.-C. Yao, Circuits and local computation, in Proc. of the 21st Annual ACM Symp. on Theory of Computing (ACM, New York, 1989), pp. 186–196. Google Scholar