ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles
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
The weakness of CTC qubits and the power of approximate counting

We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of problems that
can be efficiently solved with a nonadaptive oracle for the Approximate Counting problem. Our
second result is concerned with the computational power conferred by CTCs; or equivalently,
the computational complexity of finding stationary distributions for quantum channels. We
show that any poly(n)-time quantum computation using a CTC of O(log n) qubits may as well
just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find
a stationary distribution for a poly(n)-dimensional quantum channel in PP.

Hardness of approximation for H-free edge modification problems

Directed multicut is W[1]-hard, even for four terminal pairs

We prove that \textsc{Multicut} in directed graphs, parameterized by the size of the cutset, is $W[1]$-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs.
This negative result almost completely resolves
one of the central open problems in the area of parameterized complexity of graph separation problems,
posted originally by Marx and Razgon [SIAM J. Comput. 43(2):355--388 (2014)], leaving only the case of three terminal pairs open. The case of two terminal pairs was shown to be FPT by Chitnis et al.~[SIAM J. Comput. 42(4):1674--1696 (2013)].

Our gadget methodology also allows us to prove $W[1]$-hardness of the \textsc{Steiner Orientation} problem
parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [SIAM J. Discrete Math. 27(3):1503-1513 (2013)].

Introduction to Special Issue on SPAA '15

The limits of SDP relaxations for general-valued CSPs

Algorithmic information, plane Kakeya sets, and conditional dimension

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

The coin problem for product tests


Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$
where the $X_i$ are independent and each $X_i$ equals $1$ with
probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We
consider the smallest value $\eps^*$ of $\eps$ such that the distributions
$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant
advantage by a function $f : \{0,1\}^m \to S$ which is the product of $k$
functions $f_1, f_2, \ldots, f_k$ on disjoint inputs of $n$ bits, where each
$f_i : \{0,1\}^n \to S$ and $m = nk$.

We prove that $\eps^* = \Theta(1/\sqrt{n \log k})$ if $S = \{0,1\}$ and if $S
= \{-1,1\}$, while $\eps^* = \Theta(1/\sqrt{nk})$ if $S$ is the set of
unit-norm complex numbers.

Bibliometrics

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

Search TOCT
enter search term and/or author name