A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines,small looseness,and small slack

We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\), a deadline \(d_j\), and a processing time \(p_j\), on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \(|d_j-t_j|\le \lambda {}p_j\) and \(|d_j-t_j|\le p_j +\sigma \) and showed the problem to be NP-hard for any \(\lambda >1\) and for any \(\sigma \ge 2\). We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\), the problem remains weakly NP-hard even for \(m=2\) and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and \(\lambda \) and a fixed-parameter tractability result for the parameter m combined with \(\sigma \).     

Reverse Public Announcement Operators on Expanded Models

Past public announcement operators have been defined in Hoshi and Yap (Synthese 169(2):259–281, 2009) and Yap (Dynamic logic montréal, 2007), to describe an agent’s knowledge before an announcement occurs. These operators rely on branching-time structures that do not mirror the traditional, relativization-based semantics of public announcement logic (PAL), and favor a historical reading of past announcements. In this paper, we introduce reverse public announcement operators that are interpreted on expanded models. Our model expansion adds accessibility links from an epistemic model \(\mathcal {M}\) to a filtrated submodel of the canonical model for \(\mathbf K _g\). Here \(\mathbf K _g\) is the minimal normal modal logic together with \(\mathbf S5 \) axioms for the universal operator U. This yields a highly general pre-announcement version of \(\mathcal {M}\) that makes our operators potentially useful for studying non-standard interpretations of rescinded announcements in PAL. Indeed, we find that our reverse announcement operators cannot be represented by product update, and that they have an intimate connection with the knowledge forgetting of Zhang and Zhou (Artif Intell J 173(16–17):1525–1537, 2009). We show that the logic resulting from adding reverse announcements to PAL is sound and complete.     

Master Lovas–Andai and equivalent formulas verifying the $$\frac{8}{33}$$ two-qubit Hilbert–Schmidt separability probability and companion rational-valued conjectures

We begin by investigating relationships between two forms of Hilbert–Schmidt two-rebit and two-qubit “separability functions”—those recently advanced by Lovas and Andai (J Phys A Math Theor 50(29):295303, 2017), and those earlier presented by Slater (J Phys A 40(47):14279, 2007). In the Lovas–Andai framework, the independent variable \(\varepsilon \in [0,1]\) is the ratio \(\sigma (V)\) of the singular values of the \(2 \times 2\) matrix \(V=D_2^{1/2} D_1^{-1/2}\) formed from the two \(2 \times 2\) diagonal blocks (\(D_1, D_2\)) of a \(4 \times 4\) density matrix \(D= \left||\rho _{ij}\right||\). In the Slater setting, the independent variable \(\mu \) is the diagonal-entry ratio \(\sqrt{\frac{\rho _{11} \rho _ {44}}{\rho _ {22} \rho _ {33}}}\)—with, of central importance, \(\mu =\varepsilon \) or \(\mu =\frac{1}{\varepsilon }\) when both \(D_1\) and \(D_2\) are themselves diagonal. Lovas and Andai established that their two-rebit “separability function” \(\tilde{\chi }_1 (\varepsilon )\) (\(\approx \varepsilon \)) yields the previously conjectured Hilbert–Schmidt separability probability of \(\frac{29}{64}\). We are able, in the Slater framework (using cylindrical algebraic decompositions [CAD] to enforce positivity constraints), to reproduce this result. Further, we newly find its two-qubit, two-quater[nionic]-bit and “two-octo[nionic]-bit” counterparts, \(\tilde{\chi _2}(\varepsilon ) =\frac{1}{3} \varepsilon ^2 \left( 4-\varepsilon ^2\right) \), \(\tilde{\chi _4}(\varepsilon ) =\frac{1}{35} \varepsilon ^4 \left( 15 \varepsilon ^4-64 \varepsilon ^2+84\right) \) and \(\tilde{\chi _8} (\varepsilon )= \frac{1}{1287}\varepsilon ^8 \left( 1155 \varepsilon ^8-7680 \varepsilon ^6+20160 \varepsilon ^4-25088 \varepsilon ^2+12740\right) \). These immediately lead to predictions of Hilbert–Schmidt separability/PPT-probabilities of \(\frac{8}{33}\), \(\frac{26}{323}\) and \(\frac{44482}{4091349}\), in full agreement with those of the “concise formula” (Slater in J Phys A 46:445302, 2013), and, additionally, of a “specialized induced measure” formula. Then, we find a Lovas–Andai “master formula,” \(\tilde{\chi _d}(\varepsilon )= \frac{\varepsilon ^d \Gamma (d+1)^3 \, _3\tilde{F}_2\left( -\frac{d}{2},\frac{d}{2},d;\frac{d}{2}+1,\frac{3 d}{2}+1;\varepsilon ^2\right) }{\Gamma \left( \frac{d}{2}+1\right) ^2}\), encompassing both even and odd values of d. Remarkably, we are able to obtain the \(\tilde{\chi _d}(\varepsilon )\) formulas, \(d=1,2,4\), applicable to full (9-, 15-, 27-) dimensional sets of density matrices, by analyzing (6-, 9, 15-) dimensional sets, with not only diagonal \(D_1\) and \(D_2\), but also an additional pair of nullified entries. Nullification of a further pair still leads to X-matrices, for which a distinctly different, simple Dyson-index phenomenon is noted. C. Koutschan, then, using his HolonomicFunctions program, develops an order-4 recurrence satisfied by the predictions of the several formulas, establishing their equivalence. A two-qubit separability probability of \(1-\frac{256}{27 \pi ^2}\) is obtained based on the operator monotone function \(\sqrt{x}\), with the use of \(\tilde{\chi _2}(\varepsilon )\).     

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.     

