Automatic Task-Based Code Generation for High Performance Domain Specific Embedded Language

Providing high level tools for parallel programming while sustaining a high level of performance has been a challenge that techniques like Domain Specific Embedded Languages try to solve. In previous works, we investigated the design of such a DSEL—NT\(^2\)—providing a Matlab -like syntax for parallel numerical computations inside a C++ library. In this paper, we show how NT\(^2\!\) has been redesigned for shared memory systems in an extensible and portable way. The new NT\(^2\!\) design relies on a tiered Parallel Skeleton system built using asynchronous task management and automatic compile-time taskification of user level code. We describe how this system can operate various shared memory runtimes and evaluate the design by using two benchmarks implementing linear algebra algorithms.     

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

Verification of $${{EB}^3}$$ specifications using CADP

\({{\small {EB}}^3}\) is a specification language for information systems. The core of the \({{\small {EB}}^3}\) language consists of process algebraic specifications describing the behaviour of the entities in a system, and attribute function definitions describing the entity attributes. The verification of \({{\small {EB}}^3}\) specifications against temporal properties is of great interest to users of \({{\small {EB}}^3}\). In this paper, we propose a translation from \({{\small {EB}}^3}\) to LOTOS NT (LNT for short), a value-passing concurrent language with classical process algebra features. Our translation ensures the one-to-one correspondence between states and transitions of the labelled transition systems corresponding to the \({{\small {EB}}^3}\) and LNT specifications. We automated this translation with the \({{{\small {EB}}^3}2{\small {LNT}}}\) tool, thus equipping the \({{\small {EB}}^3}\) method with the functional verification features available in the CADP toolbox.     

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

Subspace Learning by $$\ell ^{0}$$-Induced Sparsity

