ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits

A sampling procedure for a distribution P over {0, 1}ℓ is a function C: {0, 1}n → {0, 1}ℓ such that... (more)

Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the... (more)

Exact Perfect Matching in Complete Graphs

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect matching problem is logspace equivalent to the perfect matching... (more)

A Complexity Trichotomy for Approximately Counting List H-Colorings

We examine the computational complexity of approximately counting the list H-colorings of a graph. We discover a natural graph-theoretic trichotomy... (more)

Min/Max-Poly Weighting Schemes and the NL versus UL Problem

For a graph G(V, E) (|V| = n) and a vertex s ∈ V, a weighting scheme (W : E ↦ Z+) is called a min-unique (resp.... (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-2017
Publication Count 113
Citation Count 172
Available for Download 113
Downloads (6 weeks) 331
Downloads (12 Months) 2891
Downloads (cumulative) 19024
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 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
Toniann Pitassi 4
Stephen Cook 4
Meena Mahajan 4
Dana Ron 4
Leslie Goldberg 4
Alexander Razborov 3
Karteek Sreenivasaiah 3
Stefan Kratsch 3
John Hitchcock 3
Ryan O’Donnell 3
Marcin Pilipczuk 3
Emanuele Viola 3
Paul Beame 3
Thomas Watson 3
Michał Pilipczuk 3
Nutan Limaye 3
A Pavan 2
Oded Lachish 2
Per Austrin 2
Lila Fontes 2
Michael Fellows 2
Jayalal Sarma 2
Jérémie Roland 2
N Vinodchandran 2
Andreas Krebs 2
Yuval Filmus 2
Oded Regev 2
Johan Håstad 2
Yuan Zhou 2
Rahul Santhanam 2
Arpita Korwar 2
Anindya De 2
David Richerby 2
Pierre McKenzie 2
Andreas Göbel 2
Rohit Gurjar 2
Gilad Tsur 2
Anna Gál 2
Oded Goldreich 2
Moritz Müller 2
Olaf Beyersdorff 2
Jacobo Torán 2
Samir Datta 2
Massimo Lauria 2
Mark Jerrum 2
Michael Fellows 2
Marek Cygan 2
Arkadev Chattopadhyay 2
Raghav Kulkarni 2
Fedor Fomin 2
Jochen Messner 2
Thomas Thierauf 2
Balagopal Komarath 1
Markus Bläser 1
Vikraman Arvind 1
Hannes Moser 1
Rolf Niedermeier 1
Raghunath Tewari 1
Muthuramakrishnan Venkitasubramaniam 1
Christian Glaßer 1
Jacob Sponemann 1
Berthold Vöcking 1
Ryan Williams 1
Magnus Wahlström 1
Mark Jerrum 1
Shafi Goldwasser 1
Marcus Isaksson 1
Māris Ozols 1
Martin Roetteler 1
S Raja 1
Yonatan Goldhirsh 1
Jack Lutz 1
Sylvain Schmitz 1
Michael Viderman 1
Andrew Drucker 1
Jakub Wojtaszczyk 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
Peter Fulla 1
Dung Nguyen 1
Pavel Hrubeš 1
Mathieu Laurière 1
Sergei Artemenko 1
Madhav Jha 1
Sofya Raskhodnikova 1
Grant Schoenebeck 1
Paolo Penna 1
Pål Drange 1
Ioannis Caragiannis 1
Scott Aaronson 1
Avi Wigderson 1
Chandan Saha 1
Trinh Huynh 1
Nathan Segerlind 1
Matthias Englert 1
Zvika Brakerski 1
Omid Etesami 1
Eric Allender 1
Ola Svensson 1
Gaurav Maheshwari 1
Vikraman Arvind 1
Pushkar Joglekar 1
Adam Case 1
Thomas Steinke 1
Pranjal Awasthi 1
Ashutosh Rai 1
William Gasarch 1
Michael Thomas 1
Jason Teutsch 1
Or Meir 1
Maria Kyropoulou 1
Frances Rosamond 1
Hadas Shachnai 1
Ronitt Rubinfeld 1
Alex Samorodnitsky 1
Nikos Vlassis 1
Ning Zhong 1
Yijia Chen 1
James Cook 1
Hirotada Kobayashi 1
Enrico Malizia 1
Luc Segoufin 1
Ronen Shaltiel 1
Eldar Fischer 1
Varun Kanade 1
Marco Molinaro 1
Ishay Haviv 1
Daniel Lokshtanov 1
Aravind Srinivasan 1
Salil Vadhan 1
Carmine Ventre 1
Marius Zimand 1
Yi Wu 1
Christos Kaklamanis 1
Simon Straub 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
Luigi Palopoli 1
Heiko Röglin 1
Hidetoki Tanaka 1
Craig Gentry 1
Vinod Vaikuntanathan 1
Rachel Miller 1
Luca Trevisan 1
Keiji Matsumoto 1
Mahdi Cheraghchi 1
Rasmus Pagh 1
Stanislav Živný 1
Alan Selman 1
Elena Losievskaja 1
Andris Ambainis 1
Yngve Villanger 1
Alejandro López-Ortíz 1
Rafael Pass 1
Muli Safra 1
Michael Littman 1
Tomáš Vyskočil 1
Anil Ada 1
Yi Wu 1
Mihalis Yannakakis 1
Ilya Volkovich 1
Francesco Scarcello 1
Rahul Jain 1
Iordanis Kerenidis 1
Sophie Laplante 1
Víctor Dalmau 1
Yitong Yin 1
Nir Ailon 1
Dániel Marx 1
Elchanan Mossel 1
Frances Rosamond 1
Venkatesh Raman 1
Andrey Utis 1
Heribert Vollmer 1
Akitoshi Kawamura 1
Hubie Chen 1
Clifford Smyth 1
David Barber 1
Jan Kynčl 1
Matei David 1
Prahladh Harsha 1
Michal Koucký 1
Andrej Bogdanov 1
Kousha Etessami 1
Alistair Stewart 1
Paul Valiant 1
Seiichiro Tani 1
Gianluigi Greco 1
Nathan Grosshans 1
Ryan Harkins 1
Fabian Wagner 1
Saket Saurabh 1
Arnab Bhattacharyya 1
Andreas Galanis 1
Gido Scharfenberger-Fabian 1
Bodo Manthey 1
Thomas Vidick 1
Henning Fernau 1
Eric Purdy 1
Alexander Souza 1
Dustin Wehr 1
Liyang Tan 1
Shuming Sun 1
Jörg Flum 1
Nicola Galesi 1
Bart Jansen 1
Daitri 1
Mrinal Kumar 1
Andrei Krokhin 1
Sivakanth Gopi 1
Magnus Wahlström 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
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
Indian Institute of Science 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
University of Haifa 2
Saarland University 2
University of Wyoming 3
Aalen University of Applied Sciences 3
Royal Institute of Technology 3
Harvard University 3
Massachusetts Institute of Technology 3
University of Texas at Austin 3
Gottfried Wilhelm Leibniz Universitat 3
Northeastern University 3
University of Maryland 3
RWTH Aachen University 3
University of Ulm 4
Indian Institute of Technology, Madras 4
University of Calabria 4
Charles Darwin University 4
Queen Mary, University of London 4
University of Waterloo 4
Iowa State University 4
Princeton University 4
University of Nebraska - Lincoln 4
University of Edinburgh 4
Weizmann Institute of Science Israel 5
University of Chicago 5
Max Planck Institute for Informatics 5
Universite Paris 7- Denis Diderot 5
University of Washington, Seattle 6
Technion - Israel Institute of Technology 6
University of Warsaw 6
Institute of Mathematical Sciences India 7
Tel Aviv University 8
University of California, Berkeley 8
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