Low-depth uniform threshold circuits and the bit-complexity of straight line programs

Eric Allender, Nikhil Balaji, Samir Datta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We present improved uniform TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of "majority depth" (as studied by Maciel and Thérien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings
PublisherSpringer Verlag
Pages13-24
Number of pages12
EditionPART 2
ISBN (Print)9783662444641
DOIs
StatePublished - 2014
Event39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 - Budapest, Hungary
Duration: Aug 25 2014Aug 29 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume8635 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
CountryHungary
CityBudapest
Period8/25/148/29/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Low-depth uniform threshold circuits and the bit-complexity of straight line programs'. Together they form a unique fingerprint.

Cite this