Subspace clustering methods partition the data that lie in or close to a union of subspaces in accordance with the subspace structure. Such methods with sparsity prior, such as sparse subspace clustering (SSC) (Elhamifar and Vidal in IEEE Trans Pattern Anal Mach Intell 35(11):2765–2781, 2013) with the sparsity induced by the \(\ell ^{1}\)-norm, are demonstrated to be effective in subspace clustering. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. However, these assumptions are not guaranteed to hold in practice and they limit the application of existing sparse subspace clustering methods. In this paper, we propose \(\ell ^{0}\)-induced sparse subspace clustering (\(\ell ^{0}\)-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that \(\ell ^{0}\)-SSC guarantees the subspace-sparse representation, a key element in subspace clustering, for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We also present the “no free lunch” theorem which shows that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding \(\ell ^{0}\) sparse representation problem of \(\ell ^{0}\)-SSC. A novel approximate algorithm named Approximate \(\ell ^{0}\)-SSC (A\(\ell ^{0}\)-SSC) is developed which employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of \(\ell ^{0}\)-SSC with theoretical guarantee. The sub-optimal solution is used to build a sparse similarity matrix upon which spectral clustering is performed for the final clustering results. Extensive experimental results on various data sets demonstrate the superiority of A\(\ell ^{0}\)-SSC compared to other competing clustering methods. Furthermore, we extend \(\ell ^{0}\)-SSC to semi-supervised learning by performing label propagation on the sparse similarity matrix learnt by A\(\ell ^{0}\)-SSC and demonstrate the effectiveness of the resultant semi-supervised learning method termed \(\ell ^{0}\)-sparse subspace label propagation (\(\ell ^{0}\)-SSLP).     

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.     

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.     

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

An optimal discrimination of two mixed qubit states with a fixed rate of inconclusive results

In this paper we consider the optimal discrimination of two mixed qubit states for a measurement that allows a fixed rate of inconclusive results. Our strategy is to transform the problem of two qubit states into a minimum error discrimination for three qubit states by adding a specific quantum state \(\rho _{0}\) and a prior probability \(q_{0}\), which behaves as an inconclusive degree. First, we introduce the beginning and the end of practical interval of inconclusive result, \(q_{0}^{(0)}\) and \(q_{0}^{(1)}\), which are key ingredients in investigating our problem. Then we obtain the analytic form of them. Next, we show that our problem can be classified into two cases \(q_{0}=q_{0}^{(0)}\) (or \(q_{0}=q_{0}^{(1)}\)) and \(q_{0}^{(0)}<q_{0}<q_{0}^{(1)}\). In fact, by maximum confidences of two qubit states and non-diagonal element of \(\rho _{0}\), our problem is completely understood. We provide an analytic solution of our problem when \(q_{0}=q_{0}^{(0)}\) (or \(q_{0}=q_{0}^{(1)}\)). However, when \(q_{0}^{(0)}<q_{0}<q_{0}^{(1)}\), we rather supply the numerical method to find the solution, because of the complex relation between inconclusive degree and corresponding failure probability. Finally we confirm our results using previously known examples.     

Extremal properties of conditional entropy and quantum discord for XXZ,symmetric quantum states

For the XXZ subclass of symmetric two-qubit X states, we study the behavior of quantum conditional entropy \(S_{cond}\) as a function of measurement angle \(\theta \in [0,\pi /2]\). Numerical calculations show that the function \(S_{cond}(\theta )\) for X states can have at most one local extremum in the open interval from zero to \(\pi /2\) (unimodality property). If the extremum is a minimum, the quantum discord displays region with variable (state-dependent) optimal measurement angle \(\theta ^*\). Such \(\theta \)-regions (phases, fractions) are very tiny in the space of X-state parameters. We also discover the cases when the conditional entropy has a local maximum inside the interval \((0,\pi /2)\). It is remarkable that the maxima exist in surprisingly wide regions, and the boundaries for such regions are defined by the same bifurcation conditions as for those with a minimum.     

Unextendible maximally entangled bases in $${\mathbb {C}}^{pd}\otimes {\mathbb {C}}^{qd}$$

The construction of unextendible maximally entangled bases is tightly related to quantum information processing like local state discrimination. We put forward two constructions of UMEBs in \({\mathbb {C}}^{pd}\otimes {\mathbb {C}}^{qd}\)(\(p\le q\)) based on the constructions of UMEBs in \({\mathbb {C}}^{d}\otimes {\mathbb {C}}^{d}\) and in \({\mathbb {C}}^{p}\otimes {\mathbb {C}}^{q}\), which generalizes the results in Guo (Phys Rev A 94:052302, 2016) by two approaches. Two different 48-member UMEBs in \({\mathbb {C}}^{6}\otimes {\mathbb {C}}^{9}\) have been constructed in detail.     

Validation of right coronary artery lumen area from cardiac computed tomography against intravascular ultrasound

Quantification of coronary artery disease (CAD) from cardiac computed tomography angiography (CTA) is important both structurally (lumen area stenosis) and functionally (combined with computational fluid dynamics to determine fractional flow reserve) for assessment of ischemic stenosis and to guide treatment. Hence, it is important to have CTA image processing technique for segmentation and reconstruction of coronary arteries. In this study, we developed segmentation and reconstruction techniques, based on fast marching and Runge–Kutta methods for centerline extraction, and surface mesh generation. The accuracy of the reconstructed models was validated with direct intravascular ultrasound (IVUS) measurements in 1950 cross sections within 4 arteries. High correlation was found between CTA and IVUS measurements for lumen areas (\(r=0.993\), \(p<0.001\)). Receiver-operating characteristic (ROC) curves showed excellent accuracies for detection of different cutoff values of cross-lumen area (5 \(\text {mm}^2\), 6 \(\text {mm}^2\), 7 \(\text {mm}^2\) and 8 \(\text {mm}^2\), all ROC values >0.99). We conclude that our technique has sufficient accuracy for quantifying coronary lumen area. The accuracy and efficiency demonstrated that our approach can facilitate quantitative evaluation of coronary stenosis and potentially help in real-time assessment of CAD.     

Optimization in e-commerce market network based on value order parameter

This paper aims to provide a new perspective of optimization in a “scale invariant” e-commerce market network. It attempts to do so by building an optimization model based on self-organization theory and complex network. In order to investigate another path leading to some specific structures, order parameter—systemic value, a tradeoff between total cost and efficiency, is the critical optimization constraint. Simulation results reveal a strong correlation between some specific structures of e-commerce market network and order parameter. There are four key insightful findings. First, during the variation of tradeoff coefficient λ from 0 to 1, there are 3 main phases separated by 2 transitions at \( \lambda_{1}^{*} \approx 0.3 \) and \( \lambda_{2}^{*} \approx 0.7 \) which are so-called self-organization critical points. When \( \lambda \in [\lambda_{1}^{*} ,\lambda_{2}^{*} ] \), ordered macrostructure will emerge and the optimization results are more valuable. Second, we find that the system order and systemic value are essentially the same, and optimization of network structure improves the capacity of holding energy, and converts it to systemic value. Third, during the optimization of an initial random network, as cost is decreased, several typical network topology structures emerge. Finally, during the optimization against t with λ = 0.5, we find that there are also 3 phases separated by 2 transitions, and network topology changes.     

Unconditional Superconvergence Analysis for Nonlinear Parabolic Equation with $${\textit{EQ}}_1^{rot}$$ Nonconforming Finite Element

Nonlinear parabolic equation is studied with a linearized Galerkin finite element method. First of all, a time-discrete system is established to split the error into two parts which are called the temporal error and the spatial error, respectively. On one hand, a rigorous analysis for the regularity of the time-discrete system is presented based on the proof of the temporal error skillfully. On the other hand, the spatial error is derived \(\tau \)-independently with the above achievements. Then, the superclose result of order \(O(h^2+\tau ^2)\) in broken \(H^1\)-norm is deduced without any restriction of \(\tau \). The two typical characters of the \({\textit{EQ}}_1^{rot}\) nonconforming FE (see Lemma 1 below) play an important role in the procedure of proof. At last, numerical results are provided in the last section to confirm the theoretical analysis. Here, h is the subdivision parameter, and \(\tau \), the time step.     

Mutually unbiased special entangled bases with Schmidt number 2 in $${\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}$$

A way of constructing special entangled basis with fixed Schmidt number 2 (SEB2) in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k\in z^+,3\not \mid k)\) is proposed, and the conditions mutually unbiased SEB2s (MUSEB2s) satisfy are discussed. In addition, a very easy way of constructing MUSEB2s in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k=2^l)\) is presented. We first establish the concrete construction of SEB2 and MUSEB2s in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4}\) and \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{8}\), respectively, and then generalize them into \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k\in z^+,3\not \mid k)\) and display the condition that MUSEB2s satisfy; we also give general form of two MUSEB2s as examples in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k=2^l)\).     

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.     

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

