Computational Complexity (cs.CC)

  • PDF
    This volume contains the papers presented at LINEARITY 2016, the Fourth International Workshop on Linearity, held on June 26, 2016 in Porto, Portugal. The workshop was a one-day satellite event of FSCD 2016, the first International Conference on Formal Structures for Computation and Deduction. The aim of this workshop was to bring together researchers who are developing theory and applications of linear calculi, to foster their interaction and provide a forum for presenting new ideas and work in progress, and enable newcomers to learn about current activities in this area. Of interest were new results that made a central use of linearity, ranging from foundational work to applications in any field. This included: sub-linear logics, linear term calculi, linear type systems, linear proof-theory, linear programming languages, applications to concurrency, interaction-based systems, verification of linear systems, and biological and chemical models of computation.
  • PDF
    We prove a downward separation for $\mathsf{\Sigma}_2$-time classes. Specifically, we prove that if $\Sigma_2$E does not have polynomial size non-deterministic circuits, then $\Sigma_2$SubEXP does not have \textitfixed polynomial size non-deterministic circuits. To achieve this result, we use Santhanam's technique on augmented Arthur-Merlin protocols defined by Aydinlioğlu and van Melkebeek. We show that augmented Arthur-Merlin protocols with one bit of advice do not have fixed polynomial size non-deterministic circuits. We also prove a weak unconditional derandomization of a certain type of promise Arthur-Merlin protocols. Using Williams' easy hitting set technique, we show that $\Sigma_2$-promise AM problems can be decided in $\Sigma_2$SubEXP with $n^c$ advice, for some fixed constant $c$.
  • PDF
    Let $P:\{0,1\}^k \to \{0,1\}$ be a nontrivial $k$-ary predicate. Consider a random instance of the constraint satisfaction problem $\mathrm{CSP}(P)$ on $n$ variables with $\Delta n$ constraints, each being $P$ applied to $k$ randomly chosen literals. Provided the constraint density satisfies $\Delta \gg 1$, such an instance is unsatisfiable with high probability. The \emphrefutation problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate $P$ supports a $t$-\emphwise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree $d = \Theta(\frac{n}{\Delta^{2/(t-1)} \log \Delta})$ (which runs in time $n^{O(d)}$) \emphcannot refute a random instance of $\mathrm{CSP}(P)$. In particular, the polynomial-time SOS algorithm requires $\widetilde{\Omega}(n^{(t+1)/2})$ constraints to refute random instances of CSP$(P)$ when $P$ supports a $t$-wise uniform distribution on its satisfying assignments. Together with recent work of Lee et al. [LRS15], our result also implies that \emphany polynomial-size semidefinite programming relaxation for refutation requires at least $\widetilde{\Omega}(n^{(t+1)/2})$ constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate~$P$, they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen et al. [AOW15] and Raghavendra et al. [RRS16], this full three-way tradeoff is \emphtight, up to lower-order factors.

Recent comments

Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

Māris Ozols Apr 27 2016 22:31 UTC

For inspiration, [here][1] is the first editorial of a newly created open access linguistics journal called *[Glossa][2]*. This journal was established after the editorial board of another journal called *[Lingua][3]* resigned en masse after a disagreement with their owner Elsevier about the pricing

...(continued)
Māris Ozols Mar 09 2016 14:59 UTC

Wow, that's really great! I wasn't expecting that progress on this will be made any time soon, so it's great to hear that somebody is already working on this and trying to change things!

Lidia del Rio Mar 09 2016 14:36 UTC

Marcus Huber, Christian Gogolin and I are actually in the process of setting up an arXiv overlay journal for quant-ph. We are finalizing a draft with the initial proposal and guidelines, and will soon reach out to form an editorial board and open the idea to discussion by the community. More news on

...(continued)
Noon van der Silk Mar 09 2016 00:29 UTC

I don't even really see the point of a journal. Maybe we could adapt SciRate to have a little collection of longer reviews/editorials/etc associated to each article (like comments).

What do you think a journal would offer over SciRate itself? I.e. if the potential paper reviewers would just inste

...(continued)
Juan Bermejo-Vega Mar 08 2016 12:50 UTC

Gower's [earlier post][1] on this arXiv overlay initiative is also very inspiring.

[1]: https://gowers.wordpress.com/2015/09/10/discrete-analysis-an-arxiv-overlay-journal/

Tom Wong Mar 08 2016 11:21 UTC

An arXiv overlay journal was also started for [astrophysics][1], and their source is available on [GitHub][2]. All we need to do is find/replace "astrophysics" with "quantum information" in the source code, and we have a platform.

[1]: http://astro.theoj.org/about
[2]: https://github.com/o

...(continued)
Māris Ozols Mar 08 2016 05:57 UTC

This article just got published in [Discrete Analysis][1], a new arXiv overlay journal that was launched last week (by "published" I simply mean that you can read it for free on arXiv as you would normally do anyway). Just like in any other journal, this article was peer-reviewed, revised, accepted,

...(continued)
Cedric Yen-Yu Lin Jan 11 2016 22:38 UTC

Er, not in any way I know of. Maybe we could've picked a better name...

Māris Ozols Jan 11 2016 20:53 UTC

Is your $\mathsf{QMA_{exp}}$ in any way related to $\mathsf{QMA_{EXP}}$ in [arXiv:0905.2419][1] (see Definition 2.3)?

[1]: http://arxiv.org/abs/0905.2419