ACM DL

Computation Theory (TOCT)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computation Theory (TOCT), Volume 10 Issue 1, January 2018

Affine Relativization: Unifying the Algebrization and Relativization Barriers
Bariş Aydinlioğlu, Eric Bach
Article No.: 1
DOI: 10.1145/3170704

We strengthen existing evidence for the so-called “algebrization barrier.” Algebrization—short for algebraic relativization—was introduced by Aaronson and Wigderson (AW) (STOC 2008) to characterize proofs involving...

Communication Complexity of Statistical Distance
Thomas Watson
Article No.: 2
DOI: 10.1145/3170708

We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over n elements, and they wish to estimate within ±ε...

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
Article No.: 3
DOI: 10.1145/3170709

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ABP). In this work, we give an exponential lower bound of exp...

Randomized Communication versus Partition Number
Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson
Article No.: 4
DOI: 10.1145/3170711

We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique versus Independent Set...