nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

The New Complexity Landscape Around Circuit Minimization

verfasst von : Eric Allender

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We survey recent developments related to the Minimum Circuit Size Problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases

If the reader is not familiar with Kolmogorov complexity, then we recommend some excellent books on this topic [17, 33].

Allender, E.: The complexity of complexity. In: Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A., Rosamond, F. (eds.) Computability and Complexity. LNCS, vol. 10010, pp. 79–94. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-50062-1_6CrossRefMATH

Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35, 1467–1493 (2006). https://doi.org/10.1137/050628994MathSciNetCrossRefMATH

Allender, E., Das, B.: Zero knowledge and circuit minimization. Inf. Comput. 256, 2–8 (2017). https://doi.org/10.1016/j.ic.2017.04.004. Special issue for MFCS 2014MathSciNetCrossRefMATH

Allender, E., Grochow, J., van Melkebeek, D., Morgan, A., Moore, C.: Minimum circuit size, graph isomorphism and related problems. SIAM J. Comput. 47, 1339–1372 (2018). https://doi.org/10.1137/17M1157970MathSciNetCrossRefMATH

Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., Saks, M.E.: Minimizing disjunctive normal form formulas and AC\(^{\text{0 }} \) circuits given a truth table. SIAM J. Comput. 38(1), 63–84 (2008). https://doi.org/10.1137/060664537MathSciNetCrossRefMATH

Allender, E., Hirahara, S.: New insights on the (non)-hardness of circuit minimization and related problems. ACM Trans. Comput. Theory (ToCT) 11(4), 27:1–27:27 (2019). https://doi.org/10.1145/3349616MathSciNetCrossRefMATH

Allender, E., Holden, D., Kabanets, V.: The minimum oracle circuit size problem. Comput. Complex. 26(2), 469–496 (2017). https://doi.org/10.1007/s00037-016-0124-0MathSciNetCrossRefMATH

Allender, E., Ilango, R., Vafa, N.: The non-hardness of approximating circuit size. In: van Bevern, R., Kucherov, G. (eds.) CSR 2019. LNCS, vol. 11532, pp. 13–24. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19955-5_2CrossRef

Allender, E., Koucký, M.: Amplifying lower bounds by means of self-reducibility. J. ACM 57, 14:1–14:36 (2010). https://doi.org/10.1145/1706591.1706594MathSciNetCrossRefMATH

10.

Allender, E., Koucký, M., Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77, 14–40 (2010). https://doi.org/10.1016/j.jcss.2010.06.004MathSciNetCrossRefMATH

11.

Carmosino, M., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: 31st Conference on Computational Complexity, CCC. LIPIcs, vol. 50, pp. 10:1–10:24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https://doi.org/10.4230/LIPIcs.CCC.2016.10

12.

Chen, L., Hirahara, S., Oliveira, I.C., Pich, J., Rajgopal, N., Santhanam, R.: Beyond natural proofs: hardness magnification and locality. In: 11th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, vol. 151, pp. 70:1–70:48. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.70

13.

Chen, L., Jin, C., Williams, R.: Hardness magnification for all sparse NP languages. In: Symposium on Foundations of Computer Science (FOCS), pp. 1240–1255 (2019)

14.

Chen, L., Jin, C., Williams, R.: Sharp threshold results for computational complexity (2019). Manuscript

15.

Chen, L., McKay, D.M., Murray, C.D., Williams, R.R.: Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. In: 34th Computational Complexity Conference (CCC). LIPIcs, vol. 137, pp. 30:1–30:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.CCC.2019.30

16.

Cheraghchi, M., Kabanets, V., Lu, Z., Myrisiotis, D.: Circuit lower bounds for MCSP from local pseudorandom generators. In: 46th International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 132, pp. 39:1–39:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.39

17.

Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, New York (2010). https://doi.org/10.1007/978-0-387-68441-3CrossRefMATH

18.

Golovnev, A., Ilango, R., Impagliazzo, R., Kabanets, V., Kolokolova, A., Tal, A.: AC\(^0[p]\) lower bounds against MCSP via the coin problem. In: 46th International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 132, pp. 66:1–66:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.66

19.

Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 247–258 (2018). https://doi.org/10.1109/FOCS.2018.00032

20.

Hirahara, S.: Kolmogorov-randomness is harder than expected (2019). Manuscript

21.

Hirahara, S.: Unexpected power of random strings. In: 11th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 151, pp. 41:1–41:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.41

22.