We study the quantum complexity class \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\), which is an affirmative answer to the question posed by Høyer and ?palek. In sharp contrast to the strict hierarchy of the classical complexity classes: \({\mathsf{NC}^{0} \subsetneq \mathsf{AC}^{0} \subsetneq \mathsf{TC}^{0}}\), our result with Høyer and ?palek’s one implies the collapse of the hierarchy of the corresponding quantum ones: \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}=\mathsf{QAC}^\mathsf{0}_\mathsf{f}=\mathsf{QTC}^\mathsf{0}_\mathsf{f}}\). Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) and \({\mathsf{QTC}^\mathsf{0}_\mathsf{f}}\) circuits for implementing the same operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\), there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a \({\mathsf{QNC}^\mathsf{0}_\mathsf{f}}\) circuit with gates for the quantum Fourier transform.     

New asymmetric quantum codes over $$F_{q}$$

Two families of new asymmetric quantum codes are constructed in this paper. The first family is the asymmetric quantum codes with length \(n=q^{m}-1\) over \(F_{q}\), where \(q\ge 5\) is a prime power. The second one is the asymmetric quantum codes with length \(n=3^{m}-1\). These asymmetric quantum codes are derived from the CSS construction and pairs of nested BCH codes. Moreover, let the defining set \(T_{1}=T_{2}^{-q}\), then the real Z-distance of our asymmetric quantum codes are much larger than \(\delta _\mathrm{max}+1\), where \(\delta _\mathrm{max}\) is the maximal designed distance of dual-containing narrow-sense BCH code, and the parameters presented here have better than the ones available in the literature.     

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