
Let $G$ be a graph and let $I = I(G)$ be its edge ideal. When $G$ is
unicyclic, we give a decomposition of symbolic powers of $I$ in terms of its
ordinary powers. This allows us to explicitly compute the Waldschmidt constant,
the resurgence number, and the symbolic defect for $I$. When $G$ is an odd
cycle, we explicitly compute the regularity of $I^{(s)}$ for all $s \in
\mathbb{N}$. In doing so, we also give a natural lower bound for the regularity
function $\text{reg } I^{(s)}$, for $s \in \mathbb{N}$, for an arbitrary graph
$G$.

The experimental test of Bell's inequality is mainly focused on
ClauserHorneShimonyHolt (CHSH) form, which provides a quantitative bound,
while little attention has been pained on the violation of Wigner inequality
(WI). Based on the spin coherent state quantum probability statistics we in the
present paper extend the WI and its violation to arbitrary twospin entangled
states with antiparallel and parallel spinpolarizations. The local part of
density operator gives rise to the WI while the violation is a direct result of
nonlocal interference between two components of the entangled states. The
Wigner measuring outcome correlation denoted by $W$ is always less than or at
most equal to zero for the local realist model ($% W_{lc_{{}}}\leq 0$)
regardless of the specific initial state. On the other hand the violation of\
WI is characterized by any positive value of $W$, which possesses a maximum
violation bound $W_{\max }$ $=1/2$. We conclude that the WI is equally
convenient for the experimental test of violation by the quantum entanglement.

The future of main memory appears to lie in the direction of new technologies
that provide strong capacitytoperformance ratios, but have write operations
that are much more expensive than reads in terms of latency, bandwidth, and
energy. Motivated by this trend, we propose sequential and parallel algorithms
to solve graph connectivity problems using significantly fewer writes than
conventional algorithms. Our primary algorithmic tool is the construction of an
$o(n)$sized "implicit decomposition" of a boundeddegree graph $G$ on $n$
nodes, which combined with readonly access to $G$ enables fast answers to
connectivity and biconnectivity queries on $G$. The construction breaks the
linearwrite "barrier", resulting in costs that are asymptotically lower than
conventional algorithms while adding only a modest cost to querying time. For
general nonsparse graphs on $m$ edges, we also provide the first $o(m)$ writes
and $O(m)$ operations parallel algorithms for connectivity and biconnectivity.
These algorithms provide insight into how applications can efficiently process
computations on large graphs in systems with readwrite asymmetry.

In this paper we describe an algorithm that embeds a graph metric $(V,d_G)$
on an undirected weighted graph $G=(V,E)$ into a distribution of tree metrics
$(T,D_T)$ such that for every pair $u,v\in V$, $d_G(u,v)\leq d_T(u,v)$ and
${\bf{E}}_{T}[d_T(u,v)]\leq O(\log n)\cdot d_G(u,v)$. Such embeddings have
proved highly useful in designing fast approximation algorithms, as many hard
problems on graphs are easy to solve on tree instances. For a graph with $n$
vertices and $m$ edges, our algorithm runs in $O(m\log n)$ time with high
probability, which improves the previous upper bound of $O(m\log^3 n)$ shown by
Mendel et al.\,in 2009.
The key component of our algorithm is a new approximate singlesource
shortestpath algorithm, which implements the priority queue with a new data
structure, the "buckettree structure". The algorithm has three properties: it
only requires linear time in the number of edges in the input graph; the
computed distances have a distance preserving property; and when computing the
shortestpaths to the $k$nearest vertices from the source, it only requires to
visit these vertices and their edge lists. These properties are essential to
guarantee the correctness and the stated time bound.
Using this shortestpath algorithm, we show how to generate an intermediate
structure, the approximate dominance sequences of the input graph, in $O(m \log
n)$ time, and further propose a simple yet efficient algorithm to converted
this sequence to a tree embedding in $O(n\log n)$ time, both with high
probability. Combining the three subroutines gives the stated time bound of the
algorithm.
Then we show that this efficient construction can facilitate some
applications. We proved that FRT trees (the generated tree embedding) are
Ramsey partitions with asymptotically tight bound, so the construction of a
series of distance oracles can be accelerated.

