Incompressible Functions,Relative-Error Extractors,and the Power of Nondeterministic Reductions

A circuit C compresses a function \({f : \{0,1\}^n\rightarrow \{0,1\}^m}\) if given an input \({x\in \{0,1\}^n}\), the circuit C can shrink x to a shorter ?-bit string x′ such that later, a computationally unbounded solver D will be able to compute f(x) based on x′. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size \({s=n^c}\). Motivated by cryptographic applications, we focus on average-case \({(\ell,\epsilon)}\) incompressibility, which guarantees that on a random input \({x\in \{0,1\}^n}\), for every size s circuit \({C:\{0,1\}^n\rightarrow \{0,1\}^{\ell}}\) and any unbounded solver D, the success probability \({\Pr_x[D(C(x))=f(x)]}\) is upper-bounded by \({2^{-m}+\epsilon}\). While this notion of incompressibility appeared in several works (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work, we present the following results:

1. (1)
   Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) which is incompressible by size n ^c circuits with communication \({\ell=(1-o(1)) \cdot n}\) and error \({\epsilon=n^{-c}}\). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14).
    
2. (2)
   We show that it is possible to achieve negligible error parameter \({\epsilon=n^{-\omega(1)}}\) for nonboolean functions. Specifically, assuming that E is hard for exponential size \({\Sigma_3}\)-circuits, we construct a nonboolean function \({f:\{0,1\}^n\rightarrow \{0,1\}^m}\) which is incompressible by size n ^c circuits with \({\ell=\Omega(n)}\) and extremely small \({\epsilon=n^{-c} \cdot 2^{-m}}\). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest.
    
3. (3)
   We show that the task of constructing an incompressible boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) with negligible error parameter \({\epsilon}\) cannot be achieved by “existing proof techniques”. Namely, nondeterministic reductions (or even \({\Sigma_i}\) reductions) cannot get \({\epsilon=n^{-\omega(1)}}\) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospect, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (STOC 08).
    

     

Data assimilation and sampling in Banach spaces

This paper studies the problem of approximating a function f in a Banach space \(\mathcal{X}\) from measurements \(l_j(f)\), \(j=1,\ldots ,m\), where the \(l_j\) are linear functionals from \(\mathcal{X}^*\). Quantitative results for such recovery problems require additional information about the sought after function f. These additional assumptions take the form of assuming that f is in a certain model class \(K\subset \mathcal{X}\). Since there are generally infinitely many functions in K which share these same measurements, the best approximation is the center of the smallest ball B, called the Chebyshev ball, which contains the set \(\bar{K}\) of all f in K with these measurements. Therefore, the problem is reduced to analytically or numerically approximating this Chebyshev ball. Most results study this problem for classical Banach spaces \(\mathcal{X}\) such as the \(L_p\) spaces, \(1\le p\le \infty \), and for K the unit ball of a smoothness space in \(\mathcal{X}\). Our interest in this paper is in the model classes \(K=\mathcal{K}(\varepsilon ,V)\), with \(\varepsilon >0\) and V a finite dimensional subspace of \(\mathcal{X}\), which consists of all \(f\in \mathcal{X}\) such that \(\mathrm{dist}(f,V)_\mathcal{X}\le \varepsilon \). These model classes, called approximation sets, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance and algorithms for finding near optimal approximations. It builds on the initial analysis given in Maday et al. (Int J Numer Method Eng 102:933–965, 2015) for the case when \(\mathcal{X}\) is a Hilbert space, and further studied in Binev et al. (SIAM UQ, 2015). It is shown how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.     

Testing list <Emphasis Type="Italic">H</Emphasis>-homomorphisms

In the List H- Homomorphism Problem, for a graph H that is a parameter of the problem, an instance consists of an undirected graph G with a list constraint \({L(v) \subseteq V(H)}\) for each variable \({v \in V(G)}\), and the objective is to determine whether there is a list H-homomorphism \({f:V(G) \to V(H)}\), that is, \({f(v) \in L(v)}\) for every \({v \in V(G)}\) and \({(f(u),f(v)) \in E(H)}\) whenever \({(u,v) \in E(G)}\).We consider the problem of testing list H-homomorphisms in the following weighted setting: An instance consists of an undirected graph G, list constraints L, weights imposed on the vertices of G, and a map \({f:V(G) \to V(H)}\) given as an oracle access. The objective is to determine whether f is a list H-homomorphism or far from any list H-homomorphism. The farness is measured by the total weight of vertices \({v \in V(G)}\) for which f(v) must be changed so as to make f a list H-homomorphism. In this paper, we classify graphs H with respect to the number of queries to f required to test the list H-homomorphisms. Specifically, we show that (i) list H-homomorphisms are testable with a constant number of queries if and only if H is a reflexive complete graph or an irreflexive complete bipartite graph and (ii) list H-homomorphisms are testable with a sublinear number of queries if and only if H is a bi-arc graph.     