Quantum phase transition,quantum fidelity and fidelity susceptibility in the Yang–Baxter system

In this paper, we investigate the ground-state fidelity and fidelity susceptibility in the many-body Yang–Baxter system and analyze their connections with quantum phase transition. The Yang–Baxter system was perturbed by a twist of \( e^{i\varphi } \) at each bond, where the parameter \( \varphi \) originates from the q-deformation of the braiding operator U with \(q = e^{-i\varphi }\) (Jimbo in Yang–Baxter equations in integrable systems, World Scientific, Singapore, 1990), and \( \varphi \) has a physical significance of magnetic flux (Badurek et al. in Phys. Rev. D 14:1177, 1976). We test the ground-state fidelity related by a small parameter variation \(\varphi \) which is a different term from the one used for driving the system toward a quantum phase transition. It shows that ground-state fidelity develops a sharp drop at the transition. The drop gets sharper as system size N increases. It has been verified that a sufficiently small value of \(\varphi \) used has no effect on the location of the critical point, but affects the value of \( F(g_{c},\varphi ) \). The smaller the twist \(\varphi \), the more the value of \( F(g_{c},\varphi ) \) is close to 0. In order to avoid the effect of the finite value of \( \varphi \), we also calculate the fidelity susceptibility. Our results demonstrate that in the Yang–Baxter system, the quantum phase transition can be well characterized by the ground-state fidelity and fidelity susceptibility in a special way.     

Counter machines and crystallographic structures

One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages \(\mathcal {DCL}_d,\,d=0,1,2,\ldots \), within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class \(\mathcal {DCL}_d\). An intersection of d languages in \(\mathcal {DCL}_1\) defines \(\mathcal {DCL}_d\). We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in \(\mathcal {DCL}_d\). The proof uses the following result: given a digraph \(\Delta \) and a group G, there is a unique digraph \(\Gamma \) such that \(G\le \mathrm{Aut}\,\Gamma ,\,G\) acts freely on the structure, and \(\Gamma /G \cong \Delta \).     

Decoupled,Unconditionally Stable,Higher Order Discretizations for MHD Flow Simulation

We propose, analyze, and test a new MHD discretization which decouples the system into two Oseen problems at each timestep yet maintains unconditional stability with respect to the time step size, is optimally accurate in space, and behaves like second order in time in practice. The proposed method chooses a parameter \(\theta \in [0,1]\), dependent on the viscosity \(\nu \) and magnetic diffusivity \(\nu _m\), so that the explicit treatment of certain viscous terms does not cause instabilities, and gives temporal accuracy \(O(\Delta t^2 + (1-\theta )|\nu -\nu _m|\Delta t)\). In practice, \(\nu \) and \(\nu _m\) are small, and so the method behaves like second order. When \(\theta =1\), the method reduces to a linearized BDF2 method, but it has been proven by Li and Trenchea that such a method is stable only in the uncommon case of \(\frac{1}{2}< \frac{\nu }{\nu _m} < 2\). For the proposed method, stability and convergence are rigorously proven for appropriately chosen \(\theta \), and several numerical tests are provided that confirm the theory and show the method provides excellent accuracy in cases where usual BDF2 is unstable.     

