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.

Feb 28 2017

cs.CC arXiv:1702.08238v1

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.

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.

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.

Feb 28 2017

cs.CC arXiv:1702.08045v1

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.

Feb 28 2017

cs.CC arXiv:1702.07938v1

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.

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.