%%% -*-BibTeX-*-
%%% ====================================================================
%%%  BibTeX-file{
%%%     author          = "Nelson H. F. Beebe",
%%%     version         = "1.13",
%%%     date            = "05 June 2014",
%%%     time            = "14:48:10 MDT",
%%%     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        = "21825 2517 14025 127476",
%%%     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.13, the COMPLETE journal
%%%                        coverage looked like this:
%%%
%%%                             2009 (   7)    2011 (   6)    2013 (  18)
%%%                             2010 (   5)    2012 (  15)    2014 (   9)
%%%
%%%                             Article:         60
%%%
%%%                             Total entries:   60
%%%
%%%                        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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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://doi.acm.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",
}