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

Search TOCT
enter search term and/or author name