Search

The security of most lattice-based cryptography schemes are based on two computational hard problems which are the short integer solution (SIS) and learning with errors (LWE) problems. The computational complexity of SIS and LWE problems are related to approximating shortest vector problem and bounded distance decoding (BDD) problem. Approximating BDD is a special case of approximating closest vector problem (CVP). In this paper, we revisit the study for approximating CVP. We give a proof that approximating the CVP over |$\ell _\infty $| -norm (CVP |$_\infty $|⁠) within any constant factor is NP-hard. The result is obtained by the gap-preserving reduction from Min Total Label Cover problem in |$\ell _1$| -norm to to CVP |$_\infty $|⁠. This proof is simpler than known proofs [ 10 ]. [ABSTRACT FROM AUTHOR]

The issue of the reliable exponential H∞ filtering (HF) is revisited for singular Markovian jump time‐delay systems (SMJTSs) accompanied by sensor failures and interval time‐varying delays. By a new mode‐dependent Lyapunov–Krasovskii functional (LKF) containing three augmented nonintegral terms, some mean‐square exponentially admissible (MSEA) conditions satisfying an H∞ performance are derived subject to state decomposition method. On this basis, a novel reliable filter design approach is first proposed for SMJTSs by means of the idea of the state decomposition and recombining. And the filter parameters we want can be obtained. Worth noting that the results presented are not only related to interval time‐varying delay and sensor failure but also to interval delay‐change‐rate. Meanwhile, the sufficient conditions established have less conservatism and lower computational complexity in comparison with the existing results. The effectiveness and superiority of the proposed methods are verified by two numerical examples derived from some existing papers. [ABSTRACT FROM AUTHOR]

In this paper, we study the approximation complexity of the Minimum Integral Solution Problem with Preprocessing introduced by Alekhnovich et al. (FOCS, pp. 216-225, ). We show that the Minimum Integral Solution Problem with Preprocessing over $$\ell _\infty $$ norm ( $$\hbox {MISPP}_\infty $$ ) is NP-hard to approximate to within a factor of $$(\log n)^{1/2-\epsilon },$$ unless $$\mathbf{NP}\subseteq \mathbf{DTIME}(2^{poly log(n)}).$$ This improves on the best previous result. The best result so far gave $$\sqrt{2}-\epsilon $$ factor hardness for any $$\epsilon >0.$$ [ABSTRACT FROM AUTHOR]

Abstract: The Minimum Integral Solution Problem with preprocessing has been introduced by Alekhnovich, Khot, Kindler, and Vishnoi [M. Alekhnovich, S. Khot, G. Kindler, N. Vishnoi, Hardness of approximating the closest vector problem with preprocessing, in: Proc. 46th IEEE Symposium on FOCS, 2005, pp. 216–225]. They studied the complexity of Minimum Integral Solution Problem with preprocessing over norm . They leave an open problem about the complexity of the Minimum Integral Solution Problem with preprocessing over norm. In this paper, we settle the problem. We show that the Minimum Integral Solution Problem with preprocessing over norm ( ) is NP-hard to approximate to within a factor of for any , unless . [Copyright &y& Elsevier]

Abstract: An equation over a group is an expression of form , where each is either a variable, an inverted variable, or a group constant and denotes the identity element; such an equation is satisfiable if there is a setting of the variables to values in such that the equality is realized (Engebretsen et al. (2002) ). In this paper, we study the problem of simultaneously satisfying a family of equations over an infinite group . Let EQ G [k] denote the problem of determining the maximum number of simultaneously satisfiable equations in which each equation has occurrences of exactly different variables. When is an infinite cyclic group, we show that it is NP-hard to approximate EQ1 G [3] to within , where EQ1 G [3] denotes the special case of EQ G [3] in which a variable may only appear once in each equation; it is NP-hard to approximate EQ1 G [2] to within ; it is NP-hard to approximate the maximum number of simultaneously satisfiable equations of degree at most to within for any ; for any , it is NP-hard to approximate EQ G [k] within any constant factor. These results extend Håstad’s results (Håstad (2001) ) and results of (Engebretsen et al. (2002) ), who established the inapproximability results for equations over finite Abelian groups and any finite groups respectively. [Copyright &y& Elsevier]

Abstract: We introduce the maximum common subgraph problem for multiple graphs (Multi-MCS) inspired by various biological applications such as multiple alignments of gene sequences, protein structures, metabolic pathways, or protein–protein interaction networks. Multi-MCS is a generalization of the two-graph Maximum Common Subgraph problem (MCS). On the basis of the framework of parameterized complexity theory, we derive the parameterized complexity of Multi-MCS for various parameters for different classes of graphs. For example, for directed graphs with labeled vertices, we prove that the parameterized -Multi-MCS problem is [2]-hard, while the parameterized -Multi-MCS problem is -hard (), where and are the size of the maximum common subgraph and the number of multiple graphs, respectively. We show similar results for other parameterized versions of the Multi-MCS problem for directed graphs with vertex labels and undirected graphs with vertex and edge labels by giving linear FPT reductions of the problems from parameterized versions of the longest common subsequence problem. Likewise, for unlabeled undirected graphs, we show that a parameterized version of the Multi-MCS problem with a fixed number of input graphs is [1]-complete by showing a linear FPT reduction to and from a parameterized version of the maximum clique problem. [Copyright &y& Elsevier]

Abstract: In this paper, we study the inapproximability of the following NP-complete number theoretic optimization problems introduced by Rössner and Seifert [C. Rössner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International Algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307–322]: Given numbers , find an -minimum GCD multiplier for , i.e., a vector with minimum satisfying . We show that assuming , it is NP-hard to approximate the Minimum GCD Multiplier in norm () within a factor for some constant where is the dimension of the given vector. This improves on the best previous result. The best result so far gave factor hardness by Rössner and Seifert [C. Rössner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International Algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307–322], where is an arbitrarily small constant. [Copyright &y& Elsevier]

Abstract: Let be any fixed real. We show that assuming , it is hard to approximate the Minimum Solutions of Linear Diophantine Equations in norm within any constant factor and it is also hard to approximate the Minimum Solutions of Linear Diophantine Equations in norm within the factor for some constant where is the number of variables in the equations. [Copyright &y& Elsevier]