ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

Parameterized Testability

Parameterized Property Testing of Functions

An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Given a graph G and two vertices s and t in it, graph reachability is the problem of checking... (more)

NEWS

About TOCT

The ACM Transactions on Computation Theory (TOCT) is a peer-reviewed journal that explores the mathematical nature of computation and it's theoretical limitations (with an emphasis on computational complexity, foundations of cryptography and other computation-based topics in theoretical computer science).

read more
Forthcoming Articles

Communication Complexity of Statistical Distance

Randomized Communication vs. Partition Number

Affine Relativization: Unifying the Algebrization and Relativization Barriers

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) (STOC 2008) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure properties, making it conceivable to take two proofs, both with algebrizing conclusions, and combine them to get a proof without. Further, the notion is undefined for most types of statements, and does not seem to yield a general criterion by which we can tell, given a proof, whether it algebrizes. In fact the very notion of an algebrizing proof is never made explicit, and casual attempts to define it are problematic. All these issues raise the question of what evidence, if any, is obtained by knowing whether some statement does or does not algebrize.

We reformulate algebrization to handle these shortcomings. We first define a statement as *relativizing* if, intuitively, it is insensitive to the choice of a Boolean basis, and then as *relativizing affinely* if, roughly, it relativizes with respect to every affine extension --- here an affine extension is the result of a particular error correcting code applied to the characteristic string of a language. We also define the notion of a *proof* to relativize (affinely), while ensuring closure under inference. We show that all statements that AW declare as algebrizing can be derived via an affinely relativizing proof, and that no such proof exists for any of the statements shown not-algebrizing by AW in the classical computation model.

Our work complements, and goes beyond, the subsequent work by Impagliazzo, Kabanets, and Kolokolova (STOC 2009), which also proposes a reformulation of algebrization, but falls short of recovering some key results of AW, most notably regarding the NEXP versus P/poly question.

One consequence of our definitions is a demystified perspective on the extent to which relativizing techniques view computation as a "black box" and current uses of arithmetization do not. As another consequence, we give new streamlined proofs of several classic results in complexity, including PSPACE $\subset$ IP and NEXP $\subset$ MIP.

Bibliometrics

Publication Years 2009-2018
Publication Count 124
Citation Count 222
Available for Download 124
Downloads (6 weeks) 336
Downloads (12 Months) 2803
Downloads (cumulative) 20786
Average downloads per article 168
Average citations per article 2
First Name Last Name Award
Mahdi Cheraghchi ACM Senior Member (2016)
Stephen A Cook ACM Fellows (2008)
ACM A. M. Turing Award (1982)
Lance Fortnow ACM Fellows (2007)
Craig Gentry ACM Grace Murray Hopper Award (2010)
ACM Doctoral Dissertation Award (2009)
Rohit Gurjar ACM India Doctoral Dissertation Award (2017)
Venkatesan Guruswami ACM Fellows (2017)
Venkatesan Guruswami ACM Doctoral Dissertation Award (2002)
Ronitt Rubinfeld ACM Fellows (2014)
Ramprasad Saptharishi ACM India Doctoral Dissertation Award (2013)
Alan Selman ACM Fellows (1998)
Aravind Srinivasan ACM Fellows (2014)
Johan Torkel Hastad ACM Doctoral Dissertation Award (1986)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)
Mihalis Yannakakis ACM Fellows (1998)

