Efficient parallelizable hashing using small non-compressing primitives

A well-established method of constructing hash functions is to base them on non-compressing primitives, such as one-way functions or permutations. In this work, we present \(S^r\), an \(rn\)-to-\(n\)-bit compression function (for \(r\ge 1\)) making \(2r-1\) calls to \(n\)-to-\(n\)-bit primitives (random functions or permutations). \(S^r\) compresses its inputs at a rate (the amount of message blocks per primitive call) up to almost 1/2, and it outperforms all existing schemes with respect to rate and/or the size of underlying primitives. For instance, instantiated with the \(1600\)-bit permutation of NIST’s SHA-3 hash function standard, it offers about \(800\)-bit security at a rate of almost 1/2, while SHA-3-512 itself achieves only \(512\)-bit security at a rate of about \(1/3\). We prove that \(S^r\) achieves asymptotically optimal collision security against semi-adaptive adversaries up to almost \(2^{n/2}\) queries and that it can be made preimage secure up to \(2^n\) queries using a simple tweak.     

Speed scaling problems with memory/cache consideration

Speed scaling problems consider energy-efficient job scheduling in processors by adjusting the speed to reduce energy consumption, where power consumption is a convex function of speed (usually, \(P(s) =s^{\alpha }, \alpha =2,3\)). In this work, we study speed scaling problems considering memory/cache. Each job needs some time for memory operation when it is fetched from memory,, and needs less time if fetched from the cache. The objective is to minimize energy consumption while satisfying the time constraints of the jobs. Two models are investigated, the non-cache model and the with-cache model. The non-cache model is a variant of the ideal model, where each job i needs a fixed \(c_i\) time for its memory operation; the with-cache model further considers the cache, a memory device with much faster access time but limited space. The uniform with-cache model is a special case of the with-cache model in which all \(c_i\) values are the same. We provide an \(O(n^3)\) time algorithm and an improved \(O(n^2\log n)\) time algorithm to compute the optimal solution in the non-cache model. For the with-cache model, we prove that it is NP-complete to compute the optimal solution. For the uniform with-cache model with agreeable jobs (later-released jobs do not have earlier deadlines), we derive an \(O(n^4)\) time algorithm to compute the optimal schedule, while for the general case we propose a \((2\alpha \frac{g}{g-1})^{\alpha }/2\)-approximation algorithm in a resource augmentation setting in which the memory operation time can accelerate by at most g times.     

Throughput maximization for speed scaling with agreeable deadlines

We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job \(J_j\) is characterized by a processing requirement (work) \(p_j\), a release date \(r_j\), and a deadline \(d_j\). We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in \(O(n^4 \log n \log P)\) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every \(i < j\), it holds that \(r_i \le r_j\) and \(d_i \le d_j\), we propose an optimal dynamic programming algorithm which runs in \(O(n^6 \log n \log P)\) time. In addition, we consider the weighted case where every job \(J_j\) is also associated with a weight \(w_j\) and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes \(\mathcal{NP}\)-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.     

Multilevel quantum Otto heat engines with identical particles

A quantum Otto heat engine is studied with multilevel identical particles trapped in one-dimensional box potential as working substance. The symmetrical wave function for Bosons and the anti-symmetrical wave function for Fermions are considered. In two-particle case, we focus on the ratios of \(W^i\) (\(i=B,F\)) to \(W_s\), where \(W^\mathrm{B}\) and \(W^\mathrm{F}\) are the work done by two Bosons and Fermions, respectively, and \(W_s\) is the work output of a single particle under the same conditions. Due to the symmetrical of the wave functions, the ratios are not equal to 2. Three different regimes, low-temperature regime, high-temperature regime, and intermediate-temperature regime, are analyzed, and the effects of energy level number and the differences between the two baths are calculated. In the multiparticle case, we calculate the ratios of \(W^i_M/M\) to \(W_s\), where \(W^i_M/M\) can be seen as the average work done by a single particle in multiparticle heat engine. For other working substances whose energy spectrum has the form of \(E_n\sim n^2\), the results are similar. For the case \(E_n\sim n\), two different conclusions are obtained.     

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.     

Good and asymptotically good quantum codes derived from algebraic geometry

