Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 9 Issue 1, December 2016

On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
P. Hrubeš
Article No.: 1
DOI: 10.1145/2940323

For a Boolean function f: {0, 1}n → {0, 1}, let &fcirc; be the unique multilinear polynomial such that f(x) = &fcirc;(x) holds for every x...

Small Depth Proof Systems
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
Article No.: 2
DOI: 10.1145/2956229

A proof system for a language L is a function f such that Range(f) is exactly L. In this article, we look at proof systems from a circuit complexity point of view and study proof systems that are computationally very...

Noncommutative Valiant's Classes: Structure and Complete Problems
V. Arvind, P. S. Joglekar, S. Raja
Article No.: 3
DOI: 10.1145/2956230

In this article, we explore the noncommutative analogues, VPnc and VNPnc, of Valiant’s algebraic complexity classes and show some striking connections to classical formal language theory. Our main results are the...

Relative Discrepancy Does Not Separate Information and Communication Complexity
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland
Article No.: 4
DOI: 10.1145/2967605

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Ganor et al. [2014] recently provided such a separation...

Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
Article No.: 5
DOI: 10.1145/3013516

A formulation of Nečiporuk’s lower bound method slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method...