nach oben

Theory of Computing Systems

Erschienen in:

01.02.2014

Balancing Bounded Treewidth Circuits

verfasst von: Maurice Jansen, Jayalal Sarma

Erschienen in: Theory of Computing Systems | Ausgabe 2/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in arithmetic formulas of depth O(k ²logn). From this we derive an analogous statement for syntactically multilinear arithmetic circuits, which strengthens the central theorem of M. Mahajan and B.V.R. Rao (Proc. 33rd International Symposium on Mathematical Foundations of Computer Science, vol. 5162, pp. 455–466, 2008). We show our main construction has the following three applications:

Bounded width arithmetic circuits of size n ^O(1) can be balanced to depth O(logn), provided chains of iterated multiplication in the circuit are of length O(1).
Boolean bounded fan-in circuits of size n ^O(1) and treewidth k can be simulated by bounded fan-in formulas of depth O(k ²logn). This strengthens in the non-uniform setting the known inclusion that SC⁰⊆NC¹.
We demonstrate treewidth restricted cases of Directed-Reachability and Circuit Value Problem that can be solved in LogDCFL.

We also give a construction showing, for both arithmetic and Boolean circuits, that any circuit of size n ^O(1) and treewidth O(logⁱ n) can be simulated by a circuit of width O(logⁱ⁺¹ n) and size n ^c, where c=O(1), if i=0, and c=O(loglogn) otherwise.

Vorheriger Artikel Encoding Invariance in Average Case Complexity

Nächster Artikel Validating the Knuth-Morris-Pratt Failure Function, Fast and Online

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 "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

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

For a definition see Sect. 2.

It is possible to improve this to LogDCFL-uniform, by observing that over GF(2) our main construction can be implemented on a log-space Turing machine that uses a stack, where the latter does not count towards the space usage.

We indicate this with the prefix $\mbox {$\mathrm {md}$-}$. See Sect. 2 for a definition.

Allender, E.: Reachability problems: an update. In: Computation and Logic in the Real World. Lect. Notes in Comp. Sci., vol. 4497, pp. 25–27. Springer, Berlin (2007) CrossRef

Arvind, V., Joglekar, P., Srinivasan, S.: On lower bounds for constant width arithmetic circuits. ISAAC 2009. Technical Report ECCC TR09-73, Electronic Colloquium in Computational Complexity (2009, to appear)

Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. In: Proc. 20th Annual ACM Symposium on the Theory of Computing, pp. 254–257 (1988)

Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: Proc. 14th Workshop on Graph-Theoretic Concepts in Comp. Sc. (WG’88). LNCS, vol. 344, pp. 1–10. Springer, Berlin (1989) CrossRef

Brent, R.: The parallel evaluation of general arithmetic expressions. J. ACM 21, 201–206 (1974) CrossRefMATHMathSciNet

Bürgisser, P., Claussen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Springer, Berlin (1997) CrossRefMATH

Das, B., Datta, S., Nimbhorkar, P.: Log-space algorithms for paths and matchings in k-trees. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010). Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 215–226 (2010)

Goldschlager, L.M.: The monotone and planar circuit value problems are logspace comp lete for P. SIGACT News 9(2), 25–29 (1977) CrossRef

Jansen, M., Rao, B.V.R.: Simulation of arithmetical circuits by branching programs with preservation of constant width and syntactic multilinearity. In: Proceedings of the 4th International Computer Science Symposium in Russia (CSR2009). Lect. Notes in Comp. Sci., vol. 5675, pp. 179–190. Springer, Berlin (2009)

10.

Jones, N.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11, 68–85 (1975). Corrigendum: J. Comput. Syst. Sci. 15, 241 (1977) CrossRefMATH

11.

Limaye, N., Mahajan, M., Jayalal Sarma, M.N.: Upper bounds for monotone planar circuit value and variants. Comput. Complex. 18(3), 377–412 (2009) CrossRefMATH

12.

Mahajan, M.: Polynomial size log depth circuits: between NC¹ and AC¹. Technical Report 91, BEATCS Computational Complexity Column (2007)

13.

Mahajan, M., Rao, B.V.R.: Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae. In: Proc. 33rd International Symposium on Mathematical Foundations of Computer Science. Lect. Notes in Comp. Sci., vol. 5162, pp. 455–466 (2008)

14.

Mahajan, M., Rao, B.V.R.: Small-space analogues of Valiant’s classes. In: Proc. 17th International Conference on Fundamentals of Computation Theory. Lect. Notes in Comp. Sci., vol. 5699, pp. 455–466 (2009)

15.

Malod, G., Portier, N.: Characterizing Valiant’s algebraic complexity classes. J. Complex. 24(1), 16–38 (2008) CrossRefMATHMathSciNet

16.

Mix Barrington, D.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. In: Proc. 18th Annual ACM Symposium on the Theory of Computing, pp. 1–5 (1986)

17.

Mix Barrington, D.A., Lu, C.-J., Bro Miltersen, P., Skyum, S.: On monotone planar circuits. In: IEEE Conference on Computational Complexity, pp. 24–31 (1999)

18.

Raz, R.: Separation of multilinear circuit and formula size. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 344–351 (2004) CrossRef

19.

Reingold, O.: Undirected st-connectivity in log-space. In: Proc. 37th Annual ACM Symposium on the Theory of Computing, pp. 376–385 (2005)

20.

Savitch, W.J.: Maze recognizing automata and nondeterministic tape complexity. J. Comput. Syst. Sci. 7(4), 389–403 (1973) CrossRefMATHMathSciNet

21.

Till Tantau, Elberfeld, M., Jakoby, A.: Logspace versions of the theorems of bodlaender and courcelle. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). Technical report ECCC-TR10-062 (2010)

22.

Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12, 641–644 (1983) CrossRefMATHMathSciNet

Titel: Balancing Bounded Treewidth Circuits
verfasst von: Maurice Jansen
Jayalal Sarma
Publikationsdatum: 01.02.2014
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2014
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-013-9519-3

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2014

Editor’s Note

Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

Obtaining Online Ecological Colourings by Generalizing First-Fit

On Equilibria in Quantitative Games with Reachability/Safety Objectives

Quotient Complexity of Closed Languages

Approximating the Minimum Length of Synchronizing Words Is Hard