Flexible bandwidth assignment with application to optical networks

We introduce two scheduling problems, the flexible bandwidth allocation problem (\(\textsc {FBAP}\)) and the flexible storage allocation problem (\(\textsc {FSAP}\)). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In \(\textsc {FBAP}\), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in \(\textsc {FSAP}\) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore \(\text {NP-hard}\). Our main results are a 3-approximation algorithm for \(\textsc {FBAP}\) and a \((3+\epsilon )\)-approximation algorithm for \(\textsc {FSAP}\), for any fixed \(\epsilon >0 \). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a \((2+\epsilon )\)-approximation algorithm for \(\textsc {SAP}\), for any fixed \(\epsilon >0 \), thus improving the best known ratio of \(\frac{2e-1}{e-1} + \epsilon \). Our study is motivated also by critical resource allocation problems arising in all-optical networks.     

Exploring correlation for fast skyline computation

Scaling skyline queries over high-dimensional datasets remains to be challenging due to the fact that most existing algorithms assume dimensional independence when establishing the worst-case complexity by discarding correlation distribution. In this paper, we present HashSkyline, a systematic and correlation-aware approach for scaling skyline queries over high-dimensional datasets with three novel features: First, it offers a fast hash-based method to prune non-skyline points by utilizing data correlation characteristics and speed up the overall skyline evaluation for correlated datasets. Second, we develop \(HashSkyline_{GPU}\), which can dramatically reduce the response time for anti-correlated and independent datasets by capitalizing on the parallel processing power of GPUs. Third, the HashSkyline approach uses the pivot cell-based mechanism combined with the correlation threshold to determine the correlation distribution characteristics for a given dataset, enabling adaptive configuration of HashSkyline for skyline query evaluation by auto-switching of \(HashSkyline_{CPU}\) and \(HashSkyline_{GPU}\). We evaluate the validity of HashSkyline using both synthetic datasets and real datasets. Our experiments show that HashSkyline consumes significantly less pre-processing cost and achieves significantly higher overall query performance, compared to existing state-of-the-art algorithms.     

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.     

New q-ary quantum MDS codes with distances bigger than $$\frac{ q}{2}$$

The construction of quantum MDS codes has been studied by many authors. We refer to the table in page 1482 of (IEEE Trans Inf Theory 61(3):1474–1484, 2015) for known constructions. However, there have been constructed only a few q-ary quantum MDS \([[n,n-2d+2,d]]_q\) codes with minimum distances \(d>\frac{q}{2}\) for sparse lengths \(n>q+1\). In the case \(n=\frac{q^2-1}{m}\) where \(m|q+1\) or \(m|q-1\) there are complete results. In the case \(n=\frac{q^2-1}{m}\) while \(m|q^2-1\) is neither a factor of \(q-1\) nor \(q+1\), no q-ary quantum MDS code with \(d> \frac{q}{2}\) has been constructed. In this paper we propose a direct approach to construct Hermitian self-orthogonal codes over \(\mathbf{F}_{q^2}\). Then we give some new q-ary quantum codes in this case. Moreover many new q-ary quantum MDS codes with lengths of the form \(\frac{w(q^2-1)}{u}\) and minimum distances \(d > \frac{q}{2}\) are presented.     

A counterexample to the chain rule for conditional HILL entropy

Most entropy notions \({H(.)}\) like Shannon or min-entropy satisfy a chain rule stating that for random variables \({X,Z,}\) and \({A}\) we have \({H(X|Z,A)\ge H(X|Z)-|A|}\). That is, by conditioning on \({A}\) the entropy of \({X}\) can decrease by at most the bitlength \({|A|}\) of \({A}\). Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions \({(X,Z,A)}\), where \({A}\) is a distribution over a single bit, such that the HILL entropy H ^HILL \({(X|Z)}\) is large but H ^HILL \({(X|Z,A)}\) is basically zero.Our counterexample just makes the minimal assumption that \({{\mathbf{NP}} \nsubseteq{\mathbf{P/poly}}}\). Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable.Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.     

Exact and approximate flexible aggregate similarity search

