Search

In many fault-detection problems, its objective lies in discerning all the defective items from a set of $n$ items with a binary characteristic by utilizing the minimum number of tests. Group testing (i.e., testing a subset of items with a single test) plays a pivotal role in classifying a large population of items. We study a central problem in the combinatorial group testing model for the situation where the number $d$ of defectives is unknown in advance. Let $M(d,n)=\min_{\alpha}M_\alpha(d|n)$, where $M_\alpha(d|n)$ is the maximum number of tests required by an algorithm $\alpha$ for the problem. An algorithm $\alpha$ is called a $c$\emph{-competitive algorithm} if there exist constants $c$ and $a$ such that for $0\le d < n$, $M_{\alpha}(d|n)\le cM(d,n)+a$. We design a new adaptive algorithm with competitive constant $c \le 1.431$, thus pushing the competitive ratio below the best-known one of $1.452$. The new algorithm is a novel solution framework based on a strongly competitive algorithm and an up-zig-zag strategy that has not yet been investigated., Comment: 38 pages, 2 figures, uses fullpage.sty

We study entanglement of Kondo clouds in an open triple quantum dots (OTQDs) system based on the dissipaton equation of motion (DEOM) theory. A comprehensive picture of the long-range entanglement of Kondo clouds is sketched by the spectral functions, spin-spin correlation and dot occupancies of OTQDs. We find that for the configuration (N1,N2,N3) = (1, 0, 1), a conduction electrons peak occurs in the spectral function of intermediate QD in Kondo regime. This peak resulting from the overlapping of the two Kondo clouds forming from between the two peripheral QDs and leads, enhances with decreasing temperature and increasing dot-lead coupling. Both the spin-spin correlations between the two adjacent QDs and the two peripheral QDs owns negative values. It also confirms the physical picuture of the overlapping between left and right Kondo clouds via the intermediate QD. Moreover, the transition of the effective electron occupation and the spectral function of intermediate QD in Kondo regime also indicates the entanglement of Kondo clouds enhancing with decreasing temperature and increasing dot-lead coupling. This investigation will be beneficial to detect the Kondo clouds and to further explore Kondo physics in related experiment setups.

We investigate the dynamics of a strongly correlated quantum dot system in the mixed valence regime based on the hierarchical equations of motion (HEOM) approach. The transient and steady state transport properties after a quantum quench from equilibration by rapidly applying a bias voltage in a range of temperature below and above the Kondo temperature are described. We find that the time-dependent current exhibits a linear response behavior for weak bias voltage and outside of the linear response regime for larger bias voltage due to the transition of the voltage dependent quantum dot occupancies. The influence of the temperature, finite strongly correlated electron-electron interaction and energy level of the quantum dot on the nonlinear behavior and steady state values of current indicating the Kondo physics are explored in detail.

Long-range interactions in triple quantum dots (TQDs) in Kondo regime are investigated by accurately solving the three-impurity Anderson model. For the occupation configuration of (N1,N2,N3) = (1, 0, 1), a long-range antiferromagnetic exchange interaction (JAF) is demonstrated and induces a continuous phase transition from the separated Kondo singlet (KS) to the long-range spin singlet (LSS) state between edge dots. The expression of JAF is analytically derived and numerically verified, according to which JAF can be conveniently manipulated via gate control of the detuning energy. The long-range entanglement of Kondo clouds are proved to be quite robust at strong inter-dot coupling limit. Under equilibrium condition, it induces an unexpected peak in the spectral function of the middle dot whose singly occupied level keeps much higher than the Fermi level. Under nonequilibrium condition, higher inter-dot tunneling barrier induces an anomalous enhancement of current. These novel features can be observed in routine experiments., Comment: 7 pages, 5 figures

