Computational Complexity (cs.CC)

  • PDF
    Learning with Errors is one of the fundamental problems in computational learning theory and has in the last years become the cornerstone of post-quantum cryptography. In this work, we study the quantum sample complexity of Learning with Errors and show that there exists an efficient quantum learning algorithm (with polynomial sample and time complexity) for the Learning with Errors problem where the error distribution is the one used in cryptography. While our quantum learning algorithm does not break the LWE-based encryption schemes proposed in the cryptography literature, it does have some interesting implications for cryptography: first, when building an LWE-based scheme, one needs to be careful about the access to the public-key generation algorithm that is given to the adversary; second, our algorithm shows a possible way for attacking LWE-based encryption by using classical samples to approximate the quantum sample state, since then using our quantum learning algorithm would solve LWE.
  • PDF
    We consider the Consensus Patterns problem, where, given a set of input strings, one is asked to extract a long-enough pattern which appears (with some errors) in all strings. We prove that this problem is W[1]-hard when parameterized by the maximum length of input strings.
  • PDF
    In this paper, we study the computational complexity of various problems related to synchronization of weakly acyclic automata, a subclass of widely studied aperiodic automata. We provide upper and lower bounds on the length of a shortest word synchronizing a weakly acyclic automaton or, more generally, a subset of its states, and show that the problem of approximating this length is hard. We also show inapproximability of the problem of computing the rank of a subset of states in a binary weakly acyclic automaton and prove that several problems related to recognizing a synchronizing subset of states in such automata are NP-complete.
  • PDF
    Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable. In this paper we develop algorithmic statistics using space-bounded Kolmogorov complexity. We prove an analogue of one of the main result of `classic' algorithmic statistics (about the connection between optimality and randomness deficiences). The main tool of our proof is the Nisan-Wigderson generator.
  • PDF
    The paper discusses the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates in the case, when the number of additional inputs is limited. We study Shennon's gate complexity function $L(n, q)$ and depth function $D(n,q)$ for a reversible circuit implementing a transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with $8n < q \lesssim n2^{n-o(n)}$ additional inputs. We prove general upper bounds $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ and $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ for this case.
  • PDF
    We prove a complexity dichotomy theorem for the eight-vertex model. For every setting of the parameters of the model, we prove that computing the partition function is either solvable in polynomial time or \#P-hard. The dichotomy criterion is explicit. For tractability, we find some new classes of problems computable in polynomial time. For \#P-hardness, we employ Möbius transformations to prove the success of interpolations.
  • PDF
    We extend Approval voting to the settings where voters may have intransitive preferences. The major obstacle to applying Approval voting in these settings is that voters are not able to clearly determine who they should approve or disapprove, due to the intransitivity of their preferences. An approach to address this issue is to apply tournament solutions to help voters make the decision. We study a class of voting systems where first each voter casts a vote defined as a tournament, then a well-defined tournament solution is applied to select the candidates who are assumed to be approved by the voter. Winners are the ones receiving the most approvals. We study axiomatic properties of this class of voting systems and complexity of control and bribery problems for these voting systems.

Recent comments

Māris Ozols Feb 21 2017 15:35 UTC

I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

...(continued)
Jānis Iraids Jan 25 2017 11:35 UTC

You are correct, that is a mistake -- it should be $\\{0,1\\}^n\rightarrow\\{0,1\\}$. Thank you for spotting it!

Christopher Thomas Chubb Jan 25 2017 02:27 UTC

In the abstract, should the domain of $f$ be $\lbrace0,1\rbrace^n$ instead of just $\lbrace0,1\rbrace$?

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)