%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.23",
%%% date = "08 April 2017",
%%% time = "10:35:21 MST",
%%% filename = "toct.bib",
%%% address = "University of Utah
%%% Department of Mathematics, 110 LCB
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "40304 4705 26918 243038",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "bibliography, BibTeX, ACM Transactions on
%%% Computation Theory",
%%% license = "public domain",
%%% supported = "no",
%%% docstring = "This is a COMPLETE BibTeX bibliography for
%%% the journal ACM Transactions on Computation
%%% Theory (CODEN ????, ISSN 1942-3454),
%%% covering all journal issues from 2009 --
%%% date.
%%%
%%% The journal has a World-Wide Web site at:
%%%
%%% http://www.acm.org/pubs/toct
%%%
%%% Tables-of-contents are available at:
%%%
%%% http://www.acm.org/pubs/contents/journals/toct/
%%% http://portal.acm.org/browse_dl.cfm?idx=J1190
%%%
%%% Qualified subscribers can retrieve the full
%%% text of recent articles in PDF form.
%%%
%%% At version 1.23, the COMPLETE journal
%%% coverage looked like this:
%%%
%%% 2009 ( 7) 2012 ( 15) 2015 ( 13)
%%% 2010 ( 5) 2013 ( 18) 2016 ( 23)
%%% 2011 ( 6) 2014 ( 21)
%%%
%%% Article: 108
%%%
%%% Total entries: 108
%%%
%%% The initial draft was extracted from the
%%% ACM Web site, with manual corrections and
%%% additions from bibliographies in the TeX
%%% User Group collection, the author's
%%% personal bibliography files, the Compendex
%%% database, and a very large computer science
%%% bibliography collection on ftp.ira.uka.de
%%% in /pub/bibliography to which many people
%%% of have contributed. Where multiple
%%% sources of a particular entry existed,
%%% field values have been manually merged to
%%% preserve maximal information. Missing
%%% entries were identified by software
%%% developed for the TeX User Group and BibNet
%%% bibliography archive projects, and were
%%% then supplied from the original journal
%%% issues. Questions arising from conflicting
%%% data were resolved by consulting the
%%% original journal issues.
%%%
%%% ACM copyrights explicitly permit abstracting
%%% with credit, so article abstracts, keywords,
%%% and subject classifications have been
%%% included in this bibliography wherever
%%% available. Article reviews have been
%%% omitted, until their copyright status has
%%% been clarified.
%%%
%%% The bibsource keys in the bibliography
%%% entries below indicate the data sources,
%%% usually the Karlsruhe computer science
%%% bibliography archive for the first two
%%% volumes, or the journal Web site or the
%%% Compendex database, both of which lack
%%% coverage of this journal before 1985.
%%%
%%% URL keys in the bibliography point to
%%% World Wide Web locations of additional
%%% information about the entry.
%%%
%%% Spelling has been verified with the UNIX
%%% spell and GNU ispell programs using the
%%% exception dictionary stored in the
%%% companion file with extension .sok.
%%%
%%% BibTeX citation tags are uniformly chosen
%%% as name:year:abbrev, where name is the
%%% family name of the first author or editor,
%%% year is a 4-digit number, and abbrev is a
%%% 3-letter condensation of important title
%%% words. Citation tags were automatically
%%% generated by software developed for the
%%% BibNet Project.
%%%
%%% In this bibliography, entries are sorted in
%%% publication order, using ``bibsort -byvolume.''
%%%
%%% The checksum field above contains a CRC-16
%%% checksum as the first value, followed by the
%%% equivalent of the standard UNIX wc (word
%%% count) utility output of lines, words, and
%%% characters. This is produced by Robert
%%% Solovay's checksum utility.",
%%% }
%%% ====================================================================
@Preamble{"\input bibnames.sty"}
%%% ====================================================================
%%% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%%% ====================================================================
%%% Journal abbreviations:
@String{j-TOCT = "ACM Transactions on Computation Theory"}
%%% ====================================================================
%%% Publisher abbreviations:
@String{pub-ACM = "ACM Press"}
@String{pub-ACM:adr = "New York, NY 10036, USA"}
%%% ====================================================================
%%% Bibliography entries:
@Article{Fortnow:2009:EF,
author = "Lance Fortnow",
title = "{Editor}'s Foreword",
journal = j-TOCT,
volume = "1",
number = "1",
pages = "1:1--1:??",
month = feb,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1490270.1490271",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Fri Apr 24 19:03:42 MDT 2009",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Aaronson:2009:ANB,
author = "Scott Aaronson and Avi Wigderson",
title = "Algebrization: a New Barrier in Complexity Theory",
journal = j-TOCT,
volume = "1",
number = "1",
pages = "2:1--2:??",
month = feb,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1490270.1490272",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Fri Apr 24 19:03:42 MDT 2009",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Any proof of P $\neq$ NP will have to overcome two
barriers: {\em relativization\/} and {\em natural
proofs}. Yet over the last decade, we have seen circuit
lower bounds (e.g., that PP does not have linear-size
circuits) that overcome both barriers simultaneously.
So the question arises of whether there is a third
barrier to progress on the central questions in
complexity theory.\par
In this article, we present such a barrier, which we
call {\em algebraic relativization\/} or {\em
algebrization}. The idea is that, when we relativize
some complexity class inclusion, we should give the
simulating machine access not only to an oracle $A$,
but also to a low-degree extension of $A$ over a finite
field or ring.\par
We systematically go through basic results and open
problems in complexity theory to delineate the power of
the new algebrization barrier. First, we show that all
known nonrelativizing results based on
arithmetization---both inclusions such as IP = PSPACE
and MIP = NEXP, and separations such as MA$_{{EXP}_n}$
P/poly---do indeed algebrize. Second, we show that
almost all of the major open problems---including P
versus NP, P versus RP, and NEXP versus P/poly---will
require {\em non-algebrizing techniques}. In some
cases, algebrization seems to explain exactly why
progress stopped where it did: for example, why we have
superlinear circuit lower bounds for PromiseMA but not
for NP.\par
Our second set of results follows from lower bounds in
a new model of {\em algebraic query complexity}, which
we introduce in this article and which is interesting
in its own right. Some of our lower bounds use direct
combinatorial and algebraic arguments, while others
stem from a surprising connection between our model and
communication complexity. Using this connection, we are
also able to give an MA-protocol for the Inner Product
function with $O(\sqrt{n} \log n)$ communication
(essentially matching a lower bound of Klauck), as well
as a communication complexity conjecture whose truth
would imply NL $\neq$ NP.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
keywords = "arithmetization; communication complexity; interactive
proofs; Low-degree polynomials; oracles; query
complexity",
}
@Article{Razborov:2009:SPB,
author = "Alexander Razborov",
title = "A Simple Proof of {Bazzi's Theorem}",
journal = j-TOCT,
volume = "1",
number = "1",
pages = "3:1--3:??",
month = feb,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1490270.1490273",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Fri Apr 24 19:03:42 MDT 2009",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Linial and Nisan [1990] asked if any polylog-wise
independent distribution fools any function in AC$^0$.
In a recent remarkable development, Bazzi solved this
problem for the case of DNF formulas. The aim of this
note is to present a simplified version of his proof.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
keywords = "DNF; Pseudo-random generators",
}
@Article{Bourke:2009:DPR,
author = "Chris Bourke and Raghunath Tewari and N. V.
Vinodchandran",
title = "Directed Planar Reachability Is in Unambiguous
Log-Space",
journal = j-TOCT,
volume = "1",
number = "1",
pages = "4:1--4:??",
month = feb,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1490270.1490274",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Fri Apr 24 19:03:42 MDT 2009",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We make progress in understanding the complexity of
the graph reachability problem in the context of
unambiguous logarithmic space computation; a restricted
form of nondeterminism. As our main result, we show a
new upper bound on the {\em directed planar
reachability problem\/} by showing that it can be
decided in the class unambiguous logarithmic space
(UL). We explore the possibility of showing the same
upper bound for the general graph reachability problem.
We give a simple reduction showing that the
reachability problem for directed graphs with thickness
two is complete for the class nondeterministic
logarithmic space (NL). Hence an extension of our
results to directed graphs with thickness two will
unconditionally collapse NL to UL.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
keywords = "Directed graph reachability; planar graphs;
unambiguous log-space",
}
@Article{David:2009:ISB,
author = "Matei David and Toniann Pitassi and Emanuele Viola",
title = "Improved Separations between Nondeterministic and
Randomized Multiparty Communication",
journal = j-TOCT,
volume = "1",
number = "2",
pages = "5:1--5:??",
month = sep,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1595391.1595392",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Mar 16 10:08:03 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Guruswami:2009:HSS,
author = "Venkatesan Guruswami and Prasad Raghavendra",
title = "Hardness of Solving Sparse Overdetermined Linear
Systems: a 3-Query {PCP} over Integers",
journal = j-TOCT,
volume = "1",
number = "2",
pages = "6:1--6:??",
month = sep,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1595391.1595393",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Mar 16 10:08:03 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ben-Sasson:2009:SQP,
author = "Eli Ben-Sasson and Prahladh Harsha and Oded Lachish
and Arie Matsliah",
title = "Sound 3-Query {PCPPs} Are Long",
journal = j-TOCT,
volume = "1",
number = "2",
pages = "7:1--7:??",
month = sep,
year = "2009",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1595391.1595394",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Mar 16 10:08:03 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kyncl:2010:LRD,
author = "Jan Kyn{\v{c}}l and Tom{\'a}{\v{s}} Vysko{\v{c}}il",
title = "Logspace Reduction of Directed Reachability for
Bounded Genus Graphs to the Planar Case",
journal = j-TOCT,
volume = "1",
number = "3",
pages = "8:1--8:??",
month = mar,
year = "2010",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1714450.1714451",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Mar 16 10:08:04 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Beame:2010:FCD,
author = "Paul Beame and Russell Impagliazzo and Toniann Pitassi
and Nathan Segerlind",
title = "Formula Caching in {DPLL}",
journal = j-TOCT,
volume = "1",
number = "3",
pages = "9:1--9:??",
month = mar,
year = "2010",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1714450.1714452",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Mar 16 10:08:04 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Datta:2010:PDP,
author = "Samir Datta and Raghav Kulkarni and Nutan Limaye and
Meena Mahajan",
title = "Planarity, Determinants, Permanents, and (Unique)
Matchings",
journal = j-TOCT,
volume = "1",
number = "3",
pages = "10:1--10:??",
month = mar,
year = "2010",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1714450.1714453",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Mar 16 10:08:04 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Yin:2010:CPP,
author = "Yitong Yin",
title = "Cell-Probe Proofs",
journal = j-TOCT,
volume = "2",
number = "1",
pages = "1:1--1:??",
month = nov,
year = "2010",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1867719.1867720",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Nov 23 11:20:48 MST 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Hoefer:2010:TAC,
author = "Martin Hoefer and Alexander Souza",
title = "Tradeoffs and Average-Case Equilibria in Selfish
Routing",
journal = j-TOCT,
volume = "2",
number = "1",
pages = "2:1--2:??",
month = nov,
year = "2010",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1867719.1867721",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Tue Nov 23 11:20:48 MST 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Purdy:2011:LBC,
author = "Eric Purdy",
title = "Lower Bounds for Coin-Weighing Problems",
journal = j-TOCT,
volume = "2",
number = "2",
pages = "3:1--3:??",
month = mar,
year = "2011",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1944857.1944858",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Mon Mar 28 09:50:20 MDT 2011",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Arvind:2011:SGI,
author = "Vikraman Arvind and Jacobo Tor{\'a}n",
title = "Solvable Group Isomorphism Is (Almost) in {NP} $\cap$
{coNP}",
journal = j-TOCT,
volume = "2",
number = "2",
pages = "4:1--4:??",
month = mar,
year = "2011",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1944857.1944859",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Mon Mar 28 09:50:20 MDT 2011",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fellows:2011:CDF,
author = "Michael R. Fellows and Jiong Guo and Hannes Moser and
Rolf Niedermeier",
title = "A Complexity Dichotomy for Finding Disjoint Solutions
of Vertex Deletion Problems",
journal = j-TOCT,
volume = "2",
number = "2",
pages = "5:1--5:??",
month = mar,
year = "2011",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/1944857.1944860",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Mon Mar 28 09:50:20 MDT 2011",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Hitchcock:2011:KCR,
author = "John M. Hitchcock and A. Pavan and N. V.
Vinodchandran",
title = "{Kolmogorov} Complexity in Randomness Extraction",
journal = j-TOCT,
volume = "3",
number = "1",
pages = "1:1--1:??",
month = aug,
year = "2011",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2003685.2003686",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Mon Sep 5 16:58:07 MDT 2011",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kulkarni:2011:PIP,
author = "Raghav Kulkarni",
title = "On the Power of Isolation in Planar Graphs",
journal = j-TOCT,
volume = "3",
number = "1",
pages = "2:1--2:??",
month = aug,
year = "2011",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2003685.2003687",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Mon Sep 5 16:58:07 MDT 2011",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Smyth:2011:AQC,
author = "Clifford Smyth",
title = "Approximate Query Complexity",
journal = j-TOCT,
volume = "3",
number = "1",
pages = "3:1--3:??",
month = aug,
year = "2011",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2003685.2003688",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
bibdate = "Mon Sep 5 16:58:07 MDT 2011",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Cook:2012:PBP,
author = "Stephen Cook and Pierre McKenzie and Dustin Wehr and
Mark Braverman and Rahul Santhanam",
title = "Pebbles and Branching Programs for Tree Evaluation",
journal = j-TOCT,
volume = "3",
number = "2",
pages = "4:1--4:??",
month = jan,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2077336.2077337",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Mar 16 15:22:48 MDT 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We introduce the tree evaluation problem, show that it
is in LogDCFL (and hence in $P$), and study its
branching program complexity in the hope of eventually
proving a superlogarithmic space lower bound. The input
to the problem is a rooted, balanced $d$-ary tree of
height h, whose internal nodes are labeled with $d$-ary
functions on $[ k ] = {1,\ldots{} , k}$, and whose
leaves are labeled with elements of $[ k ]$. Each node
obtains a value in $[ k ]$ equal to its $d$-ary
function applied to the values of its $d$ children. The
output is the value of the root. We show that the
standard black pebbling algorithm applied to the binary
tree of height h yields a deterministic $k$-way
branching program with $O(k h)$ states solving this
problem, and we prove that this upper bound is tight
for $h = 2$ and $h = 3$. We introduce a simple semantic
restriction called thrifty on $k$-way branching
programs solving tree evaluation problems and show that
the same state bound of $\Theta ( k h)$ is tight for
all $h \geq 2$ for deterministic thrifty programs. We
introduce fractional pebbling for trees and show that
this yields nondeterministic thrifty programs with
$\Theta(k h/2 + 1)$ states solving the Boolean problem
`determine whether the root has value 1', and prove
that this bound is tight for $h = 2, 3, 4$. We also
prove that this same bound is tight for unrestricted
nondeterministic $k$-way branching programs solving the
Boolean problem for $h = 2, 3$.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Gal:2012:TQL,
author = "Anna Gal and Andrew Mills",
title = "Three-Query Locally Decodable Codes with Higher
Correctness Require Exponential Length",
journal = j-TOCT,
volume = "3",
number = "2",
pages = "5:1--5:??",
month = jan,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2077336.2077338",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Mar 16 15:22:48 MDT 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Locally decodable codes are error-correcting codes
with the extra property that, in order to retrieve the
value of a single input position, it is sufficient to
read a small number of positions of the codeword. We
refer to the probability of getting the correct value
as the correctness of the decoding algorithm. A
breakthrough result by Yekhanin [2007] showed that
3-query linear locally decodable codes may have
subexponential length. The construction of Yekhanin,
and the three query constructions that followed,
achieve correctness only up to a certain limit which is
1--3 $\delta$ for nonbinary codes, where an adversary
is allowed to corrupt up to $\delta$ fraction of the
codeword. The largest correctness for a subexponential
length 3-query binary code is achieved in a
construction by Woodruff [2008], and it is below 1--3
$\delta$. We show that achieving slightly larger
correctness (as a function of $\delta$) requires
exponential codeword length for 3-query codes.
Previously, there were no larger than quadratic lower
bounds known for locally decodable codes with more than
2 queries, even in the case of 3-query linear codes.
Our lower bounds hold for linear codes over arbitrary
finite fields and for binary nonlinear codes.
Considering larger number of queries, we obtain lower
bounds for $q$-query codes for $q > 3$, under certain
assumptions on the decoding algorithm that have been
commonly used in previous constructions. We also prove
bounds on the largest correctness achievable by these
decoding algorithms, regardless of the length of the
code. Our results explain the limitations on
correctness in previous constructions using such
decoding algorithms. In addition, our results imply
trade-offs on the parameters of error-correcting data
structures.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Beame:2012:VMR,
author = "Paul Beame and Trinh Huynh",
title = "The Value of Multiple {Read\slash} Write Streams for
Approximating Frequency Moments",
journal = j-TOCT,
volume = "3",
number = "2",
pages = "6:1--6:??",
month = jan,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2077336.2077339",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Mar 16 15:22:48 MDT 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We consider the read/write streams model, an extension
of the standard data stream model in which an algorithm
can create and manipulate multiple read/write streams
in addition to its input data stream. Like the data
stream model, the most important parameter for this
model is the amount of internal memory used by such an
algorithm. The other key parameters are the number of
streams the algorithm uses and the number of passes it
makes on these streams. We consider how the addition of
multiple streams impacts the ability of algorithms to
approximate the frequency moments of the input stream.
We show that any randomized read/write stream algorithm
with a fixed number of streams and a sublogarithmic
number of passes that produces a constant factor
approximation of the $k$ -th frequency moment $F_k$ of
an input sequence of length of at most $N$ from
$\{1,\ldots{},N\}$ requires space $\Omega(N^{1 - 4/k -
\delta})$ for any $\delta > 0$. For comparison, it is
known that with a single read-only one-pass data stream
there is a randomized constant-factor approximation for
$F_k$ using $\tilde{O}(N^{1 - 2/k})$ space, and that by
sorting, which can be done deterministically in $O(\log
N)$ passes using $3$ read/write streams, $F_k$ can be
computed exactly. Therefore, although the ability to
manipulate multiple read/write streams can add
substantial power to the data stream model, with a
sublogarithmic number of passes this does not
significantly improve the ability to approximate higher
frequency moments efficiently. We obtain our results by
showing a new connection between the read/write streams
model and the multiparty number-in-hand communication
model.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Tani:2012:EQA,
author = "Seiichiro Tani and Hirotada Kobayashi and Keiji
Matsumoto",
title = "Exact Quantum Algorithms for the Leader Election
Problem",
journal = j-TOCT,
volume = "4",
number = "1",
pages = "1:1--1:??",
month = mar,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2141938.2141939",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:48 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "This article gives a separation between quantum and
classical models in pure (i.e., noncryptographic)
computing abilities with no restriction on the amount
of available computing resources, by considering the
exact solvability of the leader election problem in
anonymous networks, a celebrated unsolvable problem in
classical distributed computing. The goal of the leader
election problem is to elect a unique leader from among
distributed parties. In an anonymous network, all
parties with the same number of communication links are
identical. It is well-known that no classical algorithm
can exactly solve (i.e., in bounded time without error)
the leader election problem in anonymous networks, even
if the number of parties is given. This article devises
a quantum algorithm that, if the number of parties is
given, exactly solves the problem for any network
topology in polynomial rounds with polynomial
communication/time complexity with respect to the
number of parties, when the parties are connected with
quantum communication links and they have the ability
of quantum computing. Our algorithm works even when
only an upper bound of the number of parties is given.
In such a case, no classical algorithm can solve the
problem even under the zero-error setting, the setting
in which error is not allowed but running time may be
unbounded.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Cheraghchi:2012:ALT,
author = "Mahdi Cheraghchi and Johan H{\aa}stad and Marcus
Isaksson and Ola Svensson",
title = "Approximating Linear Threshold Predicates",
journal = j-TOCT,
volume = "4",
number = "1",
pages = "2:1--2:??",
month = mar,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2141938.2141940",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:48 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study constraint satisfaction problems on the
domain {-1, 1}, where the given constraints are
homogeneous linear threshold predicates, that is,
predicates of the form $\sgn(w_1 x_1 + \cdots + w_n
x_n)$ for some positive integer weights $w_1, \ldots{},
w_n$. Despite their simplicity, current techniques fall
short of providing a classification of these predicates
in terms of approximability. In fact, it is not easy to
guess whether there exists a homogeneous linear
threshold predicate that is approximation resistant or
not. The focus of this article is to identify and study
the approximation curve of a class of threshold
predicates that allow for nontrivial
approximation. Arguably the simplest such predicate is
the majority predicate $\sgn(x_1 + \cdots + x_n)$, for
which we obtain an almost complete understanding of the
asymptotic approximation curve, assuming the Unique
Games Conjecture. Our techniques extend to a more
general class of ``majority-like'' predicates and we
obtain parallel results for them. In order to classify
these predicates, we introduce the notion of
Chow-robustness that might be of independent
interest.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{De:2012:ELB,
author = "Anindya De and Thomas Watson",
title = "Extractors and Lower Bounds for Locally Samplable
Sources",
journal = j-TOCT,
volume = "4",
number = "1",
pages = "3:1--3:??",
month = mar,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2141938.2141941",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:48 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We consider the problem of extracting randomness from
sources that are efficiently samplable, in the sense
that each output bit of the sampler only depends on
some small number $d$ of the random input bits. As our
main result, we construct a deterministic extractor
that, given any $d$-local source with min-entropy $k$
on $n$ bits, extracts $\Omega(k^2 / n d)$ bits that are
$2^{-n \Omega (1)}$-close to uniform, provided $d \leq
o(\log n)$ and $k \geq n^{2/3 + \gamma}$ (for
arbitrarily small constants $\gamma > 0$). Using our
result, we also improve a result of Viola [2010] who
proved a $1/2 O(1/\log n)$ statistical distance lower
bound for $o(\log n)$-local samplers trying to sample
input-output pairs of an explicit boolean function,
assuming the samplers use at most $n + n^{1 - \delta}$
random bits for some constant $\delta > 0$. Using a
different function, we simultaneously improve the lower
bound to $1/2 - 2^{-n \Omega (1)}$ and eliminate the
restriction on the number of random bits.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Schoenebeck:2012:CCN,
author = "Grant R. Schoenebeck and Salil Vadhan",
title = "The Computational Complexity of {Nash} Equilibria in
Concisely Represented Games",
journal = j-TOCT,
volume = "4",
number = "2",
pages = "4:1--4:??",
month = may,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2189778.2189779",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:49 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Games may be represented in many different ways, and
different representations of games affect the
complexity of problems associated with games, such as
finding a Nash equilibrium. The traditional method of
representing a game is to explicitly list all the
payoffs, but this incurs an exponential blowup as the
number of agents grows. We study two models of
concisely represented games: circuit games, where the
payoffs are computed by a given boolean circuit, and
graph games, where each agent's payoff is a function of
only the strategies played by its neighbors in a given
graph. For these two models, we study the complexity of
four questions: determining if a given strategy is a
Nash equilibrium, finding a Nash equilibrium,
determining if there exists a pure Nash equilibrium,
and determining if there exists a Nash equilibrium in
which the payoffs to a player meet some given
guarantees. In many cases, we obtain tight results,
showing that the problems are complete for various
complexity classes.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kawamura:2012:CTO,
author = "Akitoshi Kawamura and Stephen Cook",
title = "Complexity Theory for Operators in Analysis",
journal = j-TOCT,
volume = "4",
number = "2",
pages = "5:1--5:??",
month = may,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2189778.2189780",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:49 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We propose an extension of the framework for
discussing the computational complexity of problems
involving uncountably many objects, such as real
numbers, sets and functions, that can be represented
only through approximation. The key idea is to use a
certain class of string functions as names representing
these objects. These are more expressive than infinite
sequences, which served as names in prior work that
formulated complexity in more restricted settings. An
advantage of using string functions is that we can
define their size in a way inspired by higher-type
complexity theory. This enables us to talk about
computation on string functions whose time or space is
bounded polynomially in the input size, giving rise to
more general analogues of the classes P, NP, and
PSPACE. We also define NP- and PSPACE-completeness
under suitable many-one reductions. Because our
framework separates machine computation and semantics,
it can be applied to problems on sets of interest in
analysis once we specify a suitable representation
(encoding). As prototype applications, we consider the
complexity of functions (operators) on real numbers,
real sets, and real functions. For example, the task of
numerical algorithms for solving a certain class of
differential equations is naturally viewed as an
operator taking real functions to real functions. As
there was no complexity theory for operators, previous
results only stated how complex the solution can be. We
now reformulate them and show that the operator itself
is polynomial-space complete.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Penna:2012:CRM,
author = "Paolo Penna and Carmine Ventre",
title = "Collusion-Resistant Mechanisms with Verification
Yielding Optimal Solutions",
journal = j-TOCT,
volume = "4",
number = "2",
pages = "6:1--6:??",
month = may,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2189778.2189781",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:49 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A truthful mechanism consists of an algorithm
augmented with a suitable payment function that
guarantees that the players cannot improve their
utilities by cheating. Mechanism design approaches are
particularly appealing for designing protocols that
cannot be manipulated by rational players. We present
new constructions of so-called mechanisms with
verification introduced by Nisan and Ronen [2001]. We
first show how to obtain mechanisms that, for
single-parameter domains, are resistant to coalitions
of colluding agents even if they can exchange
compensations. Based on this result we derive a class
of exact truthful mechanisms with verification for
arbitrary bounded domains. This class of problems
includes most of the problems studied in the
algorithmic mechanism design literature and for which
exact solutions cannot be obtained with truthful
mechanisms without verification. This result is an
improvement over all known previous constructions of
exact mechanisms with verification.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Beyersdorff:2012:PBD,
author = "Olaf Beyersdorff and Nicola Galesi and Massimo Lauria
and Alexander A. Razborov",
title = "Parameterized Bounded-Depth {Frege} Is not Optimal",
journal = j-TOCT,
volume = "4",
number = "3",
pages = "7:1--7:??",
month = sep,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2355580.2355582",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:50 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A general framework for parameterized proof complexity
was introduced by Dantchev et al. [2007]. There, the
authors show important results on tree-like
Parameterized Resolution---a parameterized version of
classical Resolution---and their gap complexity theorem
implies lower bounds for that system. The main result
of this article significantly improves upon this by
showing optimal lower bounds for a parameterized
version of bounded-depth Frege. More precisely, we
prove that the pigeonhole principle requires proofs of
size n$^{\Omega (k)}$ in parameterized bounded-depth
Frege, and, as a special case, in dag-like
Parameterized Resolution. This answers an open question
posed in Dantchev et al. [2007]. In the opposite
direction, we interpret a well-known technique for FPT
algorithms as a DPLL procedure for Parameterized
Resolution. Its generalization leads to a proof search
algorithm for Parameterized Resolution that in
particular shows that tree-like Parameterized
Resolution allows short refutations of all
parameterized contradictions given as bounded-width
CNFs.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Watson:2012:RWW,
author = "Thomas Watson",
title = "Relativized Worlds without Worst-Case to Average-Case
Reductions for {NP}",
journal = j-TOCT,
volume = "4",
number = "3",
pages = "8:1--8:??",
month = sep,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2355580.2355583",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Nov 6 18:23:50 MST 2012",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We prove that, relative to an oracle, there is no
worst-case to average-case reduction for NP. We also
handle classes that are somewhat larger than NP, as
well as worst-case to errorless -average-case
reductions. In fact, we prove that relative to an
oracle, there is no worst-case to
errorless-average-case reduction from NP to
BPP$_{||}^{NP}$. We also handle reductions from NP to
the polynomial-time hierarchy and beyond, under strong
restrictions on the number of queries the reductions
can make.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kayal:2012:SSR,
author = "Neeraj Kayal and Chandan Saha",
title = "On the Sum of Square Roots of Polynomials and Related
Problems",
journal = j-TOCT,
volume = "4",
number = "4",
pages = "9:1--9:??",
month = nov,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2382559.2382560",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sun May 5 09:31:28 MDT 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The sum of square roots over integers problem is the
task of deciding the sign of a nonzero sum, {$ S =
\Sigma_{i = 1}^n \delta_i \cdot \sqrt a_i $}, where
\delta $_i$ \in {+1, -1} and a$_i$ 's are positive
integers that are upper bounded by {$N$} (say). A
fundamental open question in numerical analysis and
computational geometry is whether {$ | S | \geq 1 /
2^{(n \cdot \log N) O(1)} $} when {$ S \neq 0 $}. We
study a formulation of this problem over polynomials.
Given an expression {$ S = \Sigma_{i = 1}^n c_i \cdot
\sqrt f_i (x) $}, where $ c_i $'s belong to a field of
characteristic $0$ and $ f_i $'s are univariate
polynomials with degree bounded by $d$ and $ f_i(0)
\neq 0 $ for all $i$, is it true that the minimum
exponent of $x$ that has a nonzero coefficient in the
power series {$S$} is upper bounded by {$ (n \cdot
d)^{O(1)} $}, unless {$ S = 0 $}? We answer this
question affirmatively. Further, we show that this
result over polynomials can be used to settle
(positively) the sum of square roots problem for a
special class of integers: Suppose each integer $ a_i $
is of the form, {$ a_i = X^d_i + b_{i1} X^{di - 1} +
\ldots {} + b_{idi} $}, $ d_i > 0 $, where {$X$} is a
positive real number and $ b_{ij} $'s are integers. Let
{$ B = \max (| b_{ij} |_{i, j}, 1) $} and $ d = \max_i
\{ d_i \} $. If {$ X > (B + 1)^{(n \cdot d)O(1)} $}
then a nonzero {$ S = \Sigma_{i = 1}^n \delta_i \sqrt
a_i $} is lower bounded as {$ | S | \geq 1 / X^(n \cdot
d)O(1) $}. The constant in {$ O (1) $}, as fixed by our
analysis, is roughly $2$. We then consider the
following more general problem. Given an arithmetic
circuit computing a multivariate polynomial {$ f (X) $}
and integer $d$, is the degree of {$ f (X) $} less than
or equal to $d$ ? We give a {coRP$^{PP}$}-algorithm for
this problem, improving previous results of Allender et
al. [2009] and Koiran and Perifel [2007].",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Pass:2012:PRT,
author = "Rafael Pass and Muthuramakrishnan Venkitasubramaniam",
title = "A Parallel Repetition Theorem for Constant-Round
{Arthur--Merlin} Proofs",
journal = j-TOCT,
volume = "4",
number = "4",
pages = "10:1--10:??",
month = nov,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2382559.2382561",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sun May 5 09:31:28 MDT 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We show a parallel-repetition theorem for
constant-round Arthur--Merlin Proofs, using an
efficient reduction. As a consequence, we show that
parallel repetition reduces the soundness-error at an
optimal rate (up to a negligible factor) in
constant-round public-coin argument systems, and
constant-round public-coin proofs of knowledge. The
first of these results resolves an open question posed
by Bellare, Impagliazzo, and Naor (FOCS'97).",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ron:2012:AIM,
author = "Dana Ron and Ronitt Rubinfeld and Muli Safra and Alex
Samorodnitsky and Omri Weinstein",
title = "Approximating the Influence of Monotone {Boolean}
Functions in {$ O(\sqrt n) $} Query Complexity",
journal = j-TOCT,
volume = "4",
number = "4",
pages = "11:1--11:??",
month = nov,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2382559.2382562",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sun May 5 09:31:28 MDT 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The Total Influence ( Average Sensitivity ) of a
discrete function is one of its fundamental measures.
We study the problem of approximating the total
influence of a monotone Boolean function, which we
denote by {$ I[f] $}. We present a randomized algorithm
that approximates the influence of such functions to
within a multiplicative factor of $ (1 \pm \epsilon) $
by performing {$ O(\sqrt n I[f] \poly (1 / \epsilon))
$} queries. We also prove a lower bound of {$ \Omega
(\sqrt n \log n \cdot I[f]) $} on the query complexity
of any constant factor approximation algorithm for this
problem (which holds for {$ I[f] = \Omega (1) $}),
hence showing that our algorithm is almost optimal in
terms of its dependence on $n$. For general functions,
we give a lower bound of {$ \Omega (n I[f]) $}, which
matches the complexity of a simple sampling
algorithm.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Vlassis:2012:CCS,
author = "Nikos Vlassis and Michael L. Littman and David
Barber",
title = "On the Computational Complexity of Stochastic
Controller Optimization in {POMDPs}",
journal = j-TOCT,
volume = "4",
number = "4",
pages = "12:1--12:??",
month = nov,
year = "2012",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2382559.2382563",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sun May 5 09:31:28 MDT 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We show that the problem of finding an optimal
stochastic blind controller in a Markov decision
process is an NP-hard problem. The corresponding
decision problem is NP-hard in PSPACE and
sqrt-sum-hard, hence placing it in NP would imply
breakthroughs in long-standing open problems in
computer science. Our result establishes that the more
general problem of stochastic controller optimization
in POMDPs is also NP-hard. Nonetheless, we outline a
special case that is convex and admits efficient global
solutions.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Austrin:2013:UP,
author = "Per Austrin and Johan H{\aa}stad",
title = "On the usefulness of predicates",
journal = j-TOCT,
volume = "5",
number = "1",
pages = "1:1--1:??",
month = may,
year = "2013",
CODEN = "????",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:04 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Motivated by the pervasiveness of strong
inapproximability results for Max-CSPs, we introduce a
relaxed notion of an approximate solution of a Max-CSP.
In this relaxed version, loosely speaking, the
algorithm is allowed to replace the constraints of an
instance by some other (possibly real-valued)
constraints, and then only needs to satisfy as many of
the new constraints as possible. To be more precise, we
introduce the following notion of a predicate $P$ being
useful for a (real-valued) objective $Q$: given an
almost satisfiable Max- $P$ instance, there is an
algorithm that beats a random assignment on the
corresponding Max-$Q$ instance applied to the same sets
of literals. The standard notion of a nontrivial
approximation algorithm for a Max-CSP with predicate
$P$ is exactly the same as saying that $P$ is useful
for $P$ itself. We say that $P$ is useless if it is not
useful for any $Q$. This turns out to be equivalent to
the following pseudo-randomness property: given an
almost satisfiable instance of Max- $P$, it is hard to
find an assignment such that the induced distribution
on k -bit strings defined by the instance is not
essentially uniform. Under the unique games conjecture,
we give a complete and simple characterization of
useful Max-CSPs defined by a predicate: such a Max-CSP
is useless if and only if there is a pairwise
independent distribution supported on the satisfying
assignments of the predicate. It is natural to also
consider the case when no negations are allowed in the
CSP instance, and we derive a similar complete
characterization (under the UGC) there as well.
Finally, we also include some results and examples
shedding additional light on the approximability of
certain Max-CSPs.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Beyersdorff:2013:VPC,
author = "Olaf Beyersdorff and Samir Datta and Andreas Krebs and
Meena Mahajan and Gido Scharfenberger-Fabian and
Karteek Sreenivasaiah and Michael Thomas and Heribert
Vollmer",
title = "Verifying proofs in constant depth",
journal = j-TOCT,
volume = "5",
number = "1",
pages = "2:1--2:??",
month = may,
year = "2013",
CODEN = "????",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:04 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "In this paper we initiate the study of proof systems
where verification of proofs proceeds by NC$^0$
circuits. We investigate the question which languages
admit proof systems in this very restricted model.
Formulated alternatively, we ask which languages can be
enumerated by NC$^0$ functions. Our results show that
the answer to this problem is not determined by the
complexity of the language. On the one hand, we
construct NC$^0$ proof systems for a variety of
languages ranging from regular to NP complete. On the
other hand, we show by combinatorial methods that even
easy regular languages such as Exact-OR do not admit
NC$^0$ proof systems. We also show that Majority does
not admit NC$^0$ proof systems. Finally, we present a
general construction of NC$^0$ proof systems for
regular languages with strongly connected NFA's.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Cygan:2013:MCP,
author = "Marek Cygan and Marcin Pilipczuk and Michal Pilipczuk
and Jakub Onufry Wojtaszczyk",
title = "On multiway cut parameterized above lower bounds",
journal = j-TOCT,
volume = "5",
number = "1",
pages = "3:1--3:??",
month = may,
year = "2013",
CODEN = "????",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:04 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We introduce a concept of parameterizing a problem
above the optimum solution of its natural linear
programming relaxation and prove that the node multiway
cut problem is fixed-parameter tractable (FPT) in this
setting. As a consequence we prove that node multiway
cut is FPT, when parameterized above the maximum
separating cut, resolving an open problem of Razgon.
Our results imply $ O^*(4^k) $ algorithms for vertex
cover above maximum matching and almost 2-SAT as well
as an $ O^*(2^k) $ algorithm for node multiway cut with
a standard parameterization by the solution size,
improving previous bounds for these problems.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Englert:2013:EC,
author = "Matthias Englert and Heiko R{\"o}glin and Jacob
Sp{\"o}nemann and Berthold V{\"o}cking",
title = "Economical Caching",
journal = j-TOCT,
volume = "5",
number = "2",
pages = "4:1--4:??",
month = jul,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2493246.2493247",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:08 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study the management of buffers and storages in
environments with unpredictably varying prices in a
competitive analysis. In the economical caching
problem, there is a storage with a certain capacity.
For each time step, an online algorithm is given a
price from the interval $ [1, \alpha] $, a consumption,
and possibly a buying limit. The online algorithm has
to decide the amount to purchase from some commodity,
knowing the parameter $ \alpha $ but without knowing
how the price evolves in the future. The algorithm can
purchase at most the buying limit. If it purchases more
than the current consumption, then the excess is stored
in the storage; otherwise, the gap between consumption
and purchase must be taken from the storage. The goal
is to minimize the total cost. Interesting motivating
applications are, for example, stream caching on mobile
devices with different classes of service, battery
management in micro hybrid cars, and the efficient
purchase of resources. First we consider the simple but
natural class of algorithms that can informally be
described as memoryless. We show that these algorithms
cannot achieve a competitive ratio below $ \sqrt \alpha
$. Then we present a more sophisticated deterministic
algorithm achieving a competitive ratio of where $W$
denotes the Lambert $W$ function. We prove that this
algorithm is optimal and that not even randomized
online algorithms can achieve a better competitive
ratio. On the other hand, we show how to achieve a
constant competitive ratio if the storage capacity of
the online algorithm exceeds the storage capacity of an
optimal offline algorithm by a factor of $ \log \alpha
$.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Bogdanov:2013:HFL,
author = "Andrej Bogdanov and Akinori Kawachi and Hidetoki
Tanaka",
title = "Hard Functions for Low-Degree Polynomials over Prime
Fields",
journal = j-TOCT,
volume = "5",
number = "2",
pages = "5:1--5:??",
month = jul,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2493246.2493248",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:08 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "In this article, we present a new hardness
amplification for low-degree polynomials over prime
fields, namely, we prove that if some function is
mildly hard to approximate by any low-degree
polynomials then the sum of independent copies of the
function is very hard to approximate by them. This
result generalizes the XOR lemma for low-degree
polynomials over the binary field given by Viola and
Wigderson [2008]. The main technical contribution is
the analysis of the Gowers norm over prime fields. For
the analysis, we discuss a generalized low-degree test,
which we call the Gowers test, for polynomials over
prime fields, which is a natural generalization of that
over the binary field given by Alon et al. [2003]. This
Gowers test provides a new technique to analyze the
Gowers norm over prime fields. Actually, the rejection
probability of the Gowers test can be analyzed in the
framework of Kaufman and Sudan [2008]. However, our
analysis is self-contained and quantitatively better.
By using our argument, we also prove the hardness of
modulo functions for low-degree polynomials over prime
fields.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Williams:2013:ATP,
author = "Ryan Williams",
title = "Alternation-Trading Proofs, Linear Programming, and
Lower Bounds",
journal = j-TOCT,
volume = "5",
number = "2",
pages = "6:1--6:??",
month = jul,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2493246.2493249",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:08 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A fertile area of recent research has demonstrated
concrete polynomial-time lower bounds for natural hard
problems on restricted computational models. Among
these problems are Satisfiability, Vertex Cover,
Hamilton Path, MOD$_6$-SAT, Majority-of-Majority-SAT,
and Tautologies, to name a few. The proofs of these
lower bounds follow a proof-by-contradiction strategy
that we call resource trading or alternation trading.
An important open problem is to determine how powerful
such proofs can possibly be. We propose a methodology
for studying these proofs that makes them amenable to
both formal analysis and automated theorem proving. We
prove that the search for better lower bounds can often
be turned into a problem of solving a large series of
linear programming instances. Implementing a
small-scale theorem prover based on these results, we
extract new human-readable time lower bounds for
several problems and identify patterns that allow for
further generalization. The framework can also be used
to prove concrete limitations on the current
techniques.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ron:2013:ANR,
author = "Dana Ron and Gilad Tsur",
title = "On Approximating the Number of Relevant Variables in a
Function",
journal = j-TOCT,
volume = "5",
number = "2",
pages = "7:1--7:??",
month = jul,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2493246.2493250",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:08 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "In this work we consider the problem of approximating
the number of relevant variables in a function given
query access to the function. Since obtaining a
multiplicative factor approximation is hard in general,
we consider several relaxations of the problem. In
particular, we consider a relaxation of the property
testing variant of the problem and we consider
relaxations in which we have a promise that the
function belongs to a certain family of functions
(e.g., linear functions). In the former relaxation the
task is to distinguish between the case that the number
of relevant variables is at most $k$, and the case in
which it is far from any function in which the number
of relevant variables is more than $ (1 + \gamma) k $
for a parameter $ \gamma $. We give both upper bounds
and almost matching lower bounds for the relaxations we
study.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Allender:2013:ISI,
author = "Eric Allender and Shafi Goldwasser",
title = "Introduction to the special issue on innovations in
theoretical computer science 2012",
journal = j-TOCT,
volume = "5",
number = "3",
pages = "8:1--8:??",
month = aug,
year = "2013",
DOI = "http://dx.doi.org/10.1145/2493252.2493253",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:12 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
note = "Special issue on innovations in theoretical computer
science 2012.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Pagh:2013:CMM,
author = "Rasmus Pagh",
title = "Compressed matrix multiplication",
journal = j-TOCT,
volume = "5",
number = "3",
pages = "9:1--9:??",
month = aug,
year = "2013",
DOI = "http://dx.doi.org/10.1145/2493252.2493254",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:12 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
note = "Special issue on innovations in theoretical computer
science 2012.",
abstract = "We present a simple algorithm that approximates the
product of $n$-by-$n$ real matrices $A$ and $B$. Let $
|| A B ||_F $ denote the Frobenius norm of $ A B $, and
$b$ be a parameter determining the time\slash accuracy
trade-off. Given $2$-wise independent hash functions $
h_1, h_2 : [n] \to [b] $, and $ s_1, s_2 : [n] \to \{ -
1, + 1 \} $ the algorithm works by first
``compressing'' the matrix product into the polynomial
$ p (x) = \Sigma_{k = 1}^n \left (\Sigma_{i = 1}^n
A_{ik} s_1 (i) x^{h 1 (i)} \right) \left (\Sigma_{j =
1}^n B_{kj} s_2 (j) x^{h 2 (j)} \right) $. Using the
fast Fourier transform to compute polynomial
multiplication, we can compute $ c_0, \ldots {}, c_{b -
1} $ such that $ \Sigma_i c_i x^i = (p (x) \bmod x^b) +
(p (x) \div x^b) $ in time $ {\~ O}(n^2 + n b) $. An
unbiased estimator of $ (A B)_{ij} $ with variance at
most $ || A B ||_F^2 / b $ can then be computed as: $
C_{ij} = s_1 (i) s_2 (j) c_{(h_1 (i) + h_2 (j)) \bmod
b} $. Our approach also leads to an algorithm for
computing AB exactly, with high probability, in time $
{\~ O}(N + n b) $ in the case where $A$ and $B$ have at
most $N$ nonzero entries, and $ A B $ has at most $b$
nonzero entries.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Viderman:2013:LTD,
author = "Michael Viderman",
title = "Linear-time decoding of regular expander codes",
journal = j-TOCT,
volume = "5",
number = "3",
pages = "10:1--10:??",
month = aug,
year = "2013",
DOI = "http://dx.doi.org/10.1145/2493252.2493255",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:12 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
note = "Special issue on innovations in theoretical computer
science 2012.",
abstract = "Sipser and Spielman (IEEE IT, [1996]) showed that any
$ (c, d) $-regular expander code with expansion
parameter $ > 3 / 4 $ is decodable in linear time from
a constant fraction of errors. Feldman et al. (IEEE IT,
[2007]) proved that expansion parameter $ > 2 / 3 + (1
/ 3) c $ is sufficient to correct a constant fraction
of errors in polynomial time using LP decoding. In this
work, we give a simple combinatorial algorithm that
achieves even better parameters. In particular, our
algorithm runs in linear time and works for any
expansion parameter $ > 2 / 3 - (1 / 6) c $. We also
prove that our decoding algorithm can be executed in
logarithmic time on a linear number of parallel
processors.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ozols:2013:QRS,
author = "Maris Ozols and Martin Roetteler and J{\'e}r{\'e}mie
Roland",
title = "Quantum rejection sampling",
journal = j-TOCT,
volume = "5",
number = "3",
pages = "11:1--11:??",
month = aug,
year = "2013",
DOI = "http://dx.doi.org/10.1145/2493252.2493256",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:12 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
note = "Special issue on innovations in theoretical computer
science 2012.",
abstract = "Rejection sampling is a well-known method to sample
from a target distribution, given the ability to sample
from a given distribution. The method has been first
formalized by von Neumann [1951] and has many
applications in classical computing. We define a
quantum analogue of rejection sampling: given a black
box producing a coherent superposition of (possibly
unknown) quantum states with some amplitudes, the
problem is to prepare a coherent superposition of the
same states, albeit with different target amplitudes.
The main result of this article is a tight
characterization of the query complexity of this
quantum state generation problem. We exhibit an
algorithm, which we call quantum rejection sampling,
and analyze its cost using semidefinite programming.
Our proof of a matching lower bound is based on the
automorphism principle that allows to symmetrize any
algorithm over the automorphism group of the problem.
Our main technical innovation is an extension of the
automorphism principle to continuous groups that arise
for quantum state generation problems where the oracle
encodes unknown quantum states, instead of just
classical data. Furthermore, we illustrate how quantum
rejection sampling may be used as a primitive in
designing quantum algorithms, by providing three
different applications. We first show that it was
implicitly used in the quantum algorithm for linear
systems of equations by Harrow et al. [2009]. Second we
show that it can be used to speed up the main step in
the quantum Metropolis sampling algorithm by Temme et
al. [2011]. Finally, we derive a new quantum algorithm
for the hidden shift problem of an arbitrary Boolean
function and relate its query complexity to
``water-filling'' of the Fourier spectrum.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Drucker:2013:HCP,
author = "Andrew Drucker",
title = "High-confidence predictions under adversarial
uncertainty",
journal = j-TOCT,
volume = "5",
number = "3",
pages = "12:1--12:??",
month = aug,
year = "2013",
DOI = "http://dx.doi.org/10.1145/2493252.2493257",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:12 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
note = "Special issue on innovations in theoretical computer
science 2012.",
abstract = "We study the setting in which the bits of an unknown
infinite binary sequence $x$ are revealed sequentially
to an observer. We show that very limited assumptions
about $x$ allow one to make successful predictions
about unseen bits of $x$. First, we study the problem
of successfully predicting a single 0 from among the
bits of $x$. In our model, we have only one chance to
make a prediction, but may do so at a time of our
choosing. This model is applicable to a variety of
situations in which we want to perform an action of
fixed duration, and need to predict a ``safe''
time-interval to perform it. Letting $ N_t $ denote the
number of $1$'s among the first $t$ bits of $x$, we say
that $x$ is ``$ \epsilon $-weakly sparse'' if $ \lim
\inf (N_t / t) < = \epsilon $. Our main result is a
randomized algorithm that, given any $ \epsilon
$-weakly sparse sequence $x$, predicts a $0$ of $x$
with success probability as close as desired to $ 1 -
\epsilon $. Thus, we can perform this task with
essentially the same success probability as under the
much stronger assumption that each bit of $x$ takes the
value $1$ independently with probability $ \epsilon $.
We apply this result to show how to successfully
predict a bit ($0$ or $1$ ) under a broad class of
possible assumptions on the sequence $x$. The
assumptions are stated in terms of the behavior of a
finite automaton $M$ reading the bits of $x$. We also
propose and solve a variant of the well-studied
``ignorant forecasting'' problem. For every $ \epsilon
> 0 $, we give a randomized forecasting algorithm $
S_\epsilon $ that, given sequential access to a binary
sequence $x$, makes a prediction of the form: ``A $p$
fraction of the next $N$ bits will be $1$'s.'' (The
algorithm gets to choose $p$, $N$, and the time of the
prediction.) For any fixed sequence $x$, the forecast
fraction $p$ is accurate to within $ \pm {} \epsilon $
with probability $ 1 - \epsilon $.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Chattopadhyay:2013:GIA,
author = "Arkadev Chattopadhyay and Jacobo Tor{\'a}n and Fabian
Wagner",
title = "Graph Isomorphism is Not {AC$^0$}-Reducible to Group
Isomorphism",
journal = j-TOCT,
volume = "5",
number = "4",
pages = "13:1--13:??",
month = nov,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2540088",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:15 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We give a new upper bound for the Group and Quasigroup
Isomorphism problems when the input structures are
given explicitly by multiplication tables. We show that
these problems can be computed by polynomial size
nondeterministic circuits of unbounded fan-in with $
O(\log \log n) $ depth and $ O(\log^2 n) $
nondeterministic bits, where n is the number of group
elements. This improves the existing upper bound for
the problems. In the previous bound the circuits have
bounded fan-in but depth $ O(\log^2 n) $ and also $
O(\log^2 n) $ nondeterministic bits. We then prove that
the kind of circuits from our upper bound cannot
compute the Parity function. Since Parity is
AC$^0$-reducible to Graph Isomorphism, this implies
that Graph Isomorphism is strictly harder than Group or
Quasigroup Isomorphism under the ordering defined by
AC$^0$ reductions. We extend this result to the
stronger ACC$^0 [p]$ reduction and its randomized
version.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{De:2013:EOH,
author = "Anindya De and Elchanan Mossel",
title = "Explicit Optimal Hardness via {Gaussian} Stability
Results",
journal = j-TOCT,
volume = "5",
number = "4",
pages = "14:1--14:??",
month = nov,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2505766",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:15 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The results of Raghavendra [2008] show that assuming
Khot's Unique Games Conjecture [2002], for every
constraint satisfaction problem there exists a generic
semidefinite program that achieves the optimal
approximation factor. This result is existential as it
does not provide an explicit optimal rounding procedure
nor does it allow to calculate exactly the Unique Games
hardness of the problem. Obtaining an explicit optimal
approximation scheme and the corresponding
approximation factor is a difficult challenge for each
specific approximation problem. Khot et al. [2004]
established a general approach for determining the
exact approximation factor and the corresponding
optimal rounding algorithm for any given constraint
satisfaction problem. However, this approach crucially
relies on results explicitly proving optimal partitions
in the Gaussian space. Until recently, Borell's result
[1985] was the only nontrivial Gaussian partition
result known. In this article we derive the first
explicit optimal approximation algorithm and the
corresponding approximation factor using a new result
on Gaussian partitions due to Isaksson and Mossel
[2012]. This Gaussian result allows us to determine the
exact Unique Games Hardness of MAX-$3$-EQUAL. In
particular, our results show that Zwick's algorithm for
this problem achieves the optimal approximation factor
and prove that the approximation achieved by the
algorithm is $ \approx 0.796 $ as conjectured by Zwick
[1998]. We further use the previously known optimal
Gaussian partitions results to obtain a new Unique
Games Hardness factor for MAX-$k$-CSP: Using the
well-known fact that jointly normal pairwise
independent random variables are fully independent, we
show that the UGC hardness of Max-$k$-CSP is $ \lceil
(k + 1) / 2 \rceil 2^{k - 1} $, improving on results of
Austrin and Mossel [2009].",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Dalmau:2013:RSC,
author = "V{\'\i}ctor Dalmau and Andrei Krokhin",
title = "Robust Satisfiability for {CSPs}: Hardness and
Algorithmic Results",
journal = j-TOCT,
volume = "5",
number = "4",
pages = "15:1--15:??",
month = nov,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2540090",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:15 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "An algorithm for a constraint satisfaction problem is
called robust if it outputs an assignment satisfying at
least a $ (1 - f (\epsilon)) $-fraction of constraints
for each $ (1 - \epsilon) $-satisfiable instance (i.e.,
such that at most a \epsilon -fraction of constraints
needs to be removed to make the instance satisfiable),
where $ f(\epsilon) \to 0 $ as $ \epsilon \to 0 $. We
establish an algebraic framework for analyzing
constraint satisfaction problems admitting an efficient
robust algorithm with functions $f$ of a given growth
rate. We use this framework to derive hardness results.
We also describe three classes of problems admitting an
efficient robust algorithm such that $f$ is $ O (1 /
\log (1 / \epsilon)) $, $ O(\epsilon^{1 / k}) $ for
some $ k > 1 $, and $ O(\epsilon) $, respectively.
Finally, we give a complete classification of robust
satisfiability with a given $f$ for the Boolean case.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fellows:2013:DFP,
author = "Michael Fellows and Fedor V. Fomin and Daniel
Lokshtanov and Elena Losievskaja and Frances Rosamond
and Saket Saurabh",
title = "Distortion is Fixed Parameter Tractable",
journal = j-TOCT,
volume = "5",
number = "4",
pages = "16:1--16:??",
month = nov,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2489789",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:15 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study low-distortion embedding of metric spaces
into the line, and more generally, into the shortest
path metric of trees, from the parameterized complexity
perspective. Let $ M = M (G) $ be the shortest path
metric of an edge-weighted graph $G$, with the vertex
set $ V (G) $ and the edge set $ E (G) $, on $n$
vertices. We give the first fixed parameter tractable
algorithm that for an unweighted graph metric $M$ and
integer $d$ either constructs an embedding of $M$ into
the line with distortion at most $d$, or concludes that
no such embedding exists. Our algorithm requires O(
nd$^4$ (2 d + 1)$^{2d}$ ) time which is a significant
improvement over the best previous algorithm that runs
in time $ O(n^{4d + 2} d^{O(1)}) $. Because of its
apparent similarity to the notoriously hard Bandwidth
Minimization problem, we find it surprising that this
problem turns out to be fixed parameter tractable. We
extend our results on embedding unweighted graph metric
into the line in two ways. First, we give an algorithm
to construct small-distortion embeddings of weighted
graph metrics. The running time of our algorithm is $
O(n (d W)^4 (2 d + 1)^{2dW}) $, where $W$ is the
largest edge weight of the input graph. To complement
this result, we show that the exponential dependence on
the maximum edge weight is unavoidable. In particular,
we show that deciding whether a weighted graph metric $
M (G) $ with maximum weight $ W < | V (G)| $ can be
embedded into the line with distortion at most $d$ is
NP-complete for every fixed rational $ d \geq 2 $. This
rules out any possibility of an algorithm with running
time $ O((n W)^{h(d)}) $ where $h$ is a function of $d$
alone. Second, we consider more general host metrics
for which analogous results hold. In particular, we
prove that for any tree $T$ with maximum degree \Delta
, embedding $M$ into a shortest path metric of $T$ is
fixed parameter tractable, parameterized by $ (\Delta,
d) $.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Razborov:2013:RA,
author = "Alexander Razborov and Emanuele Viola",
title = "Real Advantage",
journal = j-TOCT,
volume = "5",
number = "4",
pages = "17:1--17:??",
month = nov,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2540089",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:15 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We highlight the challenge of proving correlation
bounds between boolean functions and real-valued
polynomials, where any non-boolean output counts
against correlation. We prove that real-valued
polynomials of degree $ 1 2 \lg_2 \lg_2 n $ have
correlation with parity at most zero. Such a result is
false for modular and threshold polynomials. Its proof
is based on a variant of an anti-concentration result
by Costello et al. [2006].",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Harkins:2013:ELA,
author = "Ryan C. Harkins and John M. Hitchcock",
title = "Exact Learning Algorithms, Betting Games, and Circuit
Lower Bounds",
journal = j-TOCT,
volume = "5",
number = "4",
pages = "18:1--18:??",
month = nov,
year = "2013",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2539126.2539130",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Dec 12 17:32:15 MST 2013",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "This article extends and improves the work of Fortnow
and Klivans [2009], who showed that if a circuit class
$C$ has an efficient learning algorithm in Angluin's
model of exact learning via equivalence and membership
queries [Angluin 1988], then we have the lower bound
EXP$^{NP}$ not $C$. We use entirely different
techniques involving betting games [Buhrman et al.
2001] to remove the NP oracle and improve the lower
bound to EXP not $C$. This shows that it is even more
difficult to design a learning algorithm for $C$ than
the results of Fortnow and Klivans [2009] indicated. We
also investigate the connection between betting games
and natural proofs, and as a corollary the existence of
strong pseudorandom generators. Our results also yield
further evidence that the class of Boolean circuits has
no efficient exact learning algorithm. This is because
our separation is strong in that it yields a natural
proof [Razborov and Rudich 1997] against the class.
From this we conclude that an exact learning algorithm
for Boolean circuits would imply that strong
pseudorandom generators do not exist, which contradicts
widely believed conjectures from cryptography. As a
corollary we obtain that if strong pseudorandom
generators exist, then there is no exact learning
algorithm for Boolean circuits.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ada:2014:HBP,
author = "Anil Ada and Arkadev Chattopadhyay and Stephen A. Cook
and Lila Fontes and Michal Kouck{\'y} and Toniann
Pitassi",
title = "The Hardness of Being Private",
journal = j-TOCT,
volume = "6",
number = "1",
pages = "1:1--1:??",
month = mar,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2567671",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Apr 1 06:02:31 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Kushilevitz [1989] initiated the study of
information-theoretic privacy within the context of
communication complexity. Unfortunately, it has been
shown that most interesting functions are not privately
computable [Kushilevitz 1989, Brandt and Sandholm
2008]. The unattainability of perfect privacy for many
functions motivated the study of approximate privacy.
Feigenbaum et al. [2010a, 2010b] define notions of
worst-case as well as average-case approximate privacy
and present several interesting upper bounds as well as
some open problems for further study. In this article,
we obtain asymptotically tight bounds on the trade-offs
between both the worst-case and average-case
approximate privacy of protocols and their
communication cost for Vickrey auctions. Further, we
relate the notion of average-case approximate privacy
to other measures based on information cost of
protocols. This enables us to prove exponential lower
bounds on the subjective approximate privacy of
protocols for computing the Intersection function,
independent of its communication cost. This proves a
conjecture of Feigenbaum et al. [2010a].",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Austrin:2014:NNH,
author = "Per Austrin and Ryan O'Donnell and Li-Yang Tan and
John Wright",
title = "New {NP}-Hardness Results for $3$-Coloring and
$2$-to-$1$ Label Cover",
journal = j-TOCT,
volume = "6",
number = "1",
pages = "2:1--2:??",
month = mar,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2537800",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Apr 1 06:02:31 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We show that given a 3-colorable graph, it is NP-hard
to find a 3-coloring with $ (16 / 17 + \epsilon) $ of
the edges bichromatic. In a related result, we show
that given a satisfiable instance of the 2-to-1 Label
Cover problem, it is NP-hard to find a $ (23 / 24 +
\epsilon) $-satisfying assignment.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Glasser:2014:UDN,
author = "Christian Gla{\ss}er and John M. Hitchcock and A.
Pavan and Stephan Travers",
title = "Unions of Disjoint {NP}-Complete Sets",
journal = j-TOCT,
volume = "6",
number = "1",
pages = "3:1--3:??",
month = mar,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2591508",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Apr 1 06:02:31 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study the following question: if A and B are
disjoint NP-complete sets, then is A \cup B
NP-complete? We provide necessary and sufficient
conditions under which the union of disjoint
NP-complete sets remain complete.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Sun:2014:ECN,
author = "Shu-Ming Sun and Ning Zhong",
title = "On Effective Convergence of Numerical Solutions for
Differential Equations",
journal = j-TOCT,
volume = "6",
number = "1",
pages = "4:1--4:??",
month = mar,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2578219",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Apr 1 06:02:31 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "This article studies the effective convergence of
numerical solutions of initial value problems (IVPs)
for ordinary differential equations (ODEs). A
convergent sequence $ \{ Y_m \} $ of numerical
solutions is said to be effectively convergent to the
exact solution if there is an algorithm that computes
an $ N \in N $, given an arbitrary $ n \in N $ as
input, such that the error between $ Y_m $ and the
exact solution is less than $ 2^{-n} $ for all $ m \geq
N $. It is proved that there are convergent numerical
solutions generated from Euler's method which are not
effectively convergent. It is also shown that a
theoretically-proved-computable solution using Picard's
iteration method might not be computable by classical
numerical methods, which suggests that sometimes there
is a gap between theoretical computability and
practical numerical computations concerning solutions
of ODEs. Moreover, it is noted that the main theorem
(Theorem 4.1) provides an example of an IVP with a
nonuniform Lipschitz function for which the numerical
solutions generated by Euler's method are still
convergent.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{ODonnell:2014:OLB,
author = "Ryan O'Donnell and Yi Wu and Yuan Zhou",
title = "Optimal Lower Bounds for Locality-Sensitive Hashing
(Except When $q$ is Tiny)",
journal = j-TOCT,
volume = "6",
number = "1",
pages = "5:1--5:??",
month = mar,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2578221",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Apr 1 06:02:31 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/hash.bib;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study lower bounds for Locality-Sensitive Hashing
(LSH) in the strongest setting: point sets in $ \{ 0, 1
\}^d $ under the Hamming distance. Recall that $H$ is
said to be an $ (r, c r, p, q) $-sensitive hash family
if all pairs $ x, y \in \{ 0, 1 \}^d $ with $ {\rm
dist}(x, y) \leq r $ have probability at least $p$ of
collision under a randomly chosen $ h \in H $, whereas
all pairs $ x, y \in \{ 0, 1 \}^d $ with $ {\rm
dist}(x, y) \geq c r $ have probability at most $q$ of
collision. Typically, one considers $ d \to \infty $,
with $ c > 1 $ fixed and $q$ bounded away from $0$. For
its applications to approximate nearest-neighbor search
in high dimensions, the quality of an LSH family $H$ is
governed by how small its $ \rho $ parameter $ \rho =
\ln (1 / p) / l n(1 / q) $ is as a function of the
parameter $c$. The seminal paper of Indyk and Motwani
[1998] showed that for each $ c \geq 1 $, the extremely
simple family $ H = \{ x \mapsto x $ _i$ : i \in [d] \}
$ achieves $ \rho \leq 1 / c $. The only known lower
bound, due to Motwani et al. [2007], is that $ \rho $
must be at least $ (e^{1 / c} - 1) / (e^{1 / c} + 1)
\geq .46 / c $ (minus $ o_d(1) $ ). The contribution of
this article is twofold. (1) We show the ``optimal''
lower bound for $ \rho $: it must be at least $ 1 / c $
(minus $ o_d(1) $ ). Our proof is very simple,
following almost immediately from the observation that
the noise stability of a boolean function at time $t$
is a log-convex function of $t$. (2) We raise and
discuss the following issue: neither the application of
LSH to nearest-neighbor search nor the known LSH lower
bounds hold as stated if the q parameter is tiny. Here,
``tiny'' means $ q = 2^{- \Theta (d)} $, a parameter
range we believe is natural.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Cygan:2014:CCG,
author = "Marek Cygan and Stefan Kratsch and Marcin Pilipczuk
and Michal Pilipczuk and Magnus Wahlstr{\"o}m",
title = "Clique Cover and Graph Separation: New
Incompressibility Results",
journal = j-TOCT,
volume = "6",
number = "2",
pages = "6:1--6:??",
month = may,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2594439",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Jun 5 14:42:53 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The field of kernelization studies polynomial-time
preprocessing routines for hard problems in the
framework of parameterized complexity. In this article,
we show that, unless the polynomial hierarchy collapses
to its third level, the following parameterized
problems do not admit a polynomial-time preprocessing
algorithm that reduces the size of an instance to
polynomial in the parameter: ---Edge Clique Cover,
parameterized by the number of cliques, ---Directed
Edge/Vertex Multiway Cut, parameterized by the size of
the cutset, even in the case of two terminals,
---Edge/Vertex Multicut, parameterized by the size of
the cutset, and --- k -Way Cut, parameterized by the
size of the cutset.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Chen:2014:HIA,
author = "Yijia Chen and J{\"o}rg Flum and Moritz M{\"u}ller",
title = "Hard Instances of Algorithms and Proof Systems",
journal = j-TOCT,
volume = "6",
number = "2",
pages = "7:1--7:??",
month = may,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2601336",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Jun 5 14:42:53 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "If the class TAUT of tautologies of propositional
logic has no almost optimal algorithm, then every
algorithm A deciding TAUT has a hard sequence, that is,
a polynomial time computable sequence witnessing that A
is not almost optimal. We show that this result extends
to every $\Pi t p$-complete problem with $t \geq 1$;
however, assuming the Measure Hypothesis, there is a
problem which has no almost optimal algorithm but is
decided by an algorithm without hard sequences. For
problems Q with an almost optimal algorithm, we analyze
whether every algorithm deciding Q, which is not almost
optimal, has a hard sequence.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Goldberg:2014:CAC,
author = "Leslie Ann Goldberg and Mark Jerrum",
title = "The Complexity of Approximately Counting Tree
Homomorphisms",
journal = j-TOCT,
volume = "6",
number = "2",
pages = "8:1--8:??",
month = may,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2600917",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Jun 5 14:42:53 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study two computational problems, parameterised by
a fixed tree H. \#HOMSTO( H ) is the problem of
counting homomorphisms from an input graph G to H.
\#WHOMSTO( H ) is the problem of counting weighted
homomorphisms to H, given an input graph G and a weight
function for each vertex v of G. Even though H is a
tree, these problems turn out to be sufficiently rich
to capture all of the known approximation behaviour in
\# P. We give a complete trichotomy for \#WHOMSTO( H ).
If H is a star, then \#WHOMSTO( H ) is in FP. If H is
not a star but it does not contain a certain induced
subgraph J 3, then \#WHOMSTO( H ) is equivalent under
approximation-preserving (AP) reductions to \#BIS, the
problem of counting independent sets in a bipartite
graph. This problem is complete for the class \#RH \Pi
1 under AP-reductions. Finally, if H contains an
induced J$_3$, then \#WHOMSTO( H ) is equivalent under
AP-reductions to \#SAT, the problem of counting
satisfying assignments to a CNF Boolean formula. Thus,
\#WHOMSTO( H ) is complete for \#P under AP-reductions.
The results are similar for \#HOMSTO( H ) except that a
rich structure emerges if H contains an induced J$_3$.
We show that there are trees H for which \#HOMSTO( H )
is \# SAT -equivalent (disproving a plausible
conjecture of Kelk). However, it is still not known
whether \#HOMSTO( H ) is \#SAT-hard for every tree H
which contains an induced J 3. It turns out that there
is an interesting connection between these
homomorphism-counting problems and the problem of
approximating the partition function of the
ferromagnetic Potts model. In particular, we show that
for a family of graphs Jq, parameterised by a positive
integer q, the problem \#HOMSTO( Jq ) is
AP-interreducible with the problem of approximating the
partition function of the q -state Potts model. It was
not previously known that the Potts model had a
homomorphism-counting interpretation. We use this
connection to obtain some additional upper bounds for
the approximation complexity of \#HOMSTO( Jq ).",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Etessami:2014:NCC,
author = "Kousha Etessami and Alistair Stewart and Mihalis
Yannakakis",
title = "A Note on the Complexity of Comparing Succinctly
Represented Integers, with an Application to Maximum
Probability Parsing",
journal = j-TOCT,
volume = "6",
number = "2",
pages = "9:1--9:??",
month = may,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2601327",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Jun 5 14:42:53 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The following two decision problems capture the
complexity of comparing integers or rationals that are
succinctly represented in product-of-exponentials
notation, or equivalently, via arithmetic circuits
using only multiplication and division gates, and
integer inputs. Input instance: Four lists of positive
integers: a 1,\ldots{}, an \in N+ n; b 1,\ldots{}, bn
\in N+ n; c 1,\ldots{}, cm \in N+ m; d 1, \ldots{}, dm
\in N+ m; where each of the integers is represented in
binary. Problem 1 (equality testing): Decide whether
$a_1 b_1 a_2 b_2 \cdots a_n b_n = c_1 d_1 c_2 d_2
\cdots c_m d_m$. Problem 2 (inequality testing): Decide
whether $a_1 b_1 a_2 b_2 \cdots a_n b_n \geq c_1 d_1
c_2 d_2 \cdots c_m d_m$. Problem 1 is easily decidable
in polynomial time using a simple iterative
algorithm. Problem 2 is much harder. We observe that
the complexity of Problem 2 is intimately connected to
deep conjectures and results in number theory. In
particular, if a refined form of the ABC conjecture
formulated by Baker in 1998 holds, or if the older
Lang-Waldschmidt conjecture (formulated in 1978) on
linear forms in logarithms holds, then Problem 2 is
decidable in P-time (in the standard Turing model of
computation). Moreover, it follows from the best
available quantitative bounds on linear forms in
logarithms, namely, by Baker and W{\"u}stholz [1993] or
Matveev [2000], that if m and n are fixed universal
constants then Problem 2 is decidable in P-time
(without relying on any conjectures). This latter fact
was observed earlier by Shub [1993]. We describe one
application: P-time maximum probability parsing for
arbitrary stochastic context-free grammars (where
\epsilon -rules are allowed).",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Allender:2014:ISI,
author = "Eric Allender and Shafi Goldwasser",
title = "Introduction to the Special Issue on Innovations in
Theoretical Computer Science 2012 --- {Part II}",
journal = j-TOCT,
volume = "6",
number = "3",
pages = "10:1--10:??",
month = jul,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2638595",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:04 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
remark = "Special issue on innovations in theoretical computer
science 2012 --- Part II.",
}
@Article{Kanade:2014:LHS,
author = "Varun Kanade and Thomas Steinke",
title = "Learning Hurdles for Sleeping Experts",
journal = j-TOCT,
volume = "6",
number = "3",
pages = "11:1--11:??",
month = jul,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2505983",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:04 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study the online decision problem in which the set
of available actions varies over time, also called the
sleeping experts problem. We consider the setting in
which the performance comparison is made with respect
to the best ordering of actions in hindsight. In this
article, both the payoff function and the availability
of actions are adversarial. Kleinberg et al. [2010]
gave a computationally efficient no-regret algorithm in
the setting in which payoffs are stochastic. Kanade et
al. [2009] gave an efficient no-regret algorithm in the
setting in which action availability is stochastic.
However, the question of whether there exists a
computationally efficient no-regret algorithm in the
adversarial setting was posed as an open problem by
Kleinberg et al. [2010]. We show that such an algorithm
would imply an algorithm for PAC learning DNF, a
long-standing important open problem. We also consider
the setting in which the number of available actions is
restricted and study its relation to agnostic-learning
monotone disjunctions over examples with bounded
Hamming weight.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
remark = "Special issue on innovations in theoretical computer
science 2012 --- Part II.",
}
@Article{Valiant:2014:ERF,
author = "Paul Valiant",
title = "Evolvability of Real Functions",
journal = j-TOCT,
volume = "6",
number = "3",
pages = "12:1--12:??",
month = jul,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2633598",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:04 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We formulate a notion of evolvability for functions
with domain and range that are real-valued vectors, a
compelling way of expressing many natural biological
processes. We show that linear and fixed-degree
polynomial functions are evolvable in the following
dually-robust sense: There is a single evolution
algorithm that, for all convex loss functions,
converges for all distributions. It is possible that
such dually-robust results can be achieved by simpler
and more-natural evolution algorithms. Towards this
end, we introduce a simple and natural algorithm that
we call wide-scale random noise and prove a
corresponding result for the L$_2$ metric. We
conjecture that the algorithm works for a more general
class of metrics.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
remark = "Special issue on innovations in theoretical computer
science 2012 --- Part II.",
}
@Article{Brakerski:2014:LFH,
author = "Zvika Brakerski and Craig Gentry and Vinod
Vaikuntanathan",
title = "(Leveled) Fully Homomorphic Encryption without
Bootstrapping",
journal = j-TOCT,
volume = "6",
number = "3",
pages = "13:1--13:??",
month = jul,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2633600",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:04 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/cryptography2010.bib;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We present a novel approach to fully homomorphic
encryption (FHE) that dramatically improves performance
and bases security on weaker assumptions. A central
conceptual contribution in our work is a new way of
constructing leveled, fully homomorphic encryption
schemes (capable of evaluating arbitrary
polynomial-size circuits of a-priori bounded depth),
without Gentry's bootstrapping procedure. Specifically,
we offer a choice of FHE schemes based on the learning
with error (LWE) or Ring LWE (RLWE) problems that have
2 \lambda security against known attacks. We construct
the following. (1) A leveled FHE scheme that can
evaluate depth-$L$ arithmetic circuits (composed of
fan-in 2 gates) using $O(\lambda . L 3)$ per-gate
computation, quasilinear in the security
parameter. Security is based on RLWE for an
approximation factor exponential in $L$. This
construction does not use the bootstrapping
procedure. (2) A leveled FHE scheme that can evaluate
depth-$L$ arithmetic circuits (composed of fan-in 2
gates) using $O (\lambda 2)$ per-gate computation,
which is independent of $L$. Security is based on RLWE
for quasipolynomial factors. This construction uses
bootstrapping as an optimization. We obtain similar
results for LWE, but with worse performance. All
previous (leveled) FHE schemes required a per-gate
computation of \Omega (\lambda 3.5), and all of them
relied on subexponential hardness assumptions. We
introduce a number of further optimizations to our
scheme based on the Ring LWE assumption. As an example,
for circuits of large width (e.g., where a constant
fraction of levels have width $ \Omega (\lambda)$), we
can reduce the per-gate computation of the bootstrapped
version to $O (\lambda)$, independent of $L$, by
batching the bootstrapping operation. At the core of
our construction is a new approach for managing the
noise in lattice-based ciphertexts, significantly
extending the techniques of Brakerski and
Vaikuntanathan [2011b].",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
remark = "Special issue on innovations in theoretical computer
science 2012 --- Part II.",
}
@Article{Cook:2014:OWF,
author = "James Cook and Omid Etesami and Rachel Miller and Luca
Trevisan",
title = "On the One-Way Function Candidate Proposed by
{Goldreich}",
journal = j-TOCT,
volume = "6",
number = "3",
pages = "14:1--14:??",
month = jul,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2633602",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:04 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Goldreich [2000] proposed a candidate one-way function
based on a bipartite graph of small right-degree d,
where the vertices on the left (resp. right) represent
input (resp. output) bits of the function. Each output
bit is computed by evaluating a fixed d -ary binary
predicate on the input bits adjacent to that output
bit. We study this function when the predicate is
random or depends linearly on many of its input bits.
We assume that the graph is a random balanced bipartite
graph with right-degree d. Inverting this function as a
one-way function by definition means finding an element
in the preimage of output of this function for a random
input. We bound the expected size of this preimage.
Next, using the preceding bound, we prove that two
restricted types of backtracking algorithms called
myopic and drunk backtracking algorithms with high
probability take exponential time to invert the
function, even if we allow the algorithms to use DPLL
elimination rules. (For drunk algorithms, a similar
result was proved by Itsykson [2010].) We also ran a
SAT solver on the satisfiability problem equivalent to
the problem of inverting the function, and
experimentally observed an exponential increase in
running time as a function of the input length.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
remark = "Special issue on innovations in theoretical computer
science 2012 --- Part II.",
}
@Article{Cook:2014:CCC,
author = "Stephen A. Cook and Yuval Filmus and Dai Tri Man
L{\^e}",
title = "The complexity of the comparator circuit value
problem",
journal = j-TOCT,
volume = "6",
number = "4",
pages = "15:1--15:??",
month = aug,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2635822",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Aug 18 17:06:20 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "In 1990, Subramanian [1990] defined the complexity
class CC as the set of problems log-space reducible to
the comparator circuit value problem (CCV). He and Mayr
showed that NL $ \subseteq $ CC $ \subseteq $ P, and
proved that in addition to CCV several other problems
are complete for CC, including the stable marriage
problem, and finding the lexicographically first
maximal matching in a bipartite graph. Although the
class has not received much attention since then, we
are interested in CC because we conjecture that it is
incomparable with the parallel class NC which also
satisfies NL $ \subseteq $ NC $ \subseteq $ P, and note
that this conjecture implies that none of the
CC-complete problems has an efficient polylog time
parallel algorithm. We provide evidence for our
conjecture by giving oracle settings in which
relativized CC and relativized NC are incomparable. We
give several alternative definitions of CC, including
(among others) the class of problems computed by
uniform polynomial-size families of comparator circuits
supplied with copies of the input and its negation, the
class of problems AC0-reducible to Ccv, and the class
of problems computed by uniform AC0 circuits with AXccv
gates. We also give a machine model for CC, which
corresponds to its characterization as log-space
uniform polynomial-size families of comparator
circuits. These various characterizations show that CC
is a robust class. Our techniques also show that the
corresponding function class FCC is closed under
composition. The main technical tool we employ is
universal comparator circuits. Other results include a
simpler proof of NL $ \subseteq $ CC, a more careful
analysis showing the lexicographically first maximal
matching problem and its variants are CC-complete under
AC0 many-one reductions, and an explanation of the
relation between the Gale--Shapley algorithm and
Subramanian's algorithm for stable marriage. This
article continues the previous work of Cook et al.
[2011], which focused on Cook-Nguyen style uniform
proof complexity, answering several open questions
raised in that article.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fellows:2014:FCU,
author = "Michael R. Fellows and Bart M. P. Jansen",
title = "{FPT} is characterized by useful obstruction sets:
Connecting algorithms, kernels, and quasi-orders",
journal = j-TOCT,
volume = "6",
number = "4",
pages = "16:1--16:??",
month = aug,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2635820",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Aug 18 17:06:20 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Many graph problems were first shown to be
fixed-parameter tractable using the results of
Robertson and Seymour on graph minors. We show that the
combination of finite, computable obstruction sets and
efficient order tests is not just one way of obtaining
strongly uniform FPT algorithms, but that all of FPT
may be captured in this way. Our new characterization
of FPT has a strong connection to the theory of
kernelization, as we prove that problems with
polynomial kernels can be characterized by obstruction
sets whose elements have polynomial size. Consequently
we investigate the interplay between the sizes of
problem kernels and the sizes of the elements of such
obstruction sets, obtaining several examples of how
results in one area yield new insights in the other. We
show how exponential-size minor-minimal obstructions
for pathwidth $k$ form the crucial ingredient in a
novel or-cross-composition for $k$-Pathwidth,
complementing the trivial and-composition that is known
for this problem. In the other direction, we show that
or-cross-compositions into a parameterized problem can
be used to rule out the existence of efficiently
generated quasi-orders on its instances that
characterize the no-instances by polynomial-size
obstructions.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Gobel:2014:CCH,
author = "Andreas G{\"o}bel and Leslie Ann Goldberg and David
Richerby",
title = "The complexity of counting homomorphisms to cactus
graphs modulo 2",
journal = j-TOCT,
volume = "6",
number = "4",
pages = "17:1--17:??",
month = aug,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2635825",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Aug 18 17:06:20 MDT 2014",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A homomorphism from a graph $G$ to a graph $H$ is a
function from $ V(G)$ to $ V(H)$ that preserves edges.
Many combinatorial structures that arise in mathematics
and in computer science can be represented naturally as
graph homomorphisms and as weighted sums of graph
homomorphisms. In this article, we study the complexity
of counting homomorphisms modulo 2. The complexity of
modular counting was introduced by Papadimitriou and
Zachos and it has been pioneered by Valiant who
famously introduced a problem for which counting modulo
7 is easy but counting modulo 2 is intractable. Modular
counting provides a rich setting in which to study the
structure of homomorphism problems. In this case, the
structure of the graph $H$ has a big influence on the
complexity of the problem. Thus, our approach is
graph-theoretic. We give a complete solution for the
class of cactus graphs, which are connected graphs in
which every edge belongs to at most one cycle. Cactus
graphs arise in many applications such as the modelling
of wireless sensor networks and the comparison of
genomes. We show that, for some cactus graphs $H$,
counting homomorphisms to $H$ modulo 2 can be done in
polynomial time. For every other fixed cactus graph
$H$, the problem is complete in the complexity class $
\oplus P$, which is a wide complexity class to which
every problem in the polynomial hierarchy can be
reduced (using randomised reductions). Determining
which $H$ lead to tractable problems can be done in
polynomial time. Our result builds upon the work of
Faben and Jerrum, who gave a dichotomy for the case in
which $H$ is a tree.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Watson:2014:ALB,
author = "Thomas Watson",
title = "Advice Lower Bounds for the Dense Model Theorem",
journal = j-TOCT,
volume = "7",
number = "1",
pages = "1:1--1:??",
month = dec,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2676659",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Jan 13 17:53:00 MST 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We prove a lower bound on the amount of nonuniform
advice needed by black-box reductions for the Dense
Model Theorem of Green, Tao, and Ziegler, and of
Reingold, Trevisan, Tulsiani, and Vadhan. The latter
theorem roughly says that for every distribution $D$
that is $ \delta $-dense in a distribution that is $
\epsilon '$-indistinguishable from uniform, there
exists a ``dense model'' for $D$, that is, a
distribution that is $ \delta $ -dense in the uniform
distribution and is $ \epsilon $-indistinguishable from
$D$. This $ \epsilon $-indistinguishability is with
respect to an arbitrary small class of functions $F$.
For the natural case where $ \epsilon ' \geq \Omega
(\epsilon \delta)$ and $ \epsilon \geq \delta O(1)$,
our lower bound implies that $ \Omega (\sqrt (1 /
\epsilon) \log (1 / \delta) \cdot \log | F |)$ advice
bits are necessary for a certain type of reduction that
establishes a stronger form of the Dense Model Theorem
(and which encompasses all known proofs of the Dense
Model Theorem in the literature). There is only a
polynomial gap between our lower bound and the best
upper bound for this case (due to Zhang), which is $ O
((1 / \epsilon^2) \log (1 / \delta) \cdot \log | F |)$.
Our lower bound can be viewed as an analogue of list
size lower bounds for list-decoding of error-correcting
codes, but for ``dense model decoding'' instead.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Awasthi:2014:LLF,
author = "Pranjal Awasthi and Madhav Jha and Marco Molinaro and
Sofya Raskhodnikova",
title = "Limitations of Local Filters of {Lipschitz} and
Monotone Functions",
journal = j-TOCT,
volume = "7",
number = "1",
pages = "2:1--2:??",
month = dec,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2692372.2692373",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Jan 13 17:53:00 MST 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study local filters for two properties of functions
of the form $ f : \{ 0, 1 d \} \to R $: the Lipschitz
property and monotonicity. A local filter with additive
error a is a randomized algorithm that is given
black-box access to a function $f$ and a query point
$x$ in the domain of $f$. It outputs a value $f$ (x)
such that (i) the reconstructed function $ f(x)$
satisfies the property (in our case, is Lipschitz or
monotone) and (ii) if the input function $f$ satisfies
the property, then for every point $x$ in the domain
(with high constant probability) the reconstructed
value $ F(x)$ differs from $ f(x)$ by at most $a$.
Local filters were introduced by Saks and Seshadhri
[2010]. The relaxed definition we study is due to
Bhattacharyya et al. [2012], except that we further
relax it by allowing additive error. Local filters for
Lipschitz and monotone functions have applications to
areas such as data privacy. We show that every local
filter for Lipschitz or monotone functions runs in time
exponential in the dimension d, even when the filter is
allowed significant additive error. Prior lower bounds
(for local filters with no additive error, that is,
with $ a = 0$) applied only to a more restrictive class
of filters, for example, nonadaptive filters. To prove
our lower bounds, we construct families of hard
functions and show that lookups of a local filter on
these functions are captured by a combinatorial object
that we call a $c$-connector. Then we present a lower
bound on the maximum outdegree of a $c$-connector and
show that it implies the desired bounds on the running
time of local filters. Our lower bounds, in particular,
imply the same bound on the running time for a class of
privacy mechanisms.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Greco:2014:CNC,
author = "Gianluigi Greco and Enrico Malizia and Luigi Palopoli
and Francesco Scarcello",
title = "The Complexity of the Nucleolus in Compact Games",
journal = j-TOCT,
volume = "7",
number = "1",
pages = "3:1--3:??",
month = dec,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2692372.2692374",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Jan 13 17:53:00 MST 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The nucleolus is a well-known solution concept for
coalitional games to fairly distribute the total
available worth among the players. The nucleolus is
known to be NP -hard to compute over compact
coalitional games, that is, over games whose functions
specifying the worth associated with each coalition are
encoded in terms of polynomially computable functions
over combinatorial structures. In particular, hardness
results have been exhibited over minimum spanning tree
games, threshold games, and flow games. However, due to
its intricate definition involving reasoning over
exponentially many coalitions, a nontrivial upper bound
on its complexity was missing in the literature and
looked for. This article faces this question and
precisely characterizes the complexity of the
nucleolus, by exhibiting an upper bound that holds on
any class of compact games, and by showing that this
bound is tight even on the (structurally simple) class
of graph games. The upper bound is established by
proposing a variant of the standard linear-programming
based algorithm for nucleolus computation and by
studying a framework for reasoning about succinctly
specified linear programs, which are contributions of
interest in their own. The hardness result is based on
an elaborate combinatorial reduction, which is
conceptually relevant for it provides a ``measure'' of
the computational cost to be paid for guaranteeing
voluntary participation to the distribution process. In
fact, the pre-nucleolus is known to be efficiently
computable over graph games, with this solution concept
being defined as the nucleolus but without guaranteeing
that each player is granted with it at least the worth
she can get alone, that is, without collaborating with
the other players. Finally, this article identifies
relevant tractable classes of coalitional games, based
on the notion of type of a player. Indeed, in most
applications where many players are involved, it is
often the case that such players do belong in fact to a
limited number of classes, which is known in advance
and may be exploited for computing the nucleolus in a
fast way.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kratsch:2014:KLB,
author = "Stefan Kratsch and Marcin Pilipczuk and Ashutosh Rai
and Venkatesh Raman",
title = "Kernel Lower Bounds using Co-Nondeterminism: Finding
Induced Hereditary Subgraphs",
journal = j-TOCT,
volume = "7",
number = "1",
pages = "4:1--4:??",
month = dec,
year = "2014",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2691321",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue Jan 13 17:53:00 MST 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "This work further explores the applications of
co-nondeterminism for showing kernelization lower
bounds. The only known example prior to this work
excludes polynomial kernelizations for the so-called
Ramsey problem of finding an independent set or a
clique of at least $k$ vertices in a given graph
[Kratsch 2012]. We study the more general problem of
finding induced subgraphs on $k$ vertices fulfilling
some hereditary property $ \Pi $, called $ \Pi
$-Induced Subgraph. The problem is NP-hard for all
nontrivial choices of $ \Pi $ by a classic result of
Lewis and Yannakakis [1980]. The parameterized
complexity of this problem was classified by Khot and
Raman [2002] depending on the choice of $ \Pi $. The
interesting cases for kernelization are for $ \Pi $
containing all independent sets and all cliques, since
the problem is trivially polynomial time solvable or
W[1]-hard otherwise. Our results are twofold. Regarding
$ \Pi $-Induced Subgraph, we show that for a large
choice of natural graph properties $ \Pi $, including
chordal, perfect, cluster, and cograph, there is no
polynomial kernel with respect to $k$. This is
established by two theorems, each one capturing
different (but not necessarily exclusive) sets of
properties: one using a co-nondeterministic variant of
OR-cross-composition and one by a polynomial parameter
transformation from Ramsey. Additionally, we show how
to use improvement versions of NP-hard problems as
source problems for lower bounds, without requiring
their NP-hardness. For example, for $ \Pi $-Induced
Subgraph our compositions may assume existing solutions
of size $ k - 1$. This follows from the more general
fact that source problems for OR-(cross-)compositions
need only be NP-hard under co-nondeterministic
reductions. We believe this to be useful for further
lower-bound proofs, for example, since improvement
versions simplify the construction of a disjunction
(OR) of instances required in compositions. This adds a
second way of using co-nondeterminism for lower
bounds.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Filmus:2015:ELB,
author = "Yuval Filmus and Toniann Pitassi and Rahul Santhanam",
title = "Exponential Lower Bounds for {AC$0$-Frege} Imply
Superpolynomial {Frege} Lower Bounds",
journal = j-TOCT,
volume = "7",
number = "2",
pages = "5:1--5:??",
month = may,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2656209",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue May 12 06:02:22 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We give a general transformation that turns
polynomial-size Frege proofs into subexponential-size
AC$^0$-Frege proofs. This indicates that proving truly
exponential lower bounds for AC$^0$-Frege is hard, as
it is a long-standing open problem to prove
superpolynomial lower bounds for Frege. Our
construction is optimal for proofs of formulas of
unbounded depth. As a consequence of our main result,
we are able to shed some light on the question of
automatizability for bounded-depth Frege systems.
First, we present a simpler proof of the results of
Bonet et al. showing that under cryptographic
assumptions, bounded-depth Frege proofs are not
automatizable. Second, we show that because our proof
is more general, under the right cryptographic
assumptions, it could resolve the automatizability
question for lower-depth Frege systems.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Blaser:2015:SCT,
author = "Markus Bl{\"a}ser and Bodo Manthey",
title = "Smoothed Complexity Theory",
journal = j-TOCT,
volume = "7",
number = "2",
pages = "6:1--6:??",
month = may,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2656210",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue May 12 06:02:22 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Smoothed analysis is a new way of analyzing algorithms
introduced by Spielman and Teng. Classical methods like
worst-case or average-case analysis have accompanying
complexity classes, such as P and Avg-P, respectively.
Whereas worst-case or average-case analysis give us a
means to talk about the running time of a particular
algorithm, complexity classes allow us to talk about
the inherent difficulty of problems. Smoothed analysis
is a hybrid of worst-case and average-case analysis and
compensates some of their drawbacks. Despite its
success for the analysis of single algorithms and
problems, there is no embedding of smoothed analysis
into computational complexity theory, which is
necessary to classify problems according to their
intrinsic difficulty. We propose a framework for
smoothed complexity theory, define the relevant
classes, and prove some first hardness results (of
bounded halting and tiling) and tractability results
(binary optimization problems, graph coloring,
satisfiability) within this framework.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Chen:2015:FCC,
author = "Hubie Chen and Moritz M{\"u}ller",
title = "The Fine Classification of Conjunctive Queries and
Parameterized Logarithmic Space",
journal = j-TOCT,
volume = "7",
number = "2",
pages = "7:1--7:??",
month = may,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2751316",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue May 12 06:02:22 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We perform a fundamental investigation of the
complexity of conjunctive query evaluation from the
perspective of parameterized complexity. We classify
sets of Boolean conjunctive queries according to the
complexity of this problem. Previous work showed that a
set of conjunctive queries is fixed-parameter tractable
precisely when the set is equivalent to a set of
queries having bounded treewidth. We present a fine
classification of query sets up to parameterized
logarithmic space reduction. We show that, in the
bounded treewidth regime, there are three complexity
degrees and that the properties that determine the
degree of a query set are bounded pathwidth and bounded
tree depth. We also engage in a study of the two higher
degrees via logarithmic space machine characterizations
and complete problems. Our work yields a significantly
richer perspective on the complexity of conjunctive
queries and, at the same time, suggests new avenues of
research in parameterized complexity.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Komarath:2015:PEB,
author = "Balagopal Komarath and Jayalal Sarma",
title = "Pebbling, Entropy, and Branching Program Size Lower
Bounds",
journal = j-TOCT,
volume = "7",
number = "2",
pages = "8:1--8:??",
month = may,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2751320",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue May 12 06:02:22 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We contribute to the program of proving lower bounds
on the size of branching programs solving the Tree
Evaluation Problem introduced by Cook et al. [2012].
Proving a superpolynomial lower bound for the size of
nondeterministic thrifty branching programs would be an
important step toward separating NL from P using the
tree evaluation problem. First, we show that Read-Once
Nondeterministic Thrifty BPs are equivalent to whole
black-white pebbling algorithms, thus showing a tight
lower bound (ignoring polynomial factors) for this
model. We then introduce a weaker restriction of
nondeterministic thrifty branching programs called
Bitwise Independence. The best known [Cook et al. 2012]
nondeterministic thrifty branching programs (of size $
O(k^{h / 2 + 1})$) for the tree evaluation problem are
Bitwise Independent. As our main result, we show that
any Bitwise Independent Nondeterministic Thrifty
Branching Program solving $ {\rm BT}_2 (h, k)$ must
have at least $ (k2)^{h / 2}$ states. Prior to this
work, lower bounds were known for nondeterministic
thrifty branching programs only for fixed heights $ h =
2, 3, 4$ [Cook et al. 2012]. We prove our results by
associating a fractional black-white pebbling strategy
with any bitwise independent nondeterministic thrifty
branching program solving the Tree Evaluation Problem.
Such a connection was not known previously, even for
fixed heights. Our main technique is the entropy method
introduced by Jukna and Z{\'a}k [2001] originally in
the context of proving lower bounds for read-once
branching programs. We also show that the previous
lower bounds known [Cook et al. 2012] for deterministic
branching programs for the Tree Evaluation Problem can
be obtained using this approach. Using this method, we
also show tight lower bounds for any $k$-way
deterministic branching program solving the Tree
Evaluation Problem when the instances are restricted to
have the same group operation in all internal nodes.",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{ODonnell:2015:HMM,
author = "Ryan O'Donnell and Yi Wu and Yuan Zhou",
title = "Hardness of {Max-2Lin} and {Max-3Lin} over Integers,
Reals, and Large Cyclic Groups",
journal = j-TOCT,
volume = "7",
number = "2",
pages = "9:1--9:??",
month = may,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2751322",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Tue May 12 06:02:22 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "In 1997, H{\aa}stad showed NP-hardness of $ (1 -
\epsilon, 1 / q + \delta)$-approximating Max-3Lin($
Z_q$); however, it was not until 2007 that Guruswami
and Raghavendra were able to show NP-hardness of $ (1 -
\epsilon, \delta)$-approximating Max-3Lin($Z$). In
2004, Khot--Kindler--Mossel--O'Donnell showed
UG-hardness of $ (1 - \epsilon, \delta)$-approximating
Max-2Lin($ Z_q$) for $ q = q (\epsilon, \delta)$ a
sufficiently large constant; however, achieving the
same hardness for Max-2Lin($Z$) was given as an open
problem in Raghavendra's 2009 thesis. In this work, we
show that fairly simple modifications to the proofs of
the Max-3Lin($ Z_q$) and Max-2Lin($ Z_q$) results yield
optimal hardness results over $Z$. In fact, we show a
kind of ``bicriteria'' hardness: Even when there is a $
(1 - \epsilon)$-good solution over $Z$, it is hard for
an algorithm to find a $ \delta $-good solution over
$Z$, $R$, or $ Z_m$ for any $ m \geq q (\epsilon,
\delta)$ of the algorithm's choosing.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ambainis:2015:LBD,
author = "Andris Ambainis and William Gasarch and Aravind
Srinivasan and Andrey Utis",
title = "Lower Bounds on the Deterministic and Quantum
Communication Complexity of {Hamming}-Distance
Problems",
journal = j-TOCT,
volume = "7",
number = "3",
pages = "10:1--10:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2698587",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Aug 7 10:02:02 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Alice and Bob want to know if two strings of length n
are almost equal. That is, do the strings differ on at
most a bits? Let $ 0 \leq a \leq n - 1 $. We show (1)
any deterministic protocol-as well as any error-free
quantum protocol ($ C* $ version)-for this problem
requires at least $ n - 2 $ bits of communication, and
(2) a lower bound of $ n / 2 - 1 $ for error-free $ Q*
$ quantum protocols. We also show the same results for
determining if two strings differ in exactly $a$ bits.
Our results are obtained by lower-bounding the ranks of
the appropriate matrices.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Jerrum:2015:SHF,
author = "Mark Jerrum and Kitty Meeks",
title = "Some Hard Families of Parameterized Counting
Problems",
journal = j-TOCT,
volume = "7",
number = "3",
pages = "11:1--11:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2786017",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Aug 7 10:02:02 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We consider parameterized subgraph counting problems
of the following form: given a graph $f$G, how many
$k$-tuples of its vertices induce a subgraph with a
given property? A number of such problems are known to
be \#W[1]-complete; here, we substantially generalize
some of these existing results by proving hardness for
two large families of such problems. We demonstrate
that it is \#W[1]-hard to count the number of
$k$-vertex subgraphs having any property where the
number of distinct edge densities of labeled subgraphs
that satisfy the property is $ o(k^2)$. In the special
case in which the property in question depends only on
the number of edges in the subgraph, we give a
strengthening of this result, which leads to our second
family of hard problems.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Case:2015:MD,
author = "Adam Case and Jack H. Lutz",
title = "Mutual Dimension",
journal = j-TOCT,
volume = "7",
number = "3",
pages = "12:1--12:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2786566",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Aug 7 10:02:02 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We define the lower and upper mutual dimensions $ {\rm
mdim}(x : y) $ and $ {\rm Mdim}(x : y) $ between any
two points $x$ and $y$ in Euclidean space. Intuitively,
these are the lower and upper densities of the
algorithmic information shared by $x$ and $y$. We show
that these quantities satisfy the main desiderata for a
satisfactory measure of mutual algorithmic information.
Our main theorem, the data processing inequality for
mutual dimension, says that if $ f : R^m > R^n$ is
computable and Lipschitz, then the inequalities $ {\rm
mdim}(f(x) : y) \leq {\rm mdim} (x : y)$ and $ {\rm
Mdim}(f(x) : y) \leq {\rm Mdim}(x : y)$ hold for all $
x \in R^m$ and $ y \in R^t$. We use this inequality and
related inequalities that we prove in like fashion to
establish conditions under which various classes of
computable functions on Euclidean space preserve or
otherwise transform mutual dimensions between points.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fernau:2015:UPT,
author = "Henning Fernau and Alejandro L{\'o}pez-Ortiz and
Jazm{\'\i}n Romero",
title = "Using Parametric Transformations Toward Polynomial
Kernels for Packing Problems Allowing Overlaps",
journal = j-TOCT,
volume = "7",
number = "3",
pages = "13:1--13:??",
month = jul,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2786015",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Fri Aug 7 10:02:02 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We consider the problem of discovering overlapping
communities in networks that we model as
generalizations of the Set and Graph Packing problems
with overlap. As usual for Set Packing problems, we
seek a collection $ S^' \subseteq S $ consisting of at
least $k$ sets subject to certain disjointness
restrictions. In the $r$-Set Packing with
$t$-Membership, each element of $U$ belongs to at most
$t$ sets of $ S^'$, while in $r$-Set Packing with
$t$-Overlap, each pair of sets in $ S^'$ overlaps in at
most $t$ elements. For both problems, each set of $S$
has at most $r$ elements. Similarly, both of our Graph
Packing problems seek a collection $K$ of at least $k$
subgraphs in a graph $G$, each isomorphic to a graph $
H \in H$. In $H$-Packing with $t$-Membership, each
vertex of $G$ belongs to at most $t$ subgraphs of $K$,
while in $H$-Packing with $t$-Overlap, each pair of
subgraphs in K overlaps in at most $t$ vertices. For
both problems, each member of $H$ has at most $r$
vertices and $m$ edges, where $t$, $r$, and $m$ are
constants. Here, we show NP-completeness results for
all of our packing problems. Furthermore, we give a
dichotomy result for the $H$-Packing with
$t$-Membership problem analogous to the Kirkpatrick and
Hell dichotomy [Kirkpatrick and Hell 1978]. Using
polynomial parameter transformations, we reduce the
$r$-Set Packing with $t$-Membership to a problem kernel
with $ O((r + 1)^r k^r)$ elements and the $H$ Packing
with $t$-Membership and its edge version to problem
kernels with $ O((r + 1)^r k^r)$ and $ O((m + 1)^m
k^m)$ vertices, respectively. On the other hand, by
generalizing [Fellows et al. 2008; Moser 2009], we
achieve a kernel with $ O(r^r k^{r - t - 1})$ elements
for the $r$-Set Packing with $t$ Overlap and kernels
with $ O(r^r k^{r - t - 1})$ and $ O(m^m k^{m - t -
1})$ vertices for the $H$-Packing with $t$-Overlap and
its edge version, respectively. In all cases, $k$ is
the input parameter, while $t$, $r$, and $m$ are
constants.",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Drange:2015:ESC,
author = "P{\aa}l Gr{\o}n{\aa}s Drange and Fedor V. Fomin and
Michal Pilipczuk and Yngve Villanger",
title = "Exploring the Subexponential Complexity of Completion
Problems",
journal = j-TOCT,
volume = "7",
number = "4",
pages = "14:1--14:??",
month = sep,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2799640",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:05 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Let $F$ be a family of graphs. In the $F$-Completion
problem, we are given an $n$-vertex graph $G$ and an
integer $k$ as input, and asked whether at most $k$
edges can be added to $G$ so that the resulting graph
does not contain a graph from $F$ as an induced
subgraph. It was shown recently that two special cases
of $F$-Completion, namely, (i) the problem of
completing into a chordal graph known as Minimum
Fill-in (SIAM J. Comput. 2013), which corresponds to
the case of $ F = \{ C_4, C_5, C_6, \ldots \} $, and
(ii) the problem of completing into a split graph
(Algorithmica 2015), that is, the case of $ F = C_4, 2
K_2, C_5$, are solvable in parameterized subexponential
time $ 2^{O (\sqrt k \log k)} n^{O(1)}$. The
exploration of this phenomenon is the main motivation
for our research on $F$-Completion. In this article, we
prove that completions into several well-studied
classes of graphs without long induced cycles and paths
also admit parameterized subexponential time algorithms
by showing that: --- The problem Trivially Perfect
Completion, which is $F$-Completion for $ F = C_4,
P_4$, a cycle and a path on four vertices, is solvable
in parameterized subexponential time $ 2^{O (\sqrt k
\log k)} n^{O(1)}$. --- The problems known in the
literature as Pseudosplit Completion, the case in which
F2 $ K_2$, $ C_4$, and Threshold Completion, in which $
F = 2 K_2, P_4, C_4$, are also solvable in time $ 2^{O
(\sqrt k \log k)} n^{O(1)}$. We complement our
algorithms for $F$-Completion with the following lower
bounds: --- For $ F = 2 K_2$, $ F = C_4$,$ F = P o_4$,
and $ F = {2 K_2, P_4}$, $F$-Completion cannot be
solved in time $ 2^{o(k)} n^{O(1)}$ unless the
Exponential Time Hypothesis (ETH) fails. Our upper and
lower bounds provide a complete picture of the
subexponential parameterized complexity of
$F$-Completion problems for any $ F \subseteq {2 K_2,
C_4, P_4}$.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Regev:2015:QXG,
author = "Oded Regev and Thomas Vidick",
title = "Quantum {XOR} Games",
journal = j-TOCT,
volume = "7",
number = "4",
pages = "15:1--15:??",
month = sep,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2799560",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:05 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We introduce quantum XOR games, a model of two-player,
one-round games that extends the model of XOR games by
allowing the referee's questions to the players to be
quantum states. We give examples showing that quantum
XOR games exhibit a wide range of behaviors that are
known not to exist for standard XOR games, such as
cases in which the use of entanglement leads to an
arbitrarily large advantage over the use of no
entanglement. By invoking two deep extensions of
Grothendieck's inequality, we present an efficient
algorithm that gives a constant-factor approximation to
the best performance that players can obtain in a given
game, both in the case that they have no shared
entanglement and that they share unlimited
entanglement. As a byproduct of the algorithm, we prove
some additional interesting properties of quantum XOR
games, such as the fact that sharing a maximally
entangled state of arbitrary dimension gives only a
small advantage over having no entanglement at all.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Goldreich:2015:IOP,
author = "Oded Goldreich and Or Meir",
title = "Input-Oblivious Proof Systems and a Uniform Complexity
Perspective on {P\slash poly}",
journal = j-TOCT,
volume = "7",
number = "4",
pages = "16:1--16:??",
month = sep,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2799645",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:05 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "An input-oblivious proof system is a proof system in
which the proof does not depend on the claim being
proved. Input-oblivious versions of NP and MA were
introduced in passing by Fortnow, Santhanam, and
Williams, who also showed that those classes are
related to questions on circuit complexity. In this
article, we wish to highlight the notion of
input-oblivious proof systems and initiate a more
systematic study of them. We begin by describing in
detail the results of Fortnow et al. and discussing
their connection to circuit complexity. We then extend
the study to input-oblivious versions of IP, and PCP,
and ZK and present few preliminary results regarding
those versions.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Teutsch:2015:ADM,
author = "Jason Teutsch and Marius Zimand",
title = "On Approximate Decidability of Minimal Programs",
journal = j-TOCT,
volume = "7",
number = "4",
pages = "17:1--17:??",
month = sep,
year = "2015",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2799561",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Thu Oct 1 16:40:05 MDT 2015",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "An index $e$ in a numbering of partial-recursive
functions is called minimal if every lesser index
computes a different function from $e$. Since the
1960s, it has been known that, in any reasonable
programming language, no effective procedure determines
whether or not a given index is minimal. We investigate
whether the task of determining minimal indices can be
solved in an approximate sense. Our first question,
regarding the set of minimal indices, is whether there
exists an algorithm that can correctly label 1 out of
$k$ indices as either minimal or nonminimal. Our second
question, regarding the function that computes minimal
indices, is whether one can compute a short list of
candidate indices that includes a minimal index for a
given program. We give negative answers to both
questions for the important case of numberings with
linearly bounded translators.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kratsch:2016:PCK,
author = "Stefan Kratsch and D{\'a}niel Marx and Magnus
Wahlstr{\"o}m",
title = "Parameterized Complexity and Kernelizability of Max
Ones and Exact Ones Problems",
journal = j-TOCT,
volume = "8",
number = "1",
pages = "1:1--1:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2858787",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat Feb 6 08:06:18 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "For a finite set $ \Gamma $ of Boolean relations, Max
Ones SAT($ \Gamma $) and Exact Ones SAT($ \Gamma $) are
generalized satisfiability problems where every
constraint relation is from $ \Gamma $, and the task is
to find a satisfying assignment with at least/exactly
$k$ variables set to $1$, respectively. We study the
parameterized complexity of these problems, including
the question whether they admit polynomial kernels. For
Max Ones SAT($ \Gamma $), we give a classification into
five different complexity levels: polynomial-time
solvable, admits a polynomial kernel, fixed-parameter
tractable, solvable in polynomial time for fixed $k$,
and NP-hard already for $ k = 1$. For Exact Ones SAT($
\Gamma $), we refine the classification obtained
earlier by taking a closer look at the fixed-parameter
tractable cases and classifying the sets $ \Gamma $ for
which Exact Ones SAT($ \Gamma $) admits a polynomial
kernel.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Volkovich:2016:CAR,
author = "Ilya Volkovich",
title = "Characterizing Arithmetic Read-Once Formulae",
journal = j-TOCT,
volume = "8",
number = "1",
pages = "2:1--2:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2858783",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat Feb 6 08:06:18 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "An arithmetic Read-Once Formula (ROF for short) is a
formula (i.e., a tree of computation) in which the
operations are $ \{ +, \times \} $ and such that every
input variable labels at most one leaf. We give a
simple characterization of such formulae. Other than
being interesting in its own right, our
characterization gives rise to a property-testing
algorithm for functions computable by such formulae. To
the best of our knowledge, prior to our work, no
characterization and/or property-testing algorithm was
known for this kind of formulae.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Schmitz:2016:CHB,
author = "Sylvain Schmitz",
title = "Complexity Hierarchies beyond Elementary",
journal = j-TOCT,
volume = "8",
number = "1",
pages = "3:1--3:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2858784",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat Feb 6 08:06:18 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We introduce a hierarchy of fast-growing complexity
classes and show its suitability for completeness
statements of many nonelementary problems. This
hierarchy allows the classification of many decision
problems with a nonelementary complexity, which occur
naturally in areas such as logic, combinatorics, formal
languages, and verification, with complexities ranging
from simple towers of exponentials to Ackermannian and
beyond.",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ailon:2016:OLR,
author = "Nir Ailon",
title = "An {$ \Omega ((n \log n) / R) $} Lower Bound for
{Fourier} Transform Computation in the {$R$}-Well
Conditioned Model",
journal = j-TOCT,
volume = "8",
number = "1",
pages = "4:1--4:??",
month = feb,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2858785",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat Feb 6 08:06:18 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Obtaining a nontrivial (superlinear) lower bound for
computation of the Fourier transform in the linear
circuit model has been a long-standing open problem for
more than 40 years. An early result by Morgenstern from
1973, provides an $ \Omega (n \log n) $ lower bound for
the unnormalized Fourier transform when the constants
used in the computation are bounded. The proof uses a
potential function related to a determinant. That
result does not explain why the normalized Fourier
transform (of unit determinant) should be difficult to
compute in the same model. Hence, it is not scale
insensitive. More recently, Ailon [2013] showed that if
only unitary 2-by-2 gates are used, and additionally no
extra memory is allowed, then the normalized Fourier
transform requires $ \Omega (n \log n) $ steps. This
rather limited result is also sensitive to scaling, but
highlights the complexity inherent in the Fourier
transform arising from introducing entropy, unlike,
say, the identity matrix (which is as complex as the
Fourier transform using Morgenstern's arguments, under
proper scaling). This work improves on Ailon [2013] in
two ways: First, we eliminate the scaling restriction
and provide a lower bound for computing any scaling of
the Fourier transform. Second, we allow the
computational model to use extra memory. Our
restriction is that the composition of all gates up to
any point must be a well- conditioned linear
transformation. The lower bound is $ \Omega (R^{-1} n
\log n) $, where $R$ is the uniform condition number.
Well-conditioned is a natural requirement for
algorithms accurately computing linear transformations
on machine architectures of bounded word size. Hence,
this result can be seen as a tradeoff between speed and
accuracy. The main technical contribution is an
extension of matrix entropy used in Ailon [2013] for
unitary matrices to a potential function computable for
any invertible matrix, using ``quasi-entropy'' of
``quasi-probabilities.''",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fischer:2016:TRO,
author = "Eldar Fischer and Yonatan Goldhirsh and Oded Lachish",
title = "Testing Read-Once Formula Satisfaction",
journal = j-TOCT,
volume = "8",
number = "2",
pages = "5:1--5:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2897184",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat May 21 08:02:14 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study the query complexity of testing for
properties defined by read-once formulas, as instances
of massively parametrized properties, and prove several
testability and nontestability results. First, we prove
the testability of any property accepted by a Boolean
read-once formula involving any bounded arity gates,
with a number of queries exponential in $ \epsilon $ ,
doubly exponential in the arity, and independent of all
other parameters. When the gates are limited to being
monotone, we prove that there is an estimation
algorithm that outputs an approximation of the distance
of the input from satisfying the property. For formulas
only involving And/Or gates, we provide a more
efficient test whose query complexity is only
quasipolynomial in $ \epsilon $ . On the other hand, we
show that such testability results do not hold in
general for formulas over non-Boolean alphabets.
Specifically, we construct a property defined by a
read-once arity 2 (non-Boolean) formula over an
alphabet of size 4, such that any 1/4-test for it
requires a number of queries depending on the formula
size. We also present such a formula over an alphabet
of size 5 that also satisfies a strong monotonicity
condition.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fellows:2016:TPM,
author = "Michael R. Fellows and Danny Hermelin and Frances
Rosamond and Hadas Shachnai",
title = "Tractable Parameterizations for the Minimum Linear
Arrangement Problem",
journal = j-TOCT,
volume = "8",
number = "2",
pages = "6:1--6:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898352",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat May 21 08:02:14 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The M inimum Linear Arrangement (MLA) problem involves
embedding a given graph on the integer line so that the
sum of the edge lengths of the embedded graph is
minimized. Most layout problems are either intractable
or not known to be tractable, parameterized by the
treewidth of the input graph. We investigate MLA with
respect to three parameters that provide more structure
than treewidth. In particular, we give a factor $ (1 +
\epsilon) $-approximation algorithm for MLA
parameterized by $ (\epsilon, k) $, where $k$ is the
vertex cover number of the input graph. By a similar
approach, we obtain two FPT algorithms that exactly
solve MLA parameterized by, respectively, the max leaf
and edge clique cover numbers of the input graph.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Goldreich:2016:SBT,
author = "Oded Goldreich and Dana Ron",
title = "On Sample-Based Testers",
journal = j-TOCT,
volume = "8",
number = "2",
pages = "7:1--7:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898355",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Sat May 21 08:02:14 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The standard definition of property testing endows the
tester with the ability to make arbitrary queries to
``elements'' of the tested object. In contrast,
sample-based testers only obtain independently
distributed elements (a.k.a. labeled samples) of the
tested object. While sample-based testers were defined
by Goldreich, Goldwasser, and Ron (JACM 1998), with
few exceptions, most research in property testing has
focused on query-based testers. In this work, we
advance the study of sample-based property testers by
providing several general positive results as well as
by revealing relations between variants of this testing
model. In particular: -We show that certain types of
query-based testers yield sample-based testers of
sublinear sample complexity. For example, this holds
for a natural class of proximity oblivious testers. -We
study the relation between distribution-free
sample-based testers and one-sided error sample-based
testers w.r.t. the uniform distribution. While most of
this work ignores the time complexity of testing, one
part of it does focus on this aspect. The main result
in this part is a sublinear- time sample-based tester,
in the dense graphs model, for $k$-colorability, for any
$k \geq 2$.",
acknowledgement = ack-nhfb,
articleno = "7",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Kumar:2016:ACL,
author = "Mrinal Kumar and Gaurav Maheshwari and Jayalal Sarma",
title = "Arithmetic Circuit Lower Bounds via Maximum-Rank of
Partial Derivative Matrices",
journal = j-TOCT,
volume = "8",
number = "3",
pages = "8:1--8:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898437",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Wed May 25 17:15:05 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We introduce the polynomial coefficient matrix and
identify the maximum rank of this matrix under variable
substitution as a complexity measure for multivariate
polynomials. We use our techniques to prove
super-polynomial lower bounds against several classes
of non-multilinear arithmetic circuits. In particular,
we obtain the following results: --- As our first main
result, we prove that any homogeneous depth-3 circuit
for computing the product of d matrices of dimension $
n \times $ n requires $ \Omega (n^{d - 1} / 2^d) $
size. This improves the lower bounds in Nisan and
Wigderson [1995] for $ d = \omega (1) $. --- As our
second main result, we show that there is an explicit
polynomial on $n$ variables and degree at most $ n / 2$
for which any depth-$3$ circuit of product dimension at
most $ n / 10$ (dimension of the space of affine forms
feeding into each product gate) requires size $
2^{\Omega (n)}$. This generalizes the lower bounds
against diagonal circuits proved in Saxena [2008].
Diagonal circuits are of product dimension $1$. --- We
prove a $ n^{ \Omega ( = log n)}$ lower bound on the
size of product-sparse formulas. By definition, any
multilinear formula is a product-sparse formula. Thus,
this result extends the known super-polynomial lower
bounds on the size of multilinear formulas [Raz 2006].
--- We prove a $ 2^{ \Omega (n)}$ lower bound on the
size of partitioned arithmetic branching programs. This
result extends the known exponential lower bound on the
size of ordered arithmetic branching programs [Jansen
2008].",
acknowledgement = ack-nhfb,
articleno = "8",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fulla:2016:GCW,
author = "Peter Fulla and Stanislav Zivn{\'y}",
title = "A {Galois} Connection for Weighted (Relational) Clones
of Infinite Size",
journal = j-TOCT,
volume = "8",
number = "3",
pages = "9:1--9:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898438",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Wed May 25 17:15:05 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A Galois connection between clones and relational
clones on a fixed finite domain is one of the
cornerstones of the so-called algebraic approach to the
computational complexity of non-uniform Constraint
Satisfaction Problems (CSPs). Cohen et al. established
a Galois connection between finitely-generated weighted
clones and finitely-generated weighted relational
clones [SICOMP'13], and asked whether this connection
holds in general. We answer this question in the
affirmative for weighted (relational) clones with real
weights and show that the complexity of the
corresponding valued CSPs is preserved.",
acknowledgement = ack-nhfb,
articleno = "9",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Haviv:2016:LDS,
author = "Ishay Haviv and Oded Regev",
title = "The List-Decoding Size of {Fourier}-Sparse {Boolean}
Functions",
journal = j-TOCT,
volume = "8",
number = "3",
pages = "10:1--10:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898439",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Wed May 25 17:15:05 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A function defined on the Boolean hypercube is
$k$-Fourier-sparse if it has at most $k$ nonzero
Fourier coefficients. For a function $ f : F_2^n \to R$
and parameters $k$ and $d$, we prove a strong upper
bound on the number of $k$-Fourier-sparse Boolean
functions that disagree with $f$ on at most $d$ inputs.
Our bound implies that the number of uniform and
independent random samples needed for learning the
class of $k$-Fourier-sparse Boolean functions on $n$
variables exactly is at most $ O (n \cdot k \log k)$.
As an application, we prove an upper bound on the query
complexity of testing Booleanity of Fourier-sparse
functions. Our bound is tight up to a logarithmic
factor and quadratically improves on a result due to
Gur and Tamuz [2013].",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Nguyen:2016:SPN,
author = "Dung Nguyen and Alan L. Selman",
title = "Structural Properties of Nonautoreducible Sets",
journal = j-TOCT,
volume = "8",
number = "3",
pages = "11:1--11:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898440",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Wed May 25 17:15:05 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We investigate autoreducibility properties of complete
sets for NEXP under different polynomial-time
reductions. Specifically, we show under some
polynomial-time reductions that there are complete sets
for NEXP that are not autoreducible. We obtain the
following main results: -For any positive integers s
and k such that 2$^s$ --- 1 {$>$} k, there is a
{$<$}=$_{s - T}^p$ -complete set for NEXP that is not
{$<$}=$_{k - tt}^p$ -autoreducible. -For every constant
c {$>$} 1, there is a {$<$}=$_{2 - T}^p$ -complete set
for NEXP that is not autoreducible under nonadaptive
reductions that make no more than three queries, such
that each of them has a length between n$^{1 / c}$ and
n$^c$, where n is input size. -For any positive integer
k, there is a {$<$}=$_{k - tt}^p$ -complete set for
NEXP that is not autoreducible under {$<$}=$_{k -
tt}^p$ -reductions whose truth table is not a
disjunction or a negated disjunction. Finally, we show
that settling the question of whether every
{$<$}=$_{dtt}^p$ -complete set for NEXP is {$<$}=$_{NOR
- tt}^p$ -autoreducible either positively or negatively
would lead to major results about the exponential time
complexity classes.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Gobel:2016:CHS,
author = "Andreas G{\"o}bel and Leslie Ann Goldberg and David
Richerby",
title = "Counting Homomorphisms to Square-Free Graphs, Modulo
2",
journal = j-TOCT,
volume = "8",
number = "3",
pages = "12:1--12:??",
month = may,
year = "2016",
CODEN = "????",
DOI = "http://dx.doi.org/10.1145/2898441",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Wed May 25 17:15:05 MDT 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study the problem $ \oplus $ Homs ToH of counting,
modulo 2, the homomorphisms from an input graph to a
fixed undirected graph H. A characteristic feature of
modular counting is that cancellations make wider
classes of instances tractable than is the case for
exact (nonmodular) counting; thus, subtle dichotomy
theorems can arise. We show the following dichotomy:
for any $H$ that contains no 4-cycles, $ \oplus $ Homs
To H is either in polynomial time or is $ \oplus $
P-complete. This partially confirms a conjecture of
Faben and Jerrum that was previously only known to hold
for trees and for a restricted class of tree-width-2
graphs called cactus graphs. We confirm the conjecture
for a rich class of graphs, including graphs of
unbounded tree-width. In particular, we focus on
square-free graphs, which are graphs without 4-cycles.
These graphs arise frequently in combinatorics, for
example, in connection with the strong perfect graph
theorem and in certain graph algorithms. Previous
dichotomy theorems required the graph to be tree-like
so that tree-like decompositions could be exploited in
the proof. We prove the conjecture for a much richer
class of graphs by adopting a much more general
approach.",
acknowledgement = ack-nhfb,
articleno = "12",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Caragiannis:2016:LDA,
author = "Ioannis Caragiannis and Christos Kaklamanis and Maria
Kyropoulou",
title = "Limitations of Deterministic Auction Design for
Correlated Bidders",
journal = j-TOCT,
volume = "8",
number = "4",
pages = "13:1--13:??",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2934309",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "The seminal work of Myerson (Mathematics of OR '81)
characterizes incentive-compatible single-item auctions
among bidders with independent valuations. In this
setting, relatively simple deterministic auction
mechanisms achieve revenue optimality. When bidders
have correlated valuations, designing the
revenue-optimal deterministic auction is a
computationally demanding problem; indeed,
Papadimitriou and Pierrakos (STOC '11) proved that it
is APX-hard, obtaining an explicit inapproximability
factor of 1999/2000 = 99.95\%. In the current article,
we strengthen this inapproximability factor to 63/64
\approx 98.5\%. Our proof is based on a gap-preserving
reduction from the M ax-NM 3SAT problem; a variant of
the maximum satisfiability problem where each clause
has exactly three literals and no clause contains both
negated and unnegated literals. We furthermore show
that the gap between the revenue of deterministic and
randomized auctions can be as low as 13/14 \approx
92.9\%, improving an explicit gap of 947/948 \approx
99.9\% by Dobzinski, Fu, and Kleinberg (STOC '11).",
acknowledgement = ack-nhfb,
articleno = "13",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Gurjar:2016:PGP,
author = "Rohit Gurjar and Arpita Korwar and Jochen Messner and
Simon Straub and Thomas Thierauf",
title = "Planarizing Gadgets for Perfect Matching Do Not
Exist",
journal = j-TOCT,
volume = "8",
number = "4",
pages = "14:1--14:??",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2934310",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "To reduce a graph problem to its planar version, a
standard technique is to replace crossings in a drawing
of the input graph by planarizing gadgets. We show
unconditionally that such a reduction is not possible
for the perfect matching problem and also extend this
to some other problems related to perfect matching. We
further show that there is no planarizing gadget for
the Hamiltonian cycle problem.",
acknowledgement = ack-nhfb,
articleno = "14",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Ron:2016:PEH,
author = "Dana Ron and Gilad Tsur",
title = "The Power of an Example: Hidden Set Size Approximation
Using Group Queries and Conditional Sampling",
journal = j-TOCT,
volume = "8",
number = "4",
pages = "15:1--15:??",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2930657",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "We study a basic problem of approximating the size of
an unknown set S in a known universe U. We consider two
versions of the problem. In both versions, the
algorithm can specify subsets T \subseteq U. In the
first version, which we refer to as the group query or
subset query version, the algorithm is told whether T
\cap S is nonempty. In the second version, which we
refer to as the subset sampling version, if T \cap S is
nonempty, then the algorithm receives a uniformly
selected element from T \cap S. We study the difference
between these two versions in both the case that the
algorithm is adaptive and the case in which it is
nonadaptive. Our main focus is on a natural family of
allowed subsets, which correspond to intervals, as well
as variants of this family.",
acknowledgement = ack-nhfb,
articleno = "15",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Gal:2016:SEA,
author = "Anna G{\'a}l and Jing-Tang Jang and Nutan Limaye and
Meena Mahajan and Karteek Sreenivasaiah",
title = "Space-Efficient Approximations for Subset Sum",
journal = j-TOCT,
volume = "8",
number = "4",
pages = "16:1--16:??",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2894843",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "SubsetSum is a well-known NP-complete problem: given
$t \in Z^+$ and a set $S$ of $m$ positive integers,
output YES if and only if there is a subset $S'
\subseteq S$ such that the sum of all numbers in $S'$
equals $t$. The problem and its search and optimization
versions are known to be solvable in pseudopolynomial
time in general. We develop a one-pass deterministic
streaming algorithm that uses space $ O(\frac {\log
t}{\epsilon })$ and decides if some subset of the input
stream adds up to a value in the range $ \{ (1 \pm
\epsilon) t \} $. Using this algorithm, we design
space-efficient fully polynomial-time approximation
schemes (FPTAS) solving the search and optimization
versions of SubsetSum. Our algorithms run in $ O(\frac
{1}{\epsilon m^2})$ time and $ O(\frac {1}{\epsilon })$
space on unit-cost RAMs, where $ 1 + \epsilon $ is the
approximation factor. This implies constant space
quadratic time FPTAS on unit-cost RAMs when \epsilon is
a constant. Previous FPTAS used space linear in $m$. In
addition, we show that on certain inputs, when a
solution is located within a short prefix of the input
sequence, our algorithms may run in sublinear time. We
apply our techniques to the problem of finding balanced
separators, and we extend our results to some other
variants of the more general knapsack problem. When the
input numbers are encoded in unary, the decision
version has been known to be in $ \log $ space. We give
streaming space lower and upper bounds for unary
SubsetSum (USS). If the input length is $N$ when the
numbers are encoded in unary, we show that randomized s
pass streaming algorithms for exact SubsetSum need
space $ \Omega (\frac {\sqrt {N}}{s})$ and give a
simple deterministic two-pass streaming algorithm using
$ O(\sqrt {N \log N})$ space. Finally, we formulate an
encoding under which USS is monotone and show that the
exact and approximate versions in this formulation have
monotone $ O(\log^2 t)$ depth Boolean circuits. We also
show that any circuit using $ \epsilon $-approximator
gates for SubsetSum under this encoding needs $ \Omega
(n / \log n)$ gates to compute the disjointness
function.",
acknowledgement = ack-nhfb,
articleno = "16",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Lauria:2016:RLB,
author = "Massimo Lauria",
title = "A Rank Lower Bound for Cutting Planes Proofs of
{Ramsey's Theorem}",
journal = j-TOCT,
volume = "8",
number = "4",
pages = "17:1--17:??",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2903266",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Ramsey's Theorem is a cornerstone of combinatorics and
logic. In its simplest formulation it says that for
every $ k > 0 $ and $ s > 0 $, there is a minimum
number $ r(k, s) $ such that any simple graph with at
least $ r (k, s) $ vertices contains either a clique of
size $k$ or an independent set of size $s$. We study
the complexity of proving upper bounds for the number $
r (k, k)$. In particular, we focus on the propositional
proof system cutting planes; we show that any cutting
plane proof of the upper bound ``$ r (k, k) \leq 4^k$''
requires high rank. In order to do that we show a
protection lemma which could be of independent
interest.",
acknowledgement = ack-nhfb,
articleno = "17",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Viola:2016:QMH,
author = "Emanuele Viola",
title = "Quadratic Maps Are Hard to Sample",
journal = j-TOCT,
volume = "8",
number = "4",
pages = "18:1--18:??",
month = jul,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2934308",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "This note proves the existence of a quadratic GF(2)
map $ p \colon \{ 0, 1 \}^n \to \{ 0, 1 \} $ such that
no constant-depth circuit of size $ \poly (n) $ can
sample the distribution $ (u, p(u)) $ for uniform
$u$.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Hrubes:2016:HMV,
author = "P. Hrubes",
title = "On Hardness of Multilinearization and
{VNP}-Completeness in Characteristic $2$",
journal = j-TOCT,
volume = "9",
number = "1",
pages = "1:1--1:??",
month = dec,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2940323",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "For a Boolean function $ f \colon \{ 0, 1 \}^n \to \{
0, 1 \} $, let $ \fcirc $ be the unique multilinear
polynomial such that $ f(x) = \fcirc (x) $ holds for
every $ x \in \{ 0, 1 \}^n $. We show that, assuming VP
/= VNP, there exists a polynomial-time computable $f$
such that $ \fcirc $ requires superpolynomial
arithmetic circuits. In fact, this $f$ can be taken as
a monotone 2-CNF, or a product of affine functions.
This holds over any field. To prove the results in
characteristic 2, we design new VNP-complete families
in this characteristic. This includes the polynomial
EC$_n$ counting edge covers in a graph and the
polynomial mclique$_n$ counting cliques in a graph with
deleted perfect matching. They both correspond to
polynomial-time decidable problems, a phenomenon
previously encountered only in characteristic /= 2.",
acknowledgement = ack-nhfb,
articleno = "1",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Krebs:2016:SDP,
author = "Andreas Krebs and Nutan Limaye and Meena Mahajan and
Karteek Sreenivasaiah",
title = "Small Depth Proof Systems",
journal = j-TOCT,
volume = "9",
number = "1",
pages = "2:1--2:??",
month = dec,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956229",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A proof system for a language L is a function f such
that Range( f ) is exactly L. In this article, we look
at proof systems from a circuit complexity point of
view and study proof systems that are computationally
very restricted. The restriction we study is proof
systems that can be computed by bounded fanin circuits
of constant depth (NC$^0$ ) or of O (log \log n ) depth
but with O (1) alternations (poly \log AC$^0$ ). Each
output bit depends on very few input bits; thus such
proof systems correspond to a kind of local error
correction on a theorem-proof pair. We identify exactly
how much power we need for proof systems to capture all
regular languages. We show that all regular languages
have poly \log AC$^0$ proof systems, and from a
previous result (Beyersdorff et al. [2011a], where
NC$^0$ proof systems were first introduced), this is
tight. Our technique also shows that M aj has poly \log
AC$^0$ proof system. We explore the question of whether
T aut has NC$^0$ proof systems. Addressing this
question about 2TAUT, and since 2TAUT is closely
related to reachability in graphs, we ask the same
question about Reachability. We show that if Directed
reachability has NC$^0$ proof systems, then so does
2TAUT. We then show that both Undirected Reachability
and Directed UnReachability have NC$^0$ proof systems,
but Directed Reachability is still open. In the context
of how much power is needed for proof systems for
languages in NP, we observe that proof systems for a
good fraction of languages in NP do not need the full
power of AC$^0$; they have SAC$^0$ or coSAC$^0$ proof
systems.",
acknowledgement = ack-nhfb,
articleno = "2",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Arvind:2016:NVC,
author = "V. Arvind and P. S. Joglekar and S. Raja",
title = "Noncommutative {Valiant}'s Classes: Structure and
Complete Problems",
journal = j-TOCT,
volume = "9",
number = "1",
pages = "3:1--3:??",
month = dec,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2956230",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "In this article, we explore the noncommutative
analogues, VP$_{nc}$ and VNP$_{nc}$, of Valiant's
algebraic complexity classes and show some striking
connections to classical formal language theory. Our
main results are the following: --- We show that Dyck
polynomials (defined from the Dyck languages of formal
language theory) are complete for the class VP$_{nc}$
under $ \leq_{abp}$ reductions. To the best of our
knowledge, these are the first natural polynomial
families shown to be VP$_{nc}$ -complete. Likewise, it
turns out that PAL (palindrome polynomials defined from
palindromes) are complete for the class VSKEW$_{nc}$
(defined by polynomial-size skew circuits) under $
\leq_{abp}$ reductions. The proof of these results is
by suitably adapting the classical
Chomsky--Sch{\"u}tzenberger theorem showing that Dyck
languages are the hardest CFLs. --- Assuming that
VP$_{nc}$ /= VNP$_{nc}$, we exhibit a strictly infinite
hierarchy of $p$-families, with respect to the
projection reducibility, between the complexity classes
VP$_{nc}$ and VNP$_{nc}$ (analogous to Ladner's theorem
[Ladner 1975]). --- Additionally, inside VP$_{nc}$, we
show that there is a strict hierarchy of p-families
(based on the nesting depth of Dyck polynomials) with
respect to the $ \leq_{abp}$ reducibility (defined
explicitly in this article).",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Fontes:2016:RDD,
author = "Lila Fontes and Rahul Jain and Iordanis Kerenidis and
Sophie Laplante and Mathieu Lauri{\`e}re and
J{\'e}r{\'e}mie Roland",
title = "Relative Discrepancy Does Not Separate Information and
Communication Complexity",
journal = j-TOCT,
volume = "9",
number = "1",
pages = "4:1--4:??",
month = dec,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/2967605",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "Does the information complexity of a function equal
its communication complexity? We examine whether any
currently known techniques might be used to show a
separation between the two notions. Ganor et al. [2014]
recently provided such a separation in the
distributional case for a specific input distribution.
We show that in the non-distributional setting, the
relative discrepancy bound is smaller than the
information complexity; hence, it cannot separate
information and communication complexity. In addition,
in the distributional case, we provide a linear program
formulation for relative discrepancy and relate it to
variants of the partition bound, resolving also an open
question regarding the relation of the partition bound
and information complexity. Last, we prove the
equivalence between the adaptive relative discrepancy
and the public-coin partition, implying that the
logarithm of the adaptive relative discrepancy bound is
quadratically tight with respect to communication.",
acknowledgement = ack-nhfb,
articleno = "4",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}
@Article{Beame:2016:NAF,
author = "Paul Beame and Nathan Grosshans and Pierre McKenzie
and Luc Segoufin",
title = "Nondeterminism and An Abstract Formulation of
{Neciporuk}'s Lower Bound Method",
journal = j-TOCT,
volume = "9",
number = "1",
pages = "5:1--5:??",
month = dec,
year = "2016",
CODEN = "????",
DOI = "https://doi.org/10.1145/3013516",
ISSN = "1942-3454 (print), 1942-3462 (electronic)",
ISSN-L = "1942-3454",
bibdate = "Mon Dec 26 17:25:10 MST 2016",
bibsource = "http://www.acm.org/pubs/contents/journals/toct/;
http://www.math.utah.edu/pub/tex/bib/toct.bib",
abstract = "A formulation of Neciporuk's lower bound method
slightly more inclusive than the usual
complexity-measure-specific formulation is
presented. Using this general formulation, limitations
to lower bounds achievable by the method are obtained
for several computation models, such as branching
programs and Boolean formulas having access to a
sublinear number of nondeterministic bits. In
particular, it is shown that any lower bound achievable
by the method of Neciporuk for the size of
nondeterministic and parity branching programs is at
most $O(n^{3 / 2} / \log n)$.",
acknowledgement = ack-nhfb,
articleno = "5",
fjournal = "ACM Transactions on Computation Theory",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J1190",
}