Hirahara, S., Oliveira, I.C., Santhanam, R.: NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In: 33rd Conference on Computational Complexity, CCC. LIPIcs, vol. 102, pp. 5:1–5:31. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https://doi.org/10.4230/LIPIcs.CCC.2018.5

23.

Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: 32nd Conference on Computational Complexity, CCC. LIPIcs, vol. 79, pp. 7:1–7:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.CCC.2017.7

24.

Hirahara, S., Watanabe, O.: On nonadaptive reductions to the set of random strings and its dense subsets. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 26, p. 25 (2019)

25.

Hitchcock, J.M., Pavan, A.: On the NP-completeness of the minimum circuit size problem. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). LIPIcs, vol. 45, pp. 236–245. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). https://doi.org/10.4230/LIPIcs.FSTTCS.2015.236

26.

Ilango, R.: Personal communication (2019)

27.

Ilango, R.: Approaching MCSP from above and below: Hardness for a conditional variant and AC\(^0[p]\). In: 11th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 151, pp. 34:1–34:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.34

28.

Ilango, R., Loff, B., Oliveira, I.C.: NP-hardness of minimizing circuits and communication (2019). Manuscript

29.

Impagliazzo, R., Kabanets, V., Volkovich, I.: The power of natural properties as oracles. In: 33rd Conference on Computational Complexity, CCC. LIPIcs, vol. 102, pp. 7:1–7:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https://doi.org/10.4230/LIPIcs.CCC.2018.7

30.

Kabanets, V., Cai, J.Y.: Circuit minimization problem. In: ACM Symposium on Theory of Computing (STOC), pp. 73–79 (2000). https://doi.org/10.1145/335305.335314

31.

Ko, K.: On the notion of infinite pseudorandom sequences. Theor. Comput. Sci. 48(3), 9–33 (1986). https://doi.org/10.1016/0304-3975(86)90081-2MathSciNetCrossRefMATH

32.

Levin, L.A.: Randomness conservation inequalities; information and independence in mathematical theories. Inf. Control 61(1), 15–37 (1984). https://doi.org/10.1016/S0019-9958(84)80060-1MathSciNetCrossRefMATH

33.

Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science, 4th edn. Springer (2019). https://doi.org/10.1007/978-3-030-11298-1

34.

McKay, D.M., Murray, C.D., Williams, R.R.: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1215–1225 (2019). https://doi.org/10.1145/3313276.3316396

35.

Murray, C., Williams, R.: On the (non) NP-hardness of computing circuit complexity. Theory Comput. 13(4), 1–22 (2017). https://doi.org/10.4086/toc.2017.v013a004MathSciNetCrossRef

36.

Oliveira, I., Santhanam, R.: Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In: 32nd Conference on Computational Complexity, CCC. LIPIcs, vol. 79, pp. 18:1–18:49. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.CCC.2017.18

37.

Oliveira, I.C.: Randomness and intractability in Kolmogorov complexity. In: 46th International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 132, pp. 32:1–32:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.32

38.

Oliveira, I.C., Pich, J., Santhanam, R.: Hardness magnification near state-of-the-art lower bounds. In: 34th Computational Complexity Conference (CCC). LIPIcs, vol. 137, pp. 27:1–27:29. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.CCC.2019.27

39.

Oliveira, I.C., Santhanam, R.: Hardness magnification for natural problems. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 65–76 (2018). https://doi.org/10.1109/FOCS.2018.00016

40.

Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965–984 (1988). https://doi.org/10.1145/48014.63140MathSciNetCrossRefMATH

41.

Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM 40(1), 95–142 (1993). https://doi.org/10.1145/138027.138042MathSciNetCrossRefMATH

42.

Razborov, A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55, 24–35 (1997). https://doi.org/10.1006/jcss.1997.1494MathSciNetCrossRefMATH

43.

Santhanam, R.: Pseudorandomness and the minimum circuit size problem. In: 11th Innovations in Theoretical Computer Science Conference (ITCS), LIPIcs, vol. 151, pp. 68:1–68:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.68

44.

Santhanam, R.: Why are proof complexity lower bounds hard? In: Symposium on Foundations of Computer Science (FOCS), pp. 1305–1324 (2019)

45.

Tal, A.: The bipartite formula complexity of inner-product is quadratic. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 23, p. 181 (2016)

46.

Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, New York Inc. (1999). https://doi.org/10.1007/978-3-662-03927-4CrossRefMATH

Titel: The New Complexity Landscape Around Circuit Minimization
verfasst von: Eric Allender
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"