In this paper, we construct several new families of quantum codes with good parameters. These new quantum codes are derived from (classical) t-point (\(t\ge 1\)) algebraic geometry (AG) codes by applying the Calderbank–Shor–Steane (CSS) construction. More precisely, we construct two classical AG codes \(C_1\) and \(C_2\) such that \(C_1\subset C_2\), applying after the well-known CSS construction to \(C_1\) and \(C_2\). Many of these new codes have large minimum distances when compared with their code lengths as well as they also have small Singleton defects. As an example, we construct a family \({[[46, 2(t_2 - t_1), d]]}_{25}\) of quantum codes, where \(t_1 , t_2\) are positive integers such that \(1<t_1< t_2 < 23\) and \(d\ge \min \{ 46 - 2t_2 , 2t_1 - 2 \}\), of length \(n=46\), with minimum distance in the range \(2\le d\le 20\), having Singleton defect at most four. Additionally, by applying the CSS construction to sequences of t-point (classical) AG codes constructed in this paper, we generate sequences of asymptotically good quantum codes.     

Fast L1–L2 Minimization via a Proximal Operator

This paper aims to develop new and fast algorithms for recovering a sparse vector from a small number of measurements, which is a fundamental problem in the field of compressive sensing (CS). Currently, CS favors incoherent systems, in which any two measurements are as little correlated as possible. In reality, however, many problems are coherent, and conventional methods such as \(L_1\) minimization do not work well. Recently, the difference of the \(L_1\) and \(L_2\) norms, denoted as \(L_1\)–\(L_2\), is shown to have superior performance over the classic \(L_1\) method, but it is computationally expensive. We derive an analytical solution for the proximal operator of the \(L_1\)–\(L_2\) metric, and it makes some fast \(L_1\) solvers such as forward–backward splitting (FBS) and alternating direction method of multipliers (ADMM) applicable for \(L_1\)–\(L_2\). We describe in details how to incorporate the proximal operator into FBS and ADMM and show that the resulting algorithms are convergent under mild conditions. Both algorithms are shown to be much more efficient than the original implementation of \(L_1\)–\(L_2\) based on a difference-of-convex approach in the numerical experiments.     

Recursive Computation of Logarithmic Derivatives,Ratios, and Products of Spheroidal Harmonics and Modified Bessel Functions and Applications

Spheroidal harmonics and modified Bessel functions have wide applications in scientific and engineering computing. Recursive methods are developed to compute the logarithmic derivatives, ratios, and products of the prolate spheroidal harmonics (\(P_n^m(x)\), \(Q_n^m(x)\), \(n\ge m\ge 0\), \(x>1\)), the oblate spheroidal harmonics (\(P_n^m(ix)\), \(Q_n^m(ix)\), \(n\ge m\ge 0\), \(x>0\)), and the modified Bessel functions (\(I_n(x)\), \(K_n(x)\), \(n\ge 0\), \(x>0\)) in order to avoid direct evaluation of these functions that may easily cause overflow/underflow for high degree/order and for extreme argument. Stability analysis shows the proposed recursive methods are stable for realistic degree/order and argument values. Physical examples in electrostatics are given to validate the recursive methods.     

Hybridized Discontinuous Galerkin Method for Elliptic Interface Problems: Error Estimates Under Low Regularity Assumptions of Solutions

New hybridized discontinuous Galerkin (HDG) methods for the interface problem for elliptic equations are proposed. Unknown functions of our schemes are \(u_h\) in elements and \(\hat{u}_h\) on inter-element edges. That is, we formulate our schemes without introducing the flux variable. We assume that subdomains \(\Omega _1\) and \(\Omega _2\) are polyhedral domains and that the interface \(\Gamma =\partial \Omega _1\cap \partial \Omega _2\) is polyhedral surface or polygon. Moreover, \(\Gamma \) is assumed to be expressed as the union of edges of some elements. We deal with the case where the interface is transversely connected with the boundary of the whole domain \(\overline{\Omega }=\overline{\Omega _1\cap \Omega _2}\). Consequently, the solution u of the interface problem may not have a sufficient regularity, say \(u\in H^2(\Omega )\) or \(u|_{\Omega _1}\in H^2(\Omega _1)\), \(u|_{\Omega _2}\in H^2(\Omega _2)\). We succeed in deriving optimal order error estimates in an HDG norm and the \(L^2\) norm under low regularity assumptions of solutions, say \(u|_{\Omega _1}\in H^{1+s}(\Omega _1)\) and \(u|_{\Omega _2}\in H^{1+s}(\Omega _2)\) for some \(s\in (1/2,1]\), where \(H^{1+s}\) denotes the fractional order Sobolev space. Numerical examples to validate our results are also presented.     

