Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Near-Optimal Asymmetric Binary Matrix Partitions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Parallel Identity Testing for Skew Circuits with Big Powers and Applications

verfasst von : Daniel König, Markus Lohrey

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labelled with powers \(x^n\) for binary encoded numbers n. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to \(\mathsf {coRNC}^2\), which generalizes a corresponding result for (standard) skew circuits. Two applications of this result are presented: (i) Equivalence of higher-dimensional straight-line programs can be tested in \(\mathsf {coRNC}^2\); this result is even new in the one-dimensional case, where the straight-line programs produce strings. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products belongs to \(\mathsf {coRNC}^2\). Full proofs can be found in the long version [13].

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
Vorheriges Kapitel Faster Lightweight Lempel-Ziv Parsing
Nächstes Kapitel On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
Literatur
1.
Agrawal, M., Biswas, S.: Primality and identity testing via Chinese remaindering. J. Assoc. Comput. Mach. 50(4), 429–443 (2003)MathSciNetCrossRefMATH
2.
Beaudry, M., McKenzie, P., Péladeau, P., Thérien, D.: Finite monoids: from word to circuit evaluation. SIAM J. Comput. 26(1), 138–152 (1997)MathSciNetCrossRefMATH
3.
Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J. Comput. Syst. Sci. 65(2), 332–350 (2002)MathSciNetCrossRefMATH
4.
5.
Fich, F.E., Tompa, M.: The parallel complexity of exponentiating polynomials over finite fields. J. Assoc. Comput. Mach. 35(3), 651–667 (1988)MathSciNetCrossRefMATH
6.
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: \({P}\)-Completeness Theory. Oxford University Press, Oxford (1995)MATH
7.
Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65, 695–716 (2002)MathSciNetCrossRefMATH
8.
Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theor. Comput. Sci. 158(1&2), 143–159 (1996)MathSciNetCrossRefMATH
9.
Ibarra, O.H., Moran, S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J. Assoc. Comput. Mach. 30(1), 217–228 (1983)MathSciNetCrossRefMATH
10.
Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the STOC 1997, pp. 220–229. ACM Press (1997)
11.
Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1–2), 1–46 (2004)MathSciNetCrossRefMATH
12.
König, D., Lohrey, M.: Evaluating matrix circuits. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 235–248. Springer, Heidelberg (2015)CrossRef
13.
14.
15.
Lohrey, M.: Algorithmics on SLP-compressed strings: asurvey. Groups Complex. Cryptol. 4(2), 241–299 (2012)MathSciNetMATH
16.
Lohrey, M.: The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer, New York (2014)CrossRefMATH
17.
Lohrey, M., Steinberg, B., Zetzsche, G.: Rational subsets and submonoids of wreath products. Inf. Comput. 243, 191–204 (2015)MathSciNetCrossRefMATH
18.
Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183–198 (1997)MathSciNetCrossRefMATH
19.
Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Amer. Math. Soc. Transl. Ser. 2(9), 1–122 (1958)MATH
20.
Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460–470. Springer, Heidelberg (1994) CrossRef
21.
Metadaten
Titel
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
verfasst von
Daniel König
Markus Lohrey
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48054-0_37