We investigate the spectral properties of serially coupled triple quantum dot (TQD) system by means of the hierarchical equations of motion (HEOM) approach. We find that with the increase of the interdot coupling t, the first Kondo screening is followed by another Kondo effect reappearing due to the transition from the respective Kondo singlet state of individual QD to the coherence bonding state generated among the three QDs. The reappearance of Kondo effect results in the three-peak structure of the spectral functions of peripheral QD-1(3). By investigating the susceptibility \c{hi}, we find that the local susceptibility of intermediate QD-2 is a positive value at weak interdot coupling, while it changes into negative value at strong interdot coupling, at which the TQD system gives rise to the reappearance of Kondo effect. We also find the slopes of 1/\c{hi} will deviate from straight line behaviour at low temperature in the reappearing Kondo regime. In addition, the influence of temperature T and dot-lead coupling strength {\Delta} on the reappearing Kondo effect as well as the Kondo-correlated transport properties are afterwards exploited in detail., Comment: 8 pages, 4 figures

We investigate the time-dependent transport properties of single and double quantum-impurity systems based on the hierarchical equations of motion (HEOM) approach. In the Kondo regime, the dynamical current in both cases is found oscillating due to the temporal coherence of electrons tunneling through the device, which shares the same mechanism as the single-level resonance without e-e interactions but shows some different characteristics. For single quantum-impurity systems, the temperature T plays an inhibitory action to the oscillations of dynamic current through its suppression to the Kondo effects. The amplitude of the current oscillations is attenuated by the e-e interaction $U$ in the Kondo regime. The frequency of the current oscillation is found almost independent of T and U. For parallel-coupling double quantum-impurity systems, the oscillation of the current shows similar behaviors to the single one, but with two-to-three times larger amplitudes. At the limit of small inter-impurity coupling the oscillation of the current exhibits enhanced characters while it is weakened at the other limit., Comment: 7 pages, 8 figures

An \emph{antimagic labeling} of a finite undirected simple graph with $m$ edges and $n$ vertices is a bijection from the set of edges to the integers $1,...,m$ such that all $n$ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called \emph{antimagic} if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph, but $K_2$, is antimagic. In 2004, N. Alon et al showed that this conjecture is true for $n$-vertex graphs with minimum degree $\Omega(\log n)$. They also proved that complete partite graphs (other than $K_2$) and $n$-vertex graphs with maximum degree at least $n-2$ are antimagic. Recently, Wang showed that the toroidal grids (the Cartesian products of two or more cycles) are antimagic. Two open problems left in Wang's paper are about the antimagicness of lattice grid graphs and prism graphs, which are the Cartesian products of two paths, and of a cycle and a path, respectively. In this article, we prove that these two classes of graphs are antimagic, by constructing such antimagic labelings., Comment: 10 pages, 6 figures

An \emph{antimagic labeling} of a finite undirected simple graph with $m$ edges and $n$ vertices is a bijection from the set of edges to the integers $1,...,m$ such that all $n$ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called \emph{antimagic} if it has an antimagic labeling. In 1990, Hartsfield and Ringel \cite{HaRi} conjectured that every simple connected graph, but $K_2$, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In addition, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in \cite{Wan}, all Cartesian products of two or more regular graphs can be proved to be antimagic., Comment: 10 pages, 2 figures

Suppose $P_n=\{1,2,...,n\}$ is a partially ordered set with the partial order defined by divisibility, that is, for any two distinct elements $i,j\in P_n$ satisfying $i$ divides $j$, $i<_{P_n} j$. A table $A_n=\{a_i|i=1,2,...,n\}$ of distinct real numbers is said to be \emph{consistent} with $P_n$, provided for any two distinct elements $i,j\in \{1,2,...,n\}$ satisfying $i$ divides $j$, $a_i< a_j$. Given an real number $x$, we want to determine whether $x\in A_n$, by comparing $x$ with as few entries of $A_n$ as possible. In this paper we investigate the complexity $\tau(n)$, measured in the number of comparisons, of the above search problem. We present a $\frac{55n}{72}+O(\ln^2 n)$ search algorithm for $A_n$ and prove a lower bound $({3/4}+{17/2160})n+O(1)$ on $\tau(n)$ by using an adversary argument., Comment: 16 pages, no figure; same results, representation improved, add references

In this paper we investigate the problem of searching monotone multi-dimensional arrays. We generalize Linial and Saks' search algorithm \cite{LS1} for monotone 3-dimensional arrays to $d$-dimensions with $d\geq 4$. Our new search algorithm is asymptotically optimal for $d=4$., Comment: 13 pages, 2 figures; same results, presentation improved, add two figures