Indistinguishability of pure orthogonal product states by LOCC

We construct two sets of incomplete and extendible quantum pure orthogonal product states (POPS) in general bipartite high-dimensional quantum systems, which are all indistinguishable by local operations and classical communication. The first set of POPS is composed of two parts which are \(\mathcal {C}^m\otimes \mathcal {C}^{n_1}\) with \(5\le m\le n_1\) and \(\mathcal {C}^m\otimes \mathcal {C}^{n_2}\) with \(5\le m \le n_2\), where \(n_1\) is odd and \(n_2\) is even. The second one is in \(\mathcal {C}^m\otimes \mathcal {C}^n\) \((m, n\ge 4)\). Some subsets of these two sets can be extended into complete sets that local indistinguishability can be decided by noncommutativity which quantifies the quantumness of a quantum ensemble. Our study shows quantum nonlocality without entanglement.     

Pure state ‘really’ informationally complete with rank-1 POVM

What is the minimal number of elements in a rank-1 positive operator-valued measure (POVM) which can uniquely determine any pure state in d-dimensional Hilbert space \(\mathcal {H}_d\)? The known result is that the number is no less than \(3d-2\). We show that this lower bound is not tight except for \(d=2\) or 4. Then we give an upper bound \(4d-3\). For \(d=2\), many rank-1 POVMs with four elements can determine any pure states in \(\mathcal {H}_2\). For \(d=3\), we show eight is the minimal number by construction. For \(d=4\), the minimal number is in the set of \(\{10,11,12,13\}\). We show that if this number is greater than 10, an unsettled open problem can be solved that three orthonormal bases cannot distinguish all pure states in \(\mathcal {H}_4\). For any dimension d, we construct \(d+2k-2\) adaptive rank-1 positive operators for the reconstruction of any unknown pure state in \(\mathcal {H}_d\), where \(1\le k \le d\).     

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.     

No nexiste nce of n-qubit u nexte ndible product bases of size $$2^ n-5$$2 n-5

It is known that the n-qubit system has no unextendible product bases (UPBs) of cardinality \(2^n-1\), \(2^n-2\) and \(2^n-3\). On the other hand, the n-qubit UPBs of cardinality \(2^n-4\) exist for all \(n\ge 3\). We prove that they do not exist for cardinality \(2^n-5\).     

The block Lanczos algorithm for linear ill-posed problems

In the present paper, we propose a new method to inexpensively determine a suitable value of the regularization parameter and an associated approximate solution, when solving ill-conditioned linear system of equations with multiple right-hand sides contaminated by errors. The proposed method is based on the symmetric block Lanczos algorithm, in connection with block Gauss quadrature rules to inexpensively approximate matrix-valued function of the form \(W^Tf(A)W\), where \(W\in {\mathbb {R}}^{n\times k}\), \(k\ll n\), and \(A\in {\mathbb {R}}^{n\times n}\) is a symmetric matrix.     

Connecting unextendible maximally entangled base with partial Hadamard matrices

We study the unextendible maximally entangled bases (UMEB) in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\) and connect the problem to the partial Hadamard matrices. We show that for a given special UMEB in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\), there is a partial Hadamard matrix which cannot be extended to a Hadamard matrix in \(\mathbb {C}^{d}\). As a corollary, any \((d-1)\times d\) partial Hadamard matrix can be extended to a Hadamard matrix, which answers a conjecture about \(d=5\). We obtain that for any d there is a UMEB except for \(d=p\ \text {or}\ 2p\), where \(p\equiv 3\mod 4\) and p is a prime. The existence of different kinds of constructions of UMEBs in \(\mathbb {C}^{nd}\bigotimes \mathbb {C}^{nd}\) for any \(n\in \mathbb {N}\) and \(d=3\times 5 \times 7\) is also discussed.     

A Weak Galerkin Method with an Over-Relaxed Stabilization for Low Regularity Elliptic Problems

A new weak Galerkin (WG) finite element method is developed and analyzed for solving second order elliptic problems with low regularity solutions in the Sobolev space \(W^{2,p}(\Omega )\) with \(p\in (1,2)\). A WG stabilizer was introduced by Wang and Ye (Math Comput 83:2101–2126, 2014) for a simpler variational formulation, and it has been commonly used since then in the WG literature. In this work, for the purpose of dealing with low regularity solutions, we propose to generalize the stabilizer of Wang and Ye by introducing a positive relaxation index to the mesh size h. The relaxed stabilization gives rise to a considerable flexibility in treating weak continuity along the interior element edges. When the norm index \(p\in (1,2]\), we strictly derive that the WG error in energy norm has an optimal convergence order \(O(h^{l+1-\frac{1}{p}-\frac{p}{4}})\) by taking the relaxed factor \(\beta =1+\frac{2}{p}-\frac{p}{2}\), and it also has an optimal convergence order \(O(h^{l+2-\frac{2}{p}})\) in \(L^2\) norm when the solution \(u\in W^{l+1,p}\) with \(p\in [1,1+\frac{2}{p}-\frac{p}{2}]\) and \(l\ge 1\). It is recovered for \(p=2\) that with the choice of \(\beta =1\), error estimates in the energy and \(L^2\) norms are optimal for the source term in the sobolev space \(L^2\). Weak variational forms of the WG method give rise to desirable flexibility in enforcing boundary conditions and can be easily implemented without requiring a sufficiently large penalty factor as in the usual discontinuous Galerkin methods. In addition, numerical results illustrate that the proposed WG method with an over-relaxed factor \(\beta (\ge 1)\) converges at optimal algebraic rates for several low regularity elliptic problems.     

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.     

Tight bounds for parallel randomized load balancing

Given a distributed system of \(n\) balls and \(n\) bins, how evenly can we distribute the balls to the bins, minimizing communication? The fastest non-adaptive and symmetric algorithm achieving a constant maximum bin load requires \(\varTheta (\log \log n)\) rounds, and any such algorithm running for \(r\in {\mathcal {O}}(1)\) rounds incurs a bin load of \(\varOmega ((\log n/\log \log n)^{1/r})\). In this work, we explore the fundamental limits of the general problem. We present a simple adaptive symmetric algorithm that achieves a bin load of 2 in \(\log ^* n+{\mathcal {O}}(1)\) communication rounds using \({\mathcal {O}}(n)\) messages in total. Our main result, however, is a matching lower bound of \((1-o(1))\log ^* n\) on the time complexity of symmetric algorithms that guarantee small bin loads. The essential preconditions of the proof are (i) a limit of \({\mathcal {O}}(n)\) on the total number of messages sent by the algorithm and (ii) anonymity of bins, i.e., the port numberings of balls need not be globally consistent. In order to show that our technique yields indeed tight bounds, we provide for each assumption an algorithm violating it, in turn achieving a constant maximum bin load in constant time.     

An EMG-marker tracking optimisation method for estimating muscle forces

Existing algorithms for estimating muscle forces mainly use least-activation criteria, which do not necessarily lead to physiologically consistent results. Our objective was to assess an innovative forward dynamics-based optimisation, assisted by both electromyography (EMG) and marker tracking, for estimating the upper-limb muscle forces. A reference movement was generated, and EMG was simulated to reproduce the desired joint kinematics. Random noise was added to both simulated EMG and marker trajectories in order to create 30 trials. Then, muscle forces were estimated using (1) the innovative EMG-marker tracking forward optimisation, (2) a marker tracking forward optimisation with a least-excitation criterion, and (3) static optimisation with a least-activation criterion. Approaches (1) and (2) were solved using a direct multiple shooting algorithm. Finally, reference and estimated joint angles and muscle forces for the three optimisations were statistically compared using root-mean-square errors (RMSEs), biases, and statistical parametric mapping. The joint angles RMSEs were qualitatively similar across the three optimisations: (1) \(1.63 \pm 0.51\)°; (2) \(2.02 \pm 0.64\)°; (3) \(0.79 \pm 0.38\)°. However, the muscle forces RMSE for the EMG-marker tracking optimisation (\(20.39 \pm 13.24\) N) was about seven times smaller than those resulting from the marker tracking (\(124.22 \pm 118.22\) N) and static (\(148.15 \pm 94.01\) N) optimisations. The originality of this novel approach is close tracking of both simulated EMG and marker trajectories in the same objective function, using forward dynamics. Therefore, the presented EMG-marker tracking optimisation led to accurate muscle forces estimations.