Aggregate similarity search, also known as aggregate nearest-neighbor (Ann) query, finds many useful applications in spatial and multimedia databases. Given a group Q of M query objects, it retrieves from a database the objects most similar to Q, where the similarity is an aggregation (e.g., \({{\mathrm{sum}}}\), \(\max \)) of the distances between each retrieved object p and all the objects in Q. In this paper, we propose an added flexibility to the query definition, where the similarity is an aggregation over the distances between p and any subset of \(\phi M\) objects in Q for some support \(0< \phi \le 1\). We call this new definition flexible aggregate similarity search and accordingly refer to a query as a flexible aggregate nearest-neighbor ( Fann ) query. We present algorithms for answering Fann queries exactly and approximately. Our approximation algorithms are especially appealing, which are simple, highly efficient, and work well in both low and high dimensions. They also return near-optimal answers with guaranteed constant-factor approximations in any dimensions. Extensive experiments on large real and synthetic datasets from 2 to 74 dimensions have demonstrated their superior efficiency and high quality.     

Some properties of the disjunctive languages contained in <Emphasis Type="Italic">Q</Emphasis>

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with \({Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}\) are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets \({Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}\) and Q _od = Q \ Q _ev of Q are disjunctive, Chien proved that each of the set \({Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}\) is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages \({Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}\) are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q _n,0) ^k are all regular languages. Some algebraic properties related to the family of languages {Q _n,r | n ≥ 2, 0 ≤ r < n } are investigated.     

Non-determinism in Gödel’s System <Emphasis Type="Italic">T</Emphasis>

The calculus T^? is a successor-free version of Gödel’s T. It is well known that a number of important complexity classes, like e.g. the classes logspace, \(\textsc{p}\), \(\textsc{linspace}\), \(\textsc{etime}\) and \(\textsc{pspace}\), are captured by natural fragments of T^? and related calculi. We introduce the calculus T^∽, which is a non-deterministic variant of T^?, and compare the computational power of T^∽ and T^?. First, we provide a denotational semantics for T^∽ and prove this semantics to be adequate. Furthermore, we prove that \(\textsc{linspace}\subseteq \mathcal {G}^{\backsim }_{0} \subseteq \textsc{linspace}\) and \(\textsc{etime}\subseteq \mathcal {G}^{\backsim }_{1} \subseteq \textsc{pspace}\) where \(\mathcal {G}^{\backsim }_{0}\) and \(\mathcal {G}^{\backsim }_{1}\) are classes of problems decidable by certain fragments of T^∽. (It is proved elsewhere that the corresponding fragments of T^? equal respectively \(\textsc{linspace}\) and \(\textsc{etime}\).) Finally, we show a way to interpret T^∽ in T^?.     

A general framework for architecture composability

Architectures depict design principles: paradigms that can be understood by all, allow thinking on a higher plane and avoiding low-level mistakes. They provide means for ensuring correctness by construction by enforcing global properties characterizing the coordination between components. An architecture can be considered as an operator A that, applied to a set of components \({\mathcal{B}}\), builds a composite component \({A(\mathcal{B})}\) meeting a characteristic property \({\Phi}\). Architecture composability is a basic and common problem faced by system designers. In this paper, we propose a formal and general framework for architecture composability based on an associative, commutative and idempotent architecture composition operator \({\oplus}\). The main result is that if two architectures A ₁ and A ₂ enforce respectively safety properties \({\Phi_{1}}\) and \({\Phi_{2}}\), the architecture \({A_{1} \oplus A_{2}}\) enforces the property \({\Phi_{1} \land \Phi_{2}}\), that is both properties are preserved by architecture composition. We also establish preservation of liveness properties by architecture composition. The presented results are illustrated by a running example and a case study.     

Mutually unbiased maximally entangled bases in $$\mathbb {C}^d\otimes \mathbb {C}^d$$

We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3).     

Inertia-driven enhancement of mixing efficiency in microfluidic cross-junctions: a combined Eulerian/Lagrangian approach

Mixing of a diffusing species entrained in a three-dimensional microfluidic flow-focusing cross-junction is numerically investigated at low Reynolds numbers, \(1 \le Re \le 150\), for a value of the Schmidt number representative of a small solute molecule in water, \(Sc = 10^3\). Accurate three-dimensional simulations of the steady-state incompressible Navier–Stokes equations confirm recent results reported in the literature highlighting the occurrence of different qualitative structures of the flow geometry, whose range of existence depends on Re and on the ratio, R, between the volumetric flowrates of the impinging currents. At low values of R and increasing Re, the flux tube enclosing the solute-rich stream undergoes a topological transition, from the classical flow-focused structure to a multi-branched shape. We here show that this transition causes a nonmonotonic behavior of mixing efficiency with Re at constant flow ratio. The increase in efficiency is the consequence of a progressive compression of the cross-sectional diffusional lengthscale, which provides the mechanism sustaining the transversal Fickian flux even when the Peclet number, \({Pe=Re \, Sc}\), characterizing mass transport, becomes higher due to the increase in Re. The quantitative assessment of mixing efficiency at the considerably high values of the Peclet number considered (\(10^3 \le Pe \le 1.5 \times 10^5\)) is here made possible by a novel method of reconstruction of steady-state cross-sectional concentration maps from velocity-weighted ensemble statistics of noisy trajectories, which does away with the severe numerical diffusion shortcomings associated with classical Eulerian approaches to mass transport in complex 3d flows.     

