ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

On Hardness of Multilinearization and VNP-Completeness in Characteristic 2

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

Small Depth Proof Systems

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 restricted. The restriction we study is proof systems that can be computed by bounded fanin circuits of constant depth (NC0) or of... (more)

Noncommutative Valiant's Classes

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 following: — We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for the... (more)

Relative Discrepancy Does Not Separate Information and Communication Complexity

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to... (more)

Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method

A formulation of Nečiporuk’s lower bound method slightly more inclusive than the usual complexity-measure-specific formulation is... (more)

NEWS

 

New ACM ToCT Editor-in-Chief

Venkatesan Guruswami is the new Editor-in-Chief for ACM ToCT, as of February 1, 2017

 

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

Bibliometrics

Publication Years 2009-2016
Publication Count 108
Citation Count 147
Available for Download 108
Downloads (6 weeks) 260
Downloads (12 Months) 2919
Downloads (cumulative) 18326
Average downloads per article 170
Average citations per article 1
First Name Last Name Award
Mahdi Cheraghchi ACM Senior Member (2016)
Stephen A Cook ACM A. M. Turing Award (1982)
Craig Gentry ACM Grace Murray Hopper Award (2010)
ACM Doctoral Dissertation Award (2009)
Rohit Gurjar ACM India Doctoral Dissertation Award (2017)
Venkatesan Guruswami ACM Doctoral Dissertation Award (2002)
Johan Torkel Hastad ACM Doctoral Dissertation Award (1986)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)

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

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 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
Aalen University of Applied Sciences 1
Cornell University 1
Hebrew University of Jerusalem 1
Birkbeck University of London 1
IBM Research 1
Center for Mathematics and Computer Science - Amsterdam 1
Technical University of Berlin 1
University of Trier 1
University of Leeds 1
Stanford University 1
The University of North Carolina at Greensboro 1
IT University of Copenhagen 1
University of Twente 1
Microsoft Research 1
New York University 1
University College London 1
University of Durham 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 the Basque Country 1
Swiss Federal Institute of Technology, Lausanne 1
Friedrich Schiller University Jena 1
University of California, San Diego 1
Academy of Sciences of the Czech Republic (Avcr.Cz) 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
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
Ben-Gurion University of the Negev 2
University of Vienna 2
The University of Warwick 2
Indian Institute of Technology, Kanpur 2
Chennai Mathematical Institute 2
NEC Laboratories America, Inc. 2
University of Tubingen 2
Charles University in Prague 2
Indian Institute of Technology, Bombay 2
University of Wurzburg 2
Brown University 2
University of Montreal 2
Utrecht University 2
Google Inc. 2
Saarland University 2
University of Wyoming 3
Harvard University 3
RWTH Aachen University 3
Queen Mary, University of London 3
Massachusetts Institute of Technology 3
University of Texas at Austin 3
Gottfried Wilhelm Leibniz Universitat 3
Northeastern University 3
University of Maryland 3
Royal Institute of Technology 3
Princeton University 3
Iowa State University 4
University of Waterloo 4
Universite Paris 7- Denis Diderot 4
University of Ulm 4
Charles Darwin University 4
Indian Institute of Technology, Madras 4
University of Edinburgh 4
University of Nebraska - Lincoln 4
University of Calabria 4
University of Chicago 5
Weizmann Institute of Science Israel 5
Max Planck Institute for Informatics 5
University of Washington, Seattle 6
University of Warsaw 6
Technion - Israel Institute of Technology 6
Tel Aviv University 7
Institute of Mathematical Sciences India 7
University of California, Berkeley 8
University of Bergen 10
University of Oxford 10
Carnegie Mellon University 11
University of Toronto 19
 
All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name