Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Near-Optimal Asymmetric Binary Matrix Partitions Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Parallel Identity Testing for Skew Circuits with Big Powers and Applications

Authors : Daniel König, Markus Lohrey

Published in: Mathematical Foundations of Computer Science 2015

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

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].

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Faster Lightweight Lempel-Ziv Parsing
next chapter On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
Literature
1.
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.
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.
Metadata
Title
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
Authors
Daniel König
Markus Lohrey
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Mathematical Foundations of Computer Science 2015

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

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

Copyright Year: 2015

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

Premium Partner

    Image Credits