ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

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

Randomized Communication versus Partition Number

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
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.

Tight Running Time Lower Bounds for Vertex Deletion Problems

Bibliometrics

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