In several emerging technologies for computer memory (main memory), the cost
of reading is significantly cheaper than the cost of writing. Such asymmetry in
memory costs poses a fundamentally different model from the RAM for algorithm
design. In this paper we study lower and upper bounds for various problems
under such asymmetric read and write costs. We consider both the case in which
all but $O(1)$ memory has asymmetric cost, and the case of a small cache of
symmetric memory. We model both cases using the $(M,\omega)$ARAM, in which
there is a small (symmetric) memory of size $M$ and a large unbounded
(asymmetric) memory, both random access, and where reading from the large
memory has unit cost, but writing has cost $\omega\gg 1$.
For FFT and sorting networks we show a lower bound cost of $\Omega(\omega
n\log_{\omega M} n)$, which indicates that it is not possible to achieve
asymptotic improvements with cheaper reads when $\omega$ is bounded by a
polynomial in $M$. Also, there is an asymptotic gap (of $\min(\omega,\log
n)/\log(\omega M)$) between the cost of sorting networks and comparison sorting
in the model. This contrasts with the RAM, and most other models. We also show
a lower bound for computations on an $n\times n$ diamond DAG of $\Omega(\omega
n^2/M)$ cost, which indicates no asymptotic improvement is achievable with fast
reads. However, we show that for the edit distance problem (and related
problems), which would seem to be a diamond DAG, there exists an algorithm with
only $O(\omega n^2/(M\min(\omega^{1/3},M^{1/2})))$ cost. To achieve this we
make use of a "path sketch" technique that is forbidden in a strict DAG
computation. Finally, we show several interesting upper bounds for shortest
path problems, minimum spanning trees, and other problems. A common theme in
many of the upper bounds is to have redundant computation to tradeoff between
reads and writes.

In this paper, we proposed a new approximate heuristic search algorithm:
Cascading A*, which is a twophrase algorithm combining A* and IDA* by a new
concept "envelope ball". The new algorithm CA* is efficient, able to generate
approximate solution and anytime solution, and parallel friendly.

The singlesource shortest path problem (SSSP) with nonnegative edge weights
is a notoriously difficult problem to solve efficiently in parallelit is one
of the graph problems said to suffer from the transitiveclosure bottleneck. In
practice, the $\Delta$stepping algorithm of Meyer and Sanders (J. Algorithms,
2003) often works efficiently but has no known theoretical bounds on general
graphs. The algorithm takes a sequence of steps, each increasing the radius by
a userspecified value $\Delta$. Each step settles the vertices in its annulus
but can take $\Theta(n)$ substeps, each requiring $\Theta(m)$ work ($n$
vertices and $m$ edges).
In this paper, we describe RadiusStepping, an algorithm with the bestknown
tradeoff between work and depth bounds for SSSP with nearlylinear
($\otilde(m)$) work. The algorithm is a $\Delta$steppinglike algorithm but
uses a variable instead of fixedsize increase in radii, allowing us to prove a
bound on the number of steps. In particular, by using what we define as a
vertex $k$radius, each step takes at most $k+2$ substeps. Furthermore, we
define a $(k, \rho)$graph property and show that if an undirected graph has
this property, then the number of steps can be bounded by $O(\frac{n}{\rho}
\log \rho L)$, for a total of $O(\frac{kn}{\rho} \log \rho L)$ substeps, each
parallel. We describe how to preprocess a graph to have this property.
Altogether, RadiusStepping takes $O((m+n\log n)\log \frac{n}{\rho})$ work and
$O(\frac{n}{\rho}\log n \log (\rho{}L))$ depth per source after preprocessing.
The preprocessing step can be done in $O(m\log n + n\rho^2)$ work and
$O(\rho^2)$ depth or in $O(m\log n + n\rho^2\log n)$ work and $O(\rho\log
\rho)$ depth, and adds no more than $O(n\rho)$ edges.

