ACM Transactions on

Computation Theory (TOCT)

Latest Articles

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

Randomized Communication versus Partition Number


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
Invariance principle on the slice

The non-linear invariance principle of Mossel, O'Donnell and Oleszkiewicz establishes that if f(x_1,\...,x_n) is a multilinear low-degree polynomial with low influences then the distribution of f(B_1,...,B_n) is close (in various senses) to the distribution of f(G_1,...,G_n), where B_i in are independent +1/-1 Bernoulli random variables and G_i ~ N(0,1) are independent standard Gaussians. The invariance principle has seen many application in theoretical computer science, including the Majority is Stablest conjecture, which shows that the Goemans-Williamson algorithm for MAX-CUT is optimal under the Unique Games Conjecture.

More generally, MOO's invariance principle works for any two vectors of hypercontractive random variables (X_1,...,X_n),(Y_1,...,Y_n) such that (i) Matching moments: X_i and Y_i have matching first and second moments, (ii) Independence: the variables X_1,...,X_n are independent, as are Y_1,...,Y_n.

The independence condition is crucial to the proof of the theorem, yet in some cases we would like to use distributions X_1,...,X_n in which the individual coordinates are not independent. A common example is the uniform distribution on the slice C([n],k) which consists of all vectors (x_1,...,x_n) in {0,1}^n with Hamming weight k. The slice shows up in theoretical computer science (hardness amplification, direct sum testing), extremal combinatorics (Erdos-Ko-Rado theorems) and coding theory (in the guise of the Johnson association scheme).

Our main result is an invariance principle in which (X_1,...,X_n) is the uniform distribution on a slice C([n],pn) and (Y_1,...,Y_n) consists either of n independent Ber(p) random variables, or of n independent N(p,p(1-p)) Gaussian random variables. As applications, we prove a version of Majority is Stablest for functions on the slice, a version of Bourgain's tail theorem, a version of the Kindler-Safra structural theorem, and a stability version of the t-intersecting Erdos-Ko-Rado theorem, combining techniques of Wilson and Friedgut.

Our proof relies on a combination of ideas from analysis and probability, algebra and combinatorics. In particular, we make essential use of recent work of the first author which describes an explicit Fourier basis for the slice.

Ground state connectivity of local Hamiltonians

The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this paper, we take a new direction by introducing the physically motivated notion of "ground state connectivity" of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. Roughly, "ground state connectivity" corresponds to the natural question: Given two ground states of a local Hamiltonian H, is there an "energy barrier" (with respect to H) along any sequence of local
operations mapping the first ground state to the second? We show that the complexity of this question can range from QCMA-complete to PSPACE-complete, as well as NEXP complete for an appropriately defined "succinct" version of the problem. As a result, we obtain a natural QCMA complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.

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

Introduction to Special Issue on SPAA '15

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

Tight Running Time Lower Bounds for Vertex Deletion Problems


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