D A Barrington
- Aj83.M. Ajtai, 'E~ formulae on finite structures', Annals of Pure and Applied Logic 24 (1983), 1-48.Google Scholar
Cross Ref
- ABHKST86.M. Ajtai, L. Bahai, P. Hajnal, J. KomlSs, E. Szemer~di, and G. Turin, 'Two lower bounds for branching programs', these proceedings. Google ScholarDigital Library
- Ba85.D. A. Barrington, 'Width-3 permutation branching programs', Technical Memorandum TM-293, M.I.T. Laboratory for Computer Science.Google Scholar
- BCH84.P. W. Beame, S. A. Cook, and H. J. Hoover, 'Logdepth circuits for division and related problems', Proc. 25th IEEE FOCS, 1984, 1-6.Google Scholar
- BDFP83.A. Borodin, D. Dolev, F. E. Fich, and W. Paul, 'Bounds for width two branching programs', Proc. 15th ACM STOC, 1983, 87-93. Google ScholarDigital Library
- Be73.C. H. Bennett, 'Logical reversibility of computation', IBM Journal of Research and Development, 17 (1973), 525-532.Google ScholarDigital Library
- CFL83.A. K. Chandra, M. L. Furst, and R. J. Lipton, 'Multiparty protocols', Proc. 15th ACM STOC, 1983, 94-99. Google ScholarDigital Library
- Co85.S. A. Cook, 'The taxonomy of problems with fast parallel algorithms', Information and Control 64 (Jan. 1985) 2-22. Google ScholarDigital Library
- FKPS84.R. Fagin, M. M. Klawe, N. J. Pippenger, and L. Stochmeyer, 'Bounded depth, polynomial-size circuits for symmetric functions', IBM Report RJ 4040 (45198) (October 1983), IBM Research Laboratory, San Jose.Google Scholar
- FSSS1.M, Furst, J. B. Saxe, and M. Sipser, 'Parity, circuits, and the polynomial time heirarchy', Proc, 22nd IEEE FOCS, 1981, 260-270.Google Scholar
- GS??.M. Ger~l>-Graus and E. Szemer~di, 'There are no p-complete families of symmetric Boolean functions', preprint.Google Scholar
- Ha86.J. Hastad, 'Improved lower bounds for small depth circuits', these proceedings.Google Scholar
- LF77.R. E. Ladner and M. J. Fischer, 'Parallel prefix computation', Proc. 1977 Intl. Conf. on Parallel Processing, 218-233.Google Scholar
- Le59.C. Y. Lee, 'Representation of switching functions by binary decision programs', Bell System Technical Journal 38 (1959) 985-999.Google ScholarCross Ref
- Ma76.W. Masek, 'A fast algorithm for the string editing problem and decision graph complexity', M. Sc. Thesis, MIT, May 1976.Google Scholar
- Pu84.P. Pddlak, 'A lower bound on complexity of branching programs', Proc. Conference on the Mathematical Foundations of Computer Science, 1984, 480-489. Google ScholarDigital Library
- Ru81.W. L. Ruzzo, 'On uniform circuit complexity', JCS~ 22, 3 (June 1981), 365-383.Google ScholarCross Ref
- Sa72.J. Savage, 'Computation work and time on finit, machines', J. ACM 19 (1972), 660-674. Google ScholarDigital Library
- Sh85.J. B. Shearer, personal communication, 1985.Google Scholar
- SV81.S. Skyum and L. G. Valiant, 'A complexity theor~ based on Boolean algebra', Proc. 22nd IEEE FOCS, 1981, 244~ 253.Google Scholar
- Ya83.A. C. Yao, 'Lower bounds by probabilistic argu merits', Proc. 24th IEEE FOCS, 1983, 420-428.Google ScholarDigital Library
- Ya85.A. C. Yao, cSeparating the polynomial-time heirar chy by oracles', 26th ACM STOC, 1985, 1-10. Google ScholarDigital Library
- Za58.H. J. Zassenhaus, Th~ Theory off Groups, 2nd ed (New York, Chelsea Publ. Co., 1958).Google Scholar
Index Terms
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
Recommendations
The power of nondeterminism in polynomial- size bounded-width branching programs
Nondeterministic branching programs introduced by Meinel (1986) proved to be an interesting computational tool for describing higher complexity classes (Meinel 1988). Investigation of the power of nondeterminism in the case of bounded-width ...
Counting paths in planar width 2 branching programs
CATS '12: Proceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 128We revisit the problem of counting paths in width-2 planar branching programs. We show that this is hard for Boolean NC1 under ACC0[5] reductions, completing a proof strategy outlined in [3]. On the other hand, for several restricted instances of width-...
Comments