Emerging memory technologies have a significant gap between the cost, both in
time and in energy, of writing to memory versus reading from memory. In this
paper we present models and algorithms that account for this difference, with a
focus on writeefficient sorting algorithms. First, we consider the PRAM model
with asymmetric write cost, and show that sorting can be performed in
$O\left(n\right)$ writes, $O\left(n \log n\right)$ reads, and logarithmic depth
(parallel time). Next, we consider a variant of the External Memory (EM) model
that charges $\omega > 1$ for writing a block of size $B$ to the secondary
memory, and present variants of three EM sorting algorithms (multiway
mergesort, sample sort, and heapsort using buffer trees) that asymptotically
reduce the number of writes over the original algorithms, and perform roughly
$\omega$ block reads for every block write. Finally, we define a variant of the
IdealCache model with asymmetric write costs, and present writeefficient,
cacheoblivious parallel algorithms for sorting, FFTs, and matrix
multiplication. Adapting prior bounds for workstealing and
paralleldepthfirst schedulers to the asymmetric setting, these yield parallel
cache complexity bounds for machines with private caches or with a shared
cache, respectively.

In this paper, we study the problem of moving $n$ sensors on a line to form a
barrier coverage of a specified segment of the line such that the maximum
moving distance of the sensors is minimized. Previously, it was an open
question whether this problem on sensors with arbitrary sensing ranges is
solvable in polynomial time. We settle this open question positively by giving
an $O(n^2 \log n)$ time algorithm. For the special case when all sensors have
the samesize sensing range, the previously best solution takes $O(n^2)$ time.
We present an $O(n \log n)$ time algorithm for this case; further, if all
sensors are initially located on the coverage segment, our algorithm takes
$O(n)$ time. Also, we extend our techniques to the cycle version of the problem
where the barrier coverage is for a simple cycle and the sensors are allowed to
move only along the cycle. For sensors with the samesize sensing range, we
solve the cycle version in $O(n)$ time, improving the previously best $O(n^2)$
time solution.

The PeacemanRachford splitting method is very efficient for minimizing sum
of two functions each depends on its variable, and the constraint is a linear
equality. However, its convergence was not guaranteed without extra
requirements. Very recently, He et al. (SIAM J. Optim. 24: 1011  1040, 2014)
proved the convergence of a strictly contractive PeacemanRachford splitting
method by employing a suitable underdetermined relaxation factor. In this
paper, we further extend the socalled strictly contractive PeacemanRachford
splitting method by using two different relaxation factors, and to make the
method more flexible, we introduce semiproximal terms to the subproblems. We
characterize the relation of these two factors, and show that one factor is
always underdetermined while the other one is allowed to be larger than 1. Such
a flexible conditions makes it possible to cover the Glowinski's ADMM whith
larger stepsize. We show that the proposed modified strictly contractive
PeacemanRachford splitting method is convergent and also prove $O(1/t)$
convergence rate in ergodic and nonergodic sense, respectively. The numerical
tests on an extensive collection of problems demonstrate the efficiency of the
proposed method.

We study quantum chaos in a nonKAM system, i.e. a kicked particle in a
onedimensional infinite square potential well. Within the perturbative regime
the classical phase space displays stochastic web structures, and the diffusion
coefficient D in the regime increases with the perturbative strength K giving a
scaling $D \propto K^{2.5}$, and in the large K regime D goes as K^2. Quantum
mechanically, we observe that the level spacing statistics of the quasi
eigenenergies changes from Poisson to Wigner distribution as the kick strength
increases. The quasi eigenstates show powerlaw localization in the small K
region, which become extended one at large K. Possible experimental realization
of this model is also discussed.