General tracking control of arbitrary <Emphasis Type="Italic">N</Emphasis>-level quantum systems using piecewise time-independent potentials

Here we propose a tracking quantum control protocol for arbitrary N-level systems. The goal is to make the expected value of an observable \({\mathcal O}\) to follow a predetermined trajectory S(t). For so, we drive the quantum state \(|\varPsi (t) \rangle \) evolution through an external potential V which depends on \(M_V\) tunable parameters (e.g., the amplitude and phase (thus \(M_V = 2\)) of a laser field in the dipolar condition). At instants \(t_n\), these parameters can be rapidly switched to specific values and then kept constant during time intervals \(\Delta t\). The method determines which sets of parameters values can result in \(\langle \varPsi (t) | {\mathcal O} |\varPsi (t) \rangle = S(t)\). It is numerically robust (no intrinsic divergences) and relatively fast since we need to solve only nonlinear algebraic (instead of a system of coupled nonlinear differential) equations to obtain the parameters at the successive \(\Delta t\)’s. For a given S(t), the required minimum \(M_V = M_{\min }\) ‘degrees of freedom’ of V attaining the control is a good figure of merit of the problem difficulty. For instance, the control cannot be unconditionally realizable if \(M_{\min } > 2\) and V is due to a laser field (the usual context in real applications). As it is discussed and exemplified, in these cases a possible procedure is to relax the control in certain problematic (but short) time intervals. Finally, when existing the approach can systematically access distinct possible solutions, thereby allowing a relatively simple way to search for the best implementation conditions. Illustrations for 3-, 4-, and 5-level systems and some comparisons with calculations in the literature are presented.     

Quantum one-way permutation over the finite field of two elements

In quantum cryptography, a one-way permutation is a bounded unitary operator \(U:\mathcal {H} \rightarrow \mathcal {H}\) on a Hilbert space \(\mathcal {H}\) that is easy to compute on every input, but hard to invert given the image of a random input. Levin (Probl Inf Transm 39(1):92–103, 2003) has conjectured that the unitary transformation \(g(a,x)=(a,f(x)+ax)\), where f is any length-preserving function and \(a,x \in \hbox {GF}_{{2}^{\Vert x\Vert }}\), is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin’s one-way permutation is provably secure because its output values are four maximally entangled two-qubit states, and whose probability of factoring them approaches zero faster than the multiplicative inverse of any positive polynomial poly(x) over the Boolean ring of all subsets of x. Our results demonstrate through well-known theorems that existence of classical one-way functions implies existence of a universal quantum one-way permutation that cannot be inverted in subexponential time in the worst case.     

Two Mixed Finite Element Methods for Time-Fractional Diffusion Equations

Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis.     

The panpositionable panconnectedness of crossed cubes

In many parallel and distributed multiprocessor systems, the processors are connected based on different types of interconnection networks. The topological structure of an interconnection network is typically modeled as a graph. Among the many kinds of network topologies, the crossed cube is one of the most popular. In this paper, we investigate the panpositionable panconnectedness problem with respect to the crossed cube. A graph G is r-panpositionably panconnected if for any three distinct vertices x, y, z of G and for any integer \(l_1\) satisfying \(r \le l_1 \le |V(G)| - r - 1\), there exists a path \(P = [x, P_1, y, P_2, z]\) in G such that (i) \(P_1\) joins x and y with \(l(P_1) = l_1\) and (ii) \(P_2\) joins y and z with \(l(P_2) = l_2\) for any integer \(l_2\) satisfying \(r \le l_2 \le |V(G)| - l_1 - 1\), where |V(G)| is the total number of vertices in G and \(l(P_1)\) (respectively, \(l(P_2)\)) is the length of path \(P_1\) (respectively, \(P_2\)). By mathematical induction, we demonstrate that the n-dimensional crossed cube \(CQ_n\) is n-panpositionably panconnected. This result indicates that the path embedding of joining x and z with a mediate vertex y in \(CQ_n\) is extremely flexible. Moreover, applying our result, crossed cube problems such as panpositionable pancyclicity, panpositionably Hamiltonian connectedness, and panpositionable Hamiltonicity can be solved.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.