First Name Last Name Paper Counts
Marcin Pilipczuk 4
Stephen Cook 4
Dana Ron 4
Leslie Goldberg 4
Toniann Pitassi 4
Meena Mahajan 4
Michał Pilipczuk 4
Thomas Watson 3
Paul Beame 3
Stefan Kratsch 3
Alexander Razborov 3
Nutan Limaye 3
Karteek Sreenivasaiah 3
Emanuele Viola 3
John Hitchcock 3
Ryan O’Donnell 3
Jayalal Sarma 3
Andreas Krebs 2
Jérémie Roland 2
Mark Jerrum 2
Massimo Lauria 2
Arkadev Chattopadhyay 2
Marek Cygan 2
Jochen Messner 2
Raghav Kulkarni 2
Jacobo Torán 2
Yuan Zhou 2
Rahul Santhanam 2
David Richerby 2
Anindya De 2
Sofya Raskhodnikova 2
Pierre McKenzie 2
Fedor Fomin 2
Andreas Göbel 2
Raghunath Tewari 2
Thomas Thierauf 2
Arpita Korwar 2
Samir Datta 2
Michael Fellows 2
Oded Regev 2
Hubie Chen 2
Yuval Filmus 2
N Vinodchandran 2
Olaf Beyersdorff 2
Lila Fontes 2
Per Austrin 2
Rohit Gurjar 2
A Pavan 2
Oded Lachish 2
Gilad Tsur 2
Anna Gál 2
Oded Goldreich 2
Moritz Müller 2
Johan Håstad 2
Michael Fellows 2
Prahladh Harsha 1
Gido Scharfenberger-Fabian 1
Michal Koucký 1
Andrej Bogdanov 1
Paul Valiant 1
Kousha Etessami 1
Alistair Stewart 1
Gianluigi Greco 1
Seiichiro Tani 1
Nathan Grosshans 1
Ryan Harkins 1
Fabian Wagner 1
Saket Saurabh 1
Andreas Galanis 1
Arnab Bhattacharyya 1
Anant Dhayal 1
Bodo Manthey 1
Thomas Vidick 1
Henning Fernau 1
Eric Purdy 1
Dustin Wehr 1
Liyang Tan 1
Alexander Souza 1
Jörg Flum 1
Shuming Sun 1
Nicola Galesi 1
Magnus Wahlström 1
Bart Jansen 1
Daitri 1
Mrinal Kumar 1
Andrei Krokhin 1
Sivakanth Gopi 1
Ramprasad Saptharishi 1
Amir Shpilka 1
Balagopal Komarath 1
Markus Bläser 1
Yonatan Goldhirsh 1
Vikraman Arvind 1
Muthuramakrishnan Venkitasubramaniam 1
Hannes Moser 1
Rolf Niedermeier 1
Michael Elberfeld 1
Jack Lutz 1
Christian Glaßer 1
Jacob Sponemann 1
Berthold Vöcking 1
Magnus Wahlström 1
Jakub Wojtaszczyk 1
Ryan Williams 1
Mark Jerrum 1
Shafi Goldwasser 1
Sylvain Schmitz 1
Marcus Isaksson 1
Māris Ozols 1
Martin Roetteler 1
Michael Viderman 1
Andrew Drucker 1
S Raja 1
Matthew Anderson 1
Ben Volk 1
Jingtang Jang 1
Neeraj Kayal 1
Omri Weinstein 1
Venkatesan Guruswami 1
Jazmin Romero 1
Jiong Guo 1
Mark Braverman 1
Eli Ben-Sasson 1
Arie Matsliah 1
Benoît Larose 1
Lance Fortnow 1
Akinori Kawachi 1
Chinglueh Chang 1
Nithin Varma 1
Paolo Penna 1
Grant Schoenebeck 1
Madhav Jha 1
Peter Fulla 1
Dung Nguyen 1
Pavel Hrubeš 1
Mathieu Laurière 1
Sergei Artemenko 1
Pål Drange 1
Chandan Saha 1
Nathan Segerlind 1
Ioannis Caragiannis 1
Pascal Schweitzer 1
Trinh Huynh 1
William Gasarch 1
Adam Case 1
Michael Thomas 1
Scott Aaronson 1
Avi Wigderson 1
Matthias Englert 1
Omid Etesami 1
Ramesh Pallavoor 1
Thomas Steinke 1
Zvika Brakerski 1
Eric Allender 1
Kazuo Iwama 1
Diptarka Chakraborty 1
Ashutosh Rai 1
Ola Svensson 1
Pranjal Awasthi 1
Luigi Palopoli 1
Gaurav Maheshwari 1
Vikraman Arvind 1
Pushkar Joglekar 1
Jason Teutsch 1
Or Meir 1
Maria Kyropoulou 1
Eldar Fischer 1
Markus Schmid 1
Ronitt Rubinfeld 1
Alex Samorodnitsky 1
Frances Rosamond 1
Hadas Shachnai 1
Anna Adamaszek 1
Nikos Vlassis 1
Aravind Srinivasan 1
James Cook 1
Yijia Chen 1
Varun Kanade 1
Ning Zhong 1
Carmine Ventre 1
Hirotada Kobayashi 1
Salil Vadhan 1
Marco Molinaro 1
Enrico Malizia 1
Ishay Haviv 1
Luc Segoufin 1
Daniel Lokshtanov 1
Ronen Shaltiel 1
Yi Wu 1
Christos Kaklamanis 1
Kitty Meeks 1
Russell Impagliazzo 1
Prasad Raghavendra 1
John Wright 1
Simon Straub 1
Danny Hermelin 1
Tomasz Kociumaka 1
Andrew Mills 1
Andris Ambainis 1
Martin Hoefer 1
Stephen Travers 1
Heiko Röglin 1
Rachel Miller 1
Luca Trevisan 1
Chris Bourke 1
Hidetoki Tanaka 1
Craig Gentry 1
Vinod Vaikuntanathan 1
Yuichi Yoshida 1
Rasmus Pagh 1
Keiji Matsumoto 1
Mahdi Cheraghchi 1
Stanislav Živný 1
Alan Selman 1
Elena Losievskaja 1
Michael Forbes 1
Yngve Villanger 1
Marius Zimand 1
Hubie Chen 1
Rafael Pass 1
Muli Safra 1
Michael Littman 1
Alejandro López-Ortíz 1
Tomáš Vyskočil 1
Andrey Utis 1
Heribert Vollmer 1
Yitong Yin 1
Anil Ada 1
Yi Wu 1
Mihalis Yannakakis 1
Venkatesh Raman 1
Nir Ailon 1
Ilya Volkovich 1
Dániel Marx 1
Akitoshi Kawamura 1
Francesco Scarcello 1
Iordanis Kerenidis 1
Rahul Jain 1
Sophie Laplante 1
Frances Rosamond 1
Víctor Dalmau 1
Elchanan Mossel 1
Saurabh Sawlani 1
David Barber 1
CLIFFORD Smyth 1
Jan Kynčl 1
Matei David 1

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 1
University of Illinois at Urbana-Champaign 1
Humboldt University of Berlin 1
Chalmers University of Technology 1
McGill University 1
Chinese University of Hong Kong 1
Towson University 1
Ecole Normale Superieure de Cachan 1
MIT Computer Science and Artificial Intelligence Laboratory 1
University of Salerno 1
Northwestern University 1
University of Bonn 1
Universitat Politecnica de Catalunya 1
Cornell University 1
Hebrew University of Jerusalem 1
Birkbeck University of London 1
Kyoto University 1
IBM Research 1
Center for Mathematics and Computer Science - Amsterdam 1
Technical University of Berlin 1
University of Leeds 1
Stanford University 1
Yuan Ze University 1
Indian Institute of Science, Bangalore 1
The University of North Carolina at Greensboro 1
IT University of Copenhagen 1
University of Twente 1
Union College, Schenectady 1
Microsoft Research 1
New York University 1
University College London 1
University of Durham 1
Massachusetts Institute of Technology 1
Shanghai Jiaotong University 1
University of Cincinnati 1
University of Tokyo 1
Nippon Telegraph and Telephone Corporation 1
University of Freiburg 1
Virginia Tech 1
University of Rochester 1
Hungarian Academy of Sciences 1
University of Quebec in Montreal 1
Swiss Federal Institute of Technology, Lausanne 1
Research Organization of Information and Systems National Institute of Informatics 1
Friedrich Schiller University Jena 1
University of California, San Diego 1
University of Copenhagen 1
Academy of Sciences of the Czech Republic (Avcr.Cz) 1
Tata Institute of Fundamental Research 1
University at Buffalo, State University of New York 1
Universitat Pompeu Fabra 1
Intel Corporation 1
Nanjing University 1
University of Iceland 1
University of Luxembourg 1
Academic College of Tel-Aviv - Yaffo 1
Centre for Quantum Technologies, Singapore 1
Vishwakarma Institute of Technology 1
Ikerbasque, the Basque Foundation for Science 1
Specifications and Verification Laboratory 1
Universite Paris Saclay 1
Laboratoire de Recherche en Informatique 1
Pennsylvania State University 2
University of Roma La Sapienza 2
University of Patras 2
Tokyo Institute of Technology 2
Rutgers, The State University of New Jersey 2
Columbia University 2
University of the Basque Country 2
Ben-Gurion University of the Negev 2
University of Vienna 2
The University of Warwick 2
Chennai Mathematical Institute 2
NEC Laboratories America, Inc. 2
University of Tubingen 2
Indian Institute of Technology, Bombay 2
University of Wurzburg 2
University of Trier 2
Brown University 2
University of Montreal 2
Utrecht University 2
Google Inc. 2
University of Haifa 2
Saarland University 2
University of Maryland 3
Royal Institute of Technology 3
Gottfried Wilhelm Leibniz Universitat 3
Charles University 3
Aalen University of Applied Sciences 3
Boston University 3
Northeastern University 3
Harvard University 3
University of Texas at Austin 3
Indian Institute of Technology, Kanpur 3
University of Wyoming 3
University of Calabria 4
University of Edinburgh 4
University of Waterloo 4
Queen Mary, University of London 4
Princeton University 4
Iowa State University 4
Charles Darwin University 4
University of Ulm 4
University of Nebraska - Lincoln 4
Weizmann Institute of Science Israel 5
RWTH Aachen University 5
Max Planck Institute for Informatics 5
Universite Paris 7- Denis Diderot 5
University of Chicago 5
Technion - Israel Institute of Technology 6
University of Washington, Seattle 6
Institute of Mathematical Sciences India 7
Indian Institute of Technology, Madras 7
University of California, Berkeley 8
University of Warsaw 9
Tel Aviv University 10
University of Bergen 10
Carnegie Mellon University 11
University of Oxford 12
University of Toronto 19
 
All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name