ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

In this article, we study the identity testing problem of arithmetic read-once formulas (ROFs) and some related models. An ROF is a formula (a circuit... (more)

Invariance Principle on the Slice

The non-linear invariance principle of Mossel, O’Donnell, and Oleszkiewicz establishes that if f(x1,&ldots; ,xn) is a multilinear low-degree polynomial with low influences, then the distribution of if f(b1,&ldots;,bn) is close (in various senses) to the distribution of f(G1,&ldots;,Gn), where Bi ∈R {-1,1} are independent... (more)

The Limits of SDP Relaxations for General-Valued CSPs

It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can... (more)

Directed Multicut is W[1]-hard, Even for Four Terminal Pairs

We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable... (more)

The Coin Problem for Product Tests

Let Xm,ϵ be the distribution over m bits X1,…,Xm where the Xi are independent and each Xi equals 1 with probability (1−ϵ)/2 and 0 with probability (1 − ϵ)/2. We consider the smallest value ϵ* of ϵ such that the distributions Xm, ϵ and Xm, 0 can be distinguished... (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

Property Testing of Joint Distributions using Conditional Samples Article

Circuits and Expressions over Finite Semirings

Bibliometrics

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

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

Search TOCT
enter search term and/or author name