On the Distribution of Photon Counts with Censoring in Two-Photon Laser Scanning Microscopy

We address the problem of counting emitted photons in two-photon laser scanning microscopy. Following a laser pulse, photons are emitted after exponentially distributed waiting times. Modeling the counting process is of interest because photon detectors have a dead period after a photon is detected that leads to an underestimate of the count of emitted photons. We describe a model which has a Poisson \((\alpha )\) number N of photons emitted, and a dead period \(\Delta \) that is standardized by the fluorescence time constant \(\tau (\delta = \Delta /\tau )\), and an observed count D. The estimate of \(\alpha \) determines the intensity of a single pixel in an image. We first derive the distribution of D and study its properties. We then use it to estimate \(\alpha \) and \(\delta \) simultaneously by maximum likelihood. We show that our results improve the signal-to-noise ratio, hence the quality of actual images.     

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.     

Explicit and Implicit TVD Schemes for Conservation Laws with Caputo Derivatives

In this paper, we investigate numerical approximations of the scalar conservation law with the Caputo derivative, which introduces the memory effect. We construct the first order and the second order explicit upwind schemes for such equations, which are shown to be conditionally \(\ell ^1\) contracting and TVD. However, the Caputo derivative leads to the modified CFL-type stability condition, \( (\Delta t)^{\alpha } = O(\Delta x)\), where \(\alpha \in (0,1]\) is the fractional exponent in the derivative. When \(\alpha \) is small, such strong constraint makes the numerical implementation extremely impractical. We have then proposed the implicit upwind scheme to overcome this issue, which is proved to be unconditionally \(\ell ^1\) contracting and TVD. Various numerical tests are presented to validate the properties of the methods and provide more numerical evidence in interpreting the memory effect in conservation laws.     

A note on double lacunary statistical $$\sigma$$-convergence of fuzzy numbers

Quite recently, Sava? (Appl Math Lett 21:134–141, 2008), defined the lacunary statistical analogue for double sequence \(X=\{X_{k,l}\}\) of fuzzy numbers as follows: a double sequence \(X=\{X_{k,l}\}\) is said to be lacunary P-statistically convergent to \(X_{0}\) provided that for each \(\epsilon >0\)

$ P-\lim_{r,s}\frac{1}{h_{r,s}}\left | \{(k,l)\in I_{r,s}: d(X_{k,l },X_0)\geq \epsilon\}\right|= 0. $

In this paper we introduce and study double lacunary \(\sigma\)-statistical convergence for sequence of fuzzy numbers and also we get some inclusion theorems.

     

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).     

WSGD-OSC Scheme for Two-Dimensional Distributed Order Fractional Reaction–Diffusion Equation

In this paper, a new numerical approximation is discussed for the two-dimensional distributed-order time fractional reaction–diffusion equation. Combining with the idea of weighted and shifted Grünwald difference (WSGD) approximation (Tian et al. in Math Comput 84:1703–1727, 2015; Wang and Vong in J Comput Phys 277:1–15, 2014) in time, we establish orthogonal spline collocation (OSC) method in space. A detailed analysis shows that the proposed scheme is unconditionally stable and convergent with the convergence order \(\mathscr {O}(\tau ^2+\Delta \alpha ^2+h^{r+1})\), where \(\tau , \Delta \alpha , h\) and r are, respectively the time step size, step size in distributed-order variable, space step size, and polynomial degree of space. Interestingly, we prove that the proposed WSGD-OSC scheme converges with the second-order in time, where OSC schemes proposed previously (Fairweather et al. in J Sci Comput 65:1217–1239, 2015; Yang et al. in J Comput Phys 256:824–837, 2014) can at most achieve temporal accuracy of order which depends on the order of fractional derivatives in the equations and is usually less than two. Some numerical results are also given to confirm our theoretical prediction.     

Minimum-Perimeter Intersecting Polygons

Given a set \(\mathcal{S}\) of segments in the plane, a polygon P is an intersecting polygon of \(\mathcal{S}\) if every segment in \(\mathcal{S}\) intersects the interior or the boundary of P. The problem MPIP of computing a minimum-perimeter intersecting polygon of a given set of n segments in the plane was first considered by Rappaport in 1995. This problem is not known to be polynomial, nor it is known to be NP-hard. Rappaport (Int. J. Comput. Geom. Appl. 5:243–265, 1995) gave an exponential-time exact algorithm for MPIP. Hassanzadeh and Rappaport (Proceedings of the 23rd International Workshop on Algorithms and Data Structures, LNCS, vol. 5664, pp. 363–374, 2009) gave a polynomial-time approximation algorithm with ratio \(\frac{\pi}{2} \approx 1.57\). In this paper, we present two improved approximation algorithms for MPIP: a 1.28-approximation algorithm by linear programming, and a polynomial-time approximation scheme by discretization and enumeration. Our algorithms can be generalized for computing an approximate minimum-perimeter intersecting polygon of a set of convex polygons in the plane. From the other direction, we show that computing a minimum-perimeter intersecting polygon of a set of (not necessarily convex) simple polygons is NP-hard.     

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\).     

Local distinguishability of generalized Bell states

We investigate the distinguishability of orthogonal generalized Bell states (GBSs) in \(d\otimes d\) system by local operations and classical communication (LOCC), where d is a prime. We show that |S| is no more than \(d+1\) for any l GBSs, i.e., \(|S|\le d+1\), where S is maximal set which is composed of pairwise noncommuting pairs in \({\varDelta } U\). If \(|S|\le d\), then the l GBSs can be distinguished by LOCC according to our main Theorem. Compared with the results (Fan in Phys Rev Lett 92:177905, 2004; Tian et al. in Phys Rev A 92:042320, 2015), our result is more general. It can determine local distinguishability of \(l (> k)\) GBSs, where k is the number of GBSs in Fan’s and Tian’s results. Only for \(|S|=d+1\), we do not find the answer. We conjecture that any l GBSs cannot be distinguished by one-way LOCC if \(|S|=d+1\). If this conjecture is right, the problem about distinguishability of GBSs with one-way LOCC is completely solved in \(d\otimes d\).     

Optimal noise functions for location privacy on continuous regions

Users of location-based services are highly vulnerable to privacy risks since they need to disclose, at least partially, their locations to benefit from these services. One possibility to limit these risks is to obfuscate the location of a user by adding random noise drawn from a noise function. In this paper, we require the noise functions to satisfy a generic location privacy notion called \(\ell \)-privacy, which makes the position of the user in a given region \(\mathcal {X}\) relatively indistinguishable from other points in \(\mathcal {X}\). We also aim at minimizing the loss in the service utility due to such obfuscation. While existing optimization frameworks regard the region \(\mathcal {X}\) restrictively as a finite set of points, we consider the more realistic case in which the region is rather continuous with a nonzero area. In this situation, we demonstrate that circular noise functions are enough to satisfy \(\ell \)-privacy on \(\mathcal {X}\) and equivalently on the entire space without any penalty in the utility. Afterward, we describe a large parametric space of noise functions that satisfy \(\ell \)-privacy on \(\mathcal {X}\), and show that this space has always an optimal member, regardless of \(\ell \) and \(\mathcal {X}\). We also investigate the recent notion of \(\epsilon \)-geo-indistinguishability as an instance of \(\ell \)-privacy and prove in this case that with respect to any increasing loss function, the planar Laplace noise function is optimal for any region having a nonzero area.     

Monogamy and polygamy for multi-qubit W-class states using convex-roof extended negativity of assistance and Rényi-$$\alpha $$ entropy

We present some new analytical polygamy inequalities satisfied by the x-th power of convex-roof extended negativity of assistance with \(x\ge 2\) and \(x\le 0\) for multi-qubit generalized W-class states. Using Rényi-\(\alpha \) entropy (R\(\alpha \)E) with \(\alpha \in [(\sqrt{7}-1)/2, (\sqrt{13}-1)/2]\), we prove new monogamy and polygamy relations. We further show that the monogamy inequality also holds for the \(\mu \)th power of Rényi-\(\alpha \) entanglement. Moreover, we study two examples in multipartite higher-dimensional system for those new inequalities.