title: Anomalous Diffusion on the Hanoi Networks

abstract:
  Diffusion is modeled on the recently proposed Hanoi networks by studying the
mean- square displacement of random walks with time, <r^2>~t^{2/d_w}. It is
found that diffusion - the quintessential mode of transport throughout Nature -
proceeds faster than ordinary, in one case with an exact, anomalous exponent dw
= 2-log_2(\phi) = 1.30576 . . .. It is an instance of a physical exponent
containing the "golden ratio" \phi=(1+\sqrt{5})/2 that is intimately related to
Fibonacci sequences and since Euclid's time has been found to be fundamental
throughout geometry, architecture, art, and Nature itself. It originates from a
singular renormalization group fixed point with a subtle boundary layer, for
whose resolution \phi is the main protagonist. The origin of this rare
singularity is easily understood in terms of the physics of the process. Yet,
the connection between network geometry and the emergence of \phi in this
context remains elusive. These results provide an accurate test of recently
proposed universal scaling forms for first passage times.


title: Time Varying Undirected Graphs

abstract:
  Undirected graphs are often used to describe high dimensional distributions.
Under sparsity conditions, the graph can be estimated using $\ell_1$
penalization methods. However, current methods assume that the data are
independent and identically distributed. If the distribution, and hence the
graph, evolves over time then the data are not longer identically distributed.
In this paper, we show how to estimate the sequence of graphs for
non-identically distributed data, where the distribution evolves over time.


title:
Specific Heat Study of Magnetic and Superconducting Transitions in
  CePt3Si

abstract:
  Measurements of specific heat between 80 mK to 4 K and electrical resistivity
between 80 mK to 10 K were carried out for polycrystalline CePt3Si samples cut
into small pieces (typically $\sim $10 mg). In the specific heat measurements,
we observed an antiferromagnetic transition jump at TN = 2.2 K for all the
samples, while the heights have large variations. As regards superconductivity,
we observed two distinct transition jumps at Tcl $\sim$ 0.45 K and Tch $\sim$
0.75 K, which were the same for all the samples. From the measurements of
specific heat and resistivity, systematic relations were found between
antiferromagnetic and superconducting transitions. We conclude that
antiferromagnetism, whose transition temperature is 2.2 K, coexists with
superconductivity, whose transition temperature is Tcl. In this sample,
residual electronic specific heat coefficient in the superconducting state
$\gamma_{\rm s}$ was quite small, and specific heat divided by temperature
below Tcl decreased almost linearly with decreasing temperature. In order to
reveal the characteristic properties of the magnetism and superconductivity of
the CePt3Si system, it is important to study the two superconducting phases
with Tcl and Tch, respectively.


title: Multicritical points for the spin glass models on hierarchical lattices

abstract:
  The locations of multicritical points on many hierarchical lattices are
numerically investigated by the renormalization group analysis. The results are
compared with an analytical conjecture derived by using the duality, the gauge
symmetry and the replica method. We find that the conjecture does not give the
exact answer but leads to locations slightly away from the numerically reliable
data. We propose an improved conjecture to give more precise predictions of the
multicritical points than the conventional one. This improvement is inspired by
a new point of view coming from renormalization group and succeeds in deriving
very consistent answers with many numerical data.


title: Quantum thermal transport in nanostructures

abstract:
  In this colloquia review we discuss methods for thermal transport
calculations for nanojunctions connected to two semi-infinite leads served as
heat-baths. Our emphases are on fundamental quantum theory and atomistic
models. We begin with an introduction of the Landauer formula for ballistic
thermal transport and give its derivation from scattering wave point of view.
Several methods (scattering boundary condition, mode-matching, Piccard and
Caroli formulas) of calculating the phonon transmission coefficients are given.
The nonequilibrium Green's function (NEGF) method is reviewed and the Caroli
formula is derived. We also give iterative methods and an algorithm based on a
generalized eigenvalue problem for the calculation of surface Green's
functions, which are starting point for an NEGF calculation. A systematic
exposition for the NEGF method is presented, starting with the fundamental
definitions of the Green's functions, and ending with equations of motion for
the contour ordered Green's functions and Feynman diagrammatic expansion. In
the later part, we discuss the treatments of nonlinear effects in heat
conduction, including a phenomenological expression for the transmission, NEGF
for phonon-phonon interactions, molecular dynamics (generalized Langevin) with
quantum heat-baths, and electron-phonon interactions. Some new results are also
shown. We also briefly review the experimental status of the thermal transport
measurements in nanostructures.


title: Weak decays of $J/\psi$: the non-leptonic case

abstract:
  In our previous study, we calculated the transition from factors of
$J/\psi\to D^{(*)}_{(s)}$ using the QCD sum rules. Based on the factorization
approximation, the obtained form factors can be applied to evaluate the weak
non-leptonic decay rates of $J/\psi\to D^{(*)}_{(s)}+M$, where $M$ stands for a
light pseudoscalar or vector meson. We predict that the branching ratio for
inclusive non-leptonic two-body weak decays of $J/\psi$ which are realized via
the spectator mechanism, can be as large as $1.3 \times 10^{-8}$, in
particular, the branching ratio of $J/\psi\to D^{*\pm}_s+\rho^\mp$ can reach
$5.3 \times 10^{-9}$. Such values will be marginally accessed by the ability of
BESIII which will begin running very soon.


title:
Mechanical mode dependence of bolometric back-action in an AFM
  microlever

abstract:
  Two back action (BA) processes generated by an optical cavity based detection
device can deeply transform the dynamical behavior of an AFM microlever: the
photothermal force or the radiation pressure. Whereas noise damping or
amplifying depends on optical cavity response for radiation pressure BA, we
present experimental results carried out under vacuum and at room temperature
on the photothermal BA process which appears to be more complex. We show for
the first time that it can simultaneously act on two vibration modes in
opposite direction: noise on one mode is amplified whereas it is damped on
another mode. Basic modeling of photothermal BA shows that dynamical effect on
mechanical mode is laser spot position dependent with respect to mode shape.
This analysis accounts for opposite behaviors of different modes as observed.


title:
Energetic neutral atoms as the explanation for the high velocity
  hydrogen around HD 209458b

abstract:
  Absorption in the stellar Lyman-$\alpha$ (Ly-$\alpha$) line observed during
the transit of the extrasolar planet HD 209458b reveals high velocity atomic
hydrogen at great distances from the planet. This has been interpreted as
hydrogen atoms escaping from the exosphere of the planet, possibly undergoing
hydrodynamic blow-off, being accelerated by stellar radiation pressure.
However, around solar system planets the production of energetic neutral atoms
from charge exchange between solar wind protons and neutral hydrogen from the
exospheres has been observed, and should also occur at extrasolar planets. Here
we show that the measured transit-associated Ly-$\alpha$ absorption can be
explained by the interaction between the exosphere of HD 209458b and the
stellar wind, and that radiation pressure alone cannot explain the observation.
This is the first observation of energetic neutral atoms outside the solar
system. Since the stellar wind protons are the source of the observed energetic
neutral atoms, this provides a completely new method of probing stellar wind
conditions, and our model suggests a slow and hot stellar wind near HD 209458b
at the time of the observation.


title:
Soft-phonon-driven superconductivity in CaAlSi as seen by inelastic
  x-ray scattering

abstract:
  Inelastic x-ray scattering and $ab$-$initio$ calculation are applied to
investigate the lattice dynamics and electron-phonon coupling of the ternary
silicide superconductor CaAlSi ($P/bar{6}m2$). A soft c-axis polarized mode is
clearly observed along the $/Gamma$-$A$-$L$ symmetry directions. The soft mode
is strongly anharmonically broadened at room temperature, but, at 10 K, its
linewidth narrows and becomes in good agreement with calculations of linear
electron-phonon coupling. This establishes a coherent description of the
detailed phonon properties in this system and links them clearly and
consistently with the superconductivity.


title: Development of bakelite based Resistive Plate Chambers

abstract:
  A Comparative study has been performed on Resistive Plate Chambers made of
different grades of bakelite paper laminates, produced and commercially
available in India. The chambers, operated in the streamer mode using argon :
tetrafluroethane : isobutane in 34:59:7 mixing ratio, are tested with cosmic
rays for the efficiency and the stability with cosmic rays. A particular grade
of bakelite (P-120, NEMA LI-1989 Grade XXX), used for high voltage insulation
in humid conditions, was found to give satisfactory performance with stable
efficiency of > 96% continuously for more than 110 days. A silicone treatment
of the inner surfaces of the bakelite RPC is found to be necessary for
operation of the detector.


title:
Classification of pairs of rotations in finite-dimensional Euclidean
  space

abstract:
  A rotation in a Euclidean space V is an orthogonal map on V which acts
locally as a plane rotation with some fixed angle. We give a classification of
all pairs of rotations in finite-dimensional Euclidean space, up to
simultaneous conjugation with orthogonal maps.


title:
Robust negative differential conductance and enhanced shot noise in
  transport through a molecular transistor with vibration assistance

abstract:
  In this paper, we analyze vibration-assisted sequential tunneling (including
current-voltage characteristics and zero-frequency shot noise) through a
molecular quantum dot with two electronic orbitals asymmetrically coupled to
the internal vibration. We employ rate equations for the case of equilibrated
phonons, and strong Coulomb blockade. We find that a system with a strongly
phonon-coupled ground state orbital and weakly phonon-coupled excited state
orbital exhibits strong negative differential conductance; and it also shows
super-Poissonian current noise. We discuss in detail the reasons and conditions
for the appearance of negative differential conductance.


title: Skeletons of monomial ideals

abstract:
  In analogy to the skeletons of a simplicial complex and their
Stanley--Reisner ideals we introduce the skeletons of an arbitrary monomial
ideal $I\subset S=K[x_1,...,x_n]$. This allows us to compute the depth of $S/I$
in terms of its skeleton ideals. We apply these techniques to show that
Stanley's conjecture on Stanley decompositions of $S/I$ holds provided it holds
whenever $S/I$ is Cohen--Macaulay. We also discuss a conjecture of
Soleyman-Jahan and show that it suffices to prove his conjecture for monomial
ideals with linear resolution.


title: Distant Radio Galaxies and their Environments

abstract:
  We review the properties and nature of luminous high-redshift radio galaxies
(HzRGs, z > 2) and the environments in which they are located. HzRGs have
several distinct constituents which interact with each other - relativistic
plasma, gas in various forms, dust, stars and an active galactic nucleus (AGN).
These building blocks provide unique diagnostics about conditions in the early
Universe. We discuss the properties of each constituent. Evidence is presented
that HzRGs are massive forming galaxies and the progenitors of brightest
cluster galaxies in the local Universe. HzRGs are located in overdense regions
in the early Universe and are frequently surrounded by protoclusters. We review
the properties and nature of these radio-selected protoclusters. Finally we
consider the potential for future progress in the field during the next few
decades. A compendium of known HzRGs is given in an appendix.


title: Transpose symmetry of the Jones Matrix and topological phases

abstract:
  The transmission Jones matrix of an arbitrary stack of reciprocal plane
parallel plates which has been turned through 180 degrees about an axis in the
plane of the stack is, in an appropriate basis, the transpose of the
transmission matrix of the unturned slab with a change in the sign of the
off-diagonal elements. We prove this convention-free result for the case where
reflection at the interfaces can be ignored and use it to devise an
experimental scheme to separate isotropic and topological phase changes in a
reciprocal optical medium.


title: The Auslander-Reiten translate on monomial quotient rings

abstract:
  For a multidegree t in N^n, E.Miller has defined a category of positively
t-determined modules over the polynomial ring S in n variables. We consider the
Auslander-Reiten translate, Na_t, on the (derived) category of such modules. A
monomial ideal I is positively t-determined if every generator x^a has a \leq
t. We compute the multigraded cohomology- and betti spaces of Na_t^k(S/I) for
every iterate k, and also the S-module structure of these cohomology modules.
This comprehensively generalizes results of Hochster and Gr\"abe on local
cohomology of Stanley-Reisner rings.


title:
Stiffness Analysis of 3-d.o.f. Overconstrained Translational Parallel
  Manipulators

abstract:
  The paper presents a new stiffness modelling method for overconstrained
parallel manipulators, which is applied to 3-d.o.f. translational mechanisms.
It is based on a multidimensional lumped-parameter model that replaces the link
flexibility by localized 6-d.o.f. virtual springs. In contrast to other works,
the method includes a FEA-based link stiffness evaluation and employs a new
solution strategy of the kinetostatic equations, which allows computing the
stiffness matrix for the overconstrained architectures and for the singular
manipulator postures. The advantages of the developed technique are confirmed
by application examples, which deal with comparative stiffness analysis of two
translational parallel manipulators.


title: Eigenvalues estimate for the Neumann problem on bounded domains

abstract:
  In this note, we investigate upper bounds of the Neumann eigenvalue problem
for the Laplacian of a bounded domain (with smooth boundary) in a given
complete (not compact a priori) Riemannian manifold with Ricci bounded below .
For this, we use test functions for the Rayleigh quotient subordinated to a
family of open sets constructed in a general metric way, interesting for
itself. As application, we get upper bounds for the Neumann spectrum which is
clearly in agreement with the Weyl law and which is analogous to Buser's upper
bounds of the spectrum of a closed Riemannian manifold with lower bound on the
Ricci curvature.


title:
Molecular Gas in NUclei of GAlaxies (NUGA): IX. The decoupled bars and
  gas inflow in NGC 2782

abstract:
  We present CO(1-0) and CO(2-1) maps of the starburst/Seyfert 1 galaxy NGC
2782, obtained with the IRAM interferometer. The CO emission is aligned along
the stellar nuclear bar of radius 1 kpc, configured in an elongated structure
with two spiral arms at high pitch angle. At the extremity of the nuclear bar,
the CO changes direction to trace two more extended spiral features at a lower
pitch angle. These are the beginning of two straight dust lanes, which are
aligned parallel to an oval distortion, reminiscent of a primary bar, almost
perpendicular to the nuclear one. The two embedded bars appear in Spitzer IRAC
near-infrared images, and HST color images, although highly obscured by dust in
the latter. We compute the torques exerted by the stellar bars on the gas, and
find systematically negative average torques down to the resolution limit of
the images, providing evidence of gas inflow tantalizingly close to the nucleus
of NGC 2782. The observations are well reproduced by numerical simulations,
including gas dissipation, which predict the secondary bar decoupling, the
formation of an elongated ring at the 1 kpc-radius Inner Lindblad Resonance
(ILR) of the primary bar, and the gas inflow to the ILR of the nuclear bar. The
presence of molecular gas inside the ILR of the primary bar, transported by a
second nuclear bar, is a potential ``smoking gun''; the gas there is certainly
fueling the central starburst, and in a second step could fuel directly the
AGN.


title:
Interaction Properties of the Periodic and Step-like Solutions of the
  Double-Sine-Gordon Equation

abstract:
  The periodic and step-like solutions of the double-Sine-Gordon equation are
investigated, with different initial conditions and for various values of the
potential parameter $\epsilon$. We plot energy and force diagrams, as functions
of the inter-soliton distance for such solutions. This allows us to consider
our system as an interacting many-body system in 1+1 dimension. We therefore
plot state diagrams (pressure vs. average density) for step-like as well as
periodic solutions. Step-like solutions are shown to behave similarly to their
counterparts in the Sine-Gordon system. However, periodic solutions show a
fundamentally different behavior as the parameter $\epsilon$ is increased. We
show that two distinct phases of periodic solutions exist which exhibit
manifestly different behavior. Response functions for these phases are shown to
behave differently, joining at an apparent phase transition point.


title: Propagation of Nonclassical Radiation through a Semiconductor Slab

abstract:
  Based on a microscopic derivation of the emission spectra of a bulk
semiconductor we arrive at a clear physical interpretation of the noise current
operators in macroscopic quantum electrodynamics. This opens the possibility to
study medium effects on nonclassical radiation propagating through an absorbing
or amplifying semiconductor. As an example, the propagation of an incident
squeezed vacuum is analyzed.


title: The time-delay of the gravitationally lensed double quasar UM 673

abstract:
  The paper has been withdrawn because double checking and comparison with
other data sets after the original submission showed that a broken R-band
filter at the Maidanak telescope had affected our quasar monitoring
observations in the years 2004 and 2005. They had led to partially spurious
measurements, hence our original analysis and conclusions are not reliable.


title:
Multiphoton Bloch-Siegert shifts and level-splittings in a three-level
  system

abstract:
  In previous work we studied the spin-boson model in the multiphoton regime,
using a rotation that provides a separation between terms that contribute most
of the level energies away from resonance, and terms responsible for the level
splittings at the anticrossing. Here, we consider a generalization of the
spin-boson model consisting of a three-level system coupled to an oscillator.
We construct a similar rotation and apply it to the more complicated model. We
find that the rotation provides a useful approximation to the energy levels in
the multiphoton region of the new problem. We find that good results can be
obtained for the level splittings at the anticrossings for resonances involving
the lower two levels in regions away from accidental or low-order resonances of
the upper two levels.


title: On pseudo-differential operators on group SU(2)

abstract:
  In this paper we will outline elements of the global calculus of
seudo-differential operators on the group SU(2). This is a part of a more
general approach to pseudo-differential operators on compact Lie groups that
will appear in the forthcoming book by the authors.


title:
Coherent tunneling and quantum coherence oscillations at the atomic
  level

abstract:
  The evolution of the quantum wave packet describing an atom trapped in the
surface-tip junction of the scanning tunneling microscope is investigated by
using the time-dependent Schroedinger equation, and by a quasi-classical
Hamiltonian approach. The estimates concern a Xe atom in a biased double-well
junction potential. The exact treatment shows that quantum coherence
oscillations of the metastable ground state may occur at particular resonant
values of the bias voltage. The effect of decoherence by partial localization
is studied within the quasi-classical frame.


title: Fiber Bundles and Matrix Models

abstract:
  We investigate relationship between a gauge theory on a principal bundle and
that on its base space. In the case where the principal bundle is itself a
group manifold, we also study relations of those gauge theories with a matrix
model obtained by dimensionally reducing them to zero dimensions. First, we
develop the dimensional reduction of Yang-Mills (YM) on the total space to
YM-higgs on the base space for a general principal bundle. Second, we show a
relationship that YM on an SU(2) bundle is equivalent to the theory around a
certain background of YM-higgs on its base space. This is an extension of our
previous work (hep-th/0703021), in which the same relationship concerning a
U(1) bundle is shown. We apply these results to the case of $SU(n+1)$ as the
total space. By dimensionally reducing YM on $SU(n+1)$, we obtain YM-higgs on
$SU(n+1)/SU(n)\simeq S^{2n+1}$ and on $SU(n+1)/(SU(n)\times U(1))\simeq CP^n$
and a matrix model. We show that the theory around each monopole vacuum of
YM-higgs on $CP^n$ is equivalent to the theory around a certain vacuum of the
matrix model in the commutative limit. By combing this with the relationship
concerning a U(1) bundle, we realize YM-higgs on $SU(n+1)/SU(n)\simeq S^{2n+1}$
in the matrix model. We see that the relationship concerning a U(1) bundle can
be interpreted as Buscher's T-duality.


title: Josephson junctions in narrow thin-film strips

abstract:
  We study the field dependence of the maximum supercurrent in narrow edge-type
thin-film Josephson junctions. It is assumed that the junction extends across
thin-film strip of width W that is much less than the Pearl length; the film
thickness is much less than the London penetration depth. We calculate the
maximum supercurrent within nonlocal Josephson electrodynamics, which takes
into account the stray fields affecting tunneling currents. In the case when W
is much less than the thin-film Josephson length, the phase difference along
the junction depends only on the junction geometry and the applied field, but
is independent of the Josephson critical current density, i.e., it is
universal. Zeros of the maximum supercurrent are equidistant only in large
fields (unlike the case of junctions with bulk banks); they are spaced by a
field that is much smaller than the one of bulk junctions. Peaks of the maximum
supercurrent decrease inversely proportional to the square root of the applied
field, i.e., slower than 1/H for the bulk.


title:
On effective actions of non-BPS branes and their higher derivative
  corrections

abstract:
  By calculating various disk level S-matrix elements and studying in details
their momentum expansions, we have extracted some of the couplings in tachyon
DBI action and Wess-Zumino terms of the non-BPS branes, and their higher
derivative corrections. In particular, we have found that there is exact
consistency between field theory and string theory tachyon pole of S-matrix
element of one RR and three tachyons provided that one takes into account the
fact that the tachyon vertex operator in 0 picture to be along the Pauli matrix
$\sigma_1$ whereas the tachyon in -1 picture to be along the $\sigma_2$
direction. This internal CP factors should be included in the tachyon DBI part
of the effective action.


title: Nonlinear Supersymmetric General Relativity and Unity of Nature

abstract:
  The basic idea and some physical implications of nonlinear supersymmetric
general relativity (NLSUSY GR) are discussed, which give new insights into the
origin of mass and the mysterious relations between the cosmology and the low
energy particle physics, e.g. the spontaneous SUSY breaking scale, the
cosmological constant, the (dark) energy density of the universe and the
neutrino mass.

categories: hep-th astro-ph gr-qc hep-ph math-ph math.MP


title: Topological instabilities of spherical vesicles

abstract:
  Within the framework of the Helfrich elastic theory of membranes and of
differential geometry we study the possible instabilities of spherical vesicles
towards double bubbles. We find that not only temperature, but also magnetic
fields can induce topological transformations between spherical vesicles and
double bubbles and provide a phase diagram for the equilibrium shapes.


title:
On the origin of 3 seismic sources in the proton-rich flare of October
  28, 2003

abstract:
  The 3 seismic sources S1, S2 and S3 detected from MDI dopplergrams using the
time-distance diagram technique are presented with the locations, areas and
vertical and horizontal velocities of the visible wave displacements. Within
the datacube of 120 Mm the horizontal velocities and the wave propagation times
slightly vary from source to source. The momenta and start times measured from
the TD diagrams in the sources S1-S3 are compared with those delivered to the
photosphere by different kinds of high energy particles with the parameters
deduced from hard X-ray and $\gamma$-ray emission as well as by the
hydrodynamic shocks caused by these particles. The energetic protons (power
laws combined with quasi-thermal ones, or jets) are shown to deliver momentum
high enough and to form the hydrodynamic shocks deeply in a flaring atmosphere
that allows them to be delivered to the photosphere through much shorter
distances and times. Then the seismic waves observed in the sources S2 and S3
can be explained by the momenta produced by hydrodynamic shocks which are
caused by mixed proton beams and jets occurring nearly simultaneously with the
third burst of hard X-ray (HXR) and $\gamma$-ray emission in the loops with
footpoints in the locations of these sources. The seismic wave in the source
S1, delayed by 4 and 2 minutes from the first and second HXR bursts,
respectively, is likely to be associated with a hydrodynamic shock occurring in
this loop from precipitation of a very powerful and hard electron beam with
higher energy cutoff mixed with quasi-thermal protons generated by either of
these 2 bursts.


title:
Excitation energy map of the high-energy dispersion anomalies in
  cuprates

abstract:
  The anomalous high-energy dispersion of the conductance band in the high-Tc
superconductor Pb-Bi2212 has been extensively mapped by angle-resolved
photoemission (ARPES) as a function of excitation energy in the range from 34
to 116 eV. Two distinctive types of dispersion behavior are observed around 0.6
eV binding energy, which alternate as a function of photon energy. The
continuous transitions observed between the two kinds of behavior near 50, 70,
and 90 eV photon energies allow to exclude the possibility that they originate
from the interplay between the bonding and antibonding bands. The effects of
three-dimensionality can also be excluded as a possible origin of the
excitation energy dependence, as the large period of the alterations is
inconsistent with the lattice constant in this material. We therefore confirm
that the strong photon energy dependence of the high-energy dispersion in
cuprates originates mainly from the photoemission matrix element that
suppresses the photocurrent in the center of the Brillouin zone.


title:
Crossover from directed percolation to mean field behavior in the
  diffusive contact process

abstract:
  Recently Dantas, Oliveira and Stilck [J. Stat. Mech. (2007) P08009] studied
how the one-dimensional diffusive contact process crosses over from the
critical behavior of directed percolation to an effective mean field behaviour
when the diffusion rate is sent to infinity. They showed that this crossover
can be described in terms of a crossover exponent $\phi$, finding the
boundaries 3 <= $\phi$ <= 4 in one spatial dimension. In the present work we
refine and extend this result up to four spatial dimensions by a
field-theoretic calculation and extensive numerical simulations.


title:
Shifted COCG method and its application to double orbital extended
  Hubbard model

abstract:
  We explains the shifted COCG method which can solve a series of the linear
equations generated by numbers of scaler shifts, without time consuming
matrix-vector operations, except at the only one reference energy. This is a
family of the CG method and sharing the robustness and the capability of the
accuracy estimation. Then shifted COCG is quite useful to calculate the Green's
function of the many-electron Hamiltonian which have very large dimension. We
applied it to the double orbital extended Hubbard model with twelve electrons
on the periodic sqrt(8) x sqrt(8) site system, the dimension of the Hamiltonian
equals to 64,128,064, and found the ground state is insulator. We also
explained the crucial points of the shifted COCG algorithm for reducing the
amount of required memory.


title:
In-plane current-voltage characteristics and oscillatory
  Josephson-vortex flow resistance in La-free
  Bi$_{2+x}$Sr$_{2-x}$CuO$_{6+\delta}$ single crystals in high magnetic fields

abstract:
  We have investigated the in-plane $I(V)$ characteristics and the Josephson
vortex flow resistance in high-quality La-free
Bi$_{2+x}$Sr$_{2-x}$CuO$_{6+\delta}$ (Bi2201) single crystals in parallel and
tilted magnetic fields at temperatures down to 40 mK. For parallel magnetic
fields below the resistive upper critical field $H^{*}_{c2}$, the $I(V)$
characteristic obey a power-law with a smooth change with increasing
magnetic-field of the exponent from above 5 down to 1. In contrast to the
double-layer cuprate Bi2212, the observed smooth change suggests that there is
no change in the mechanism of dissipation (no Kosterlitz-Thouless transition)
over the range of temperatures investigated. At small angles between the
applied field and the $ab$-plane, prominent current steps in the $I(V)$
characteristics and periodic oscillations of Josephson-vortex flow resistance
are observed. While the current steps are periodic in the voltage at constant
fields, the voltage position of the steps, together with the flux-flow voltage,
increases nonlinearly with magnetic field. The $ab$-flow resistance oscillates
as a function of field with a constant period over a wide range of magnetic
fields and temperatures. The current steps in the $I(V)$ characteristics and
the flow resistance oscillations can be linked to the motion of Josephson
vortices across layers.


title: Two dimensional Berezin-Li-Yau inequalities with a correction term

abstract:
  We improve the Berezin-Li-Yau inequality in dimension two by adding a
positive correction term to its right-hand side. It is also shown that the
asymptotical behaviour of the correction term is almost optimal. This improves
a previous result by Melas.


title: On Border Basis and Groebner Basis Schemes

abstract:
  Hilbert schemes of zero-dimensional ideals in a polynomial ring can be
covered with suitable affine open subschemes whose construction is achieved
using border bases. Moreover, border bases have proved to be an excellent tool
for describing zero-dimensional ideals when the coefficients are inexact. And
in this situation they show a clear advantage with respect to Groebner bases
which, nevertheless, can also be used in the study of Hilbert schemes, since
they provide tools for constructing suitable stratifications.
  In this paper we compare Groebner basis schemes with border basis schemes. It
is shown that Groebner basis schemes and their associated universal families
can be viewed as weighted projective schemes. A first consequence of our
approach is the proof that all the ideals which define a Groebner basis scheme
and are obtained using Buchberger's Algorithm, are equal. Another result is
that if the origin (i.e. the point corresponding to the unique monomial ideal)
in the Groebner basis scheme is smooth, then the scheme itself is isomorphic to
an affine space. This fact represents a remarkable difference between border
basis and Groebner basis schemes. Since it is natural to look for situations
where a Groebner basis scheme and the corresponding border basis scheme are
equal, we address the issue, provide an answer, and exhibit some consequences.
Open problems are discussed at the end of the paper.


title:
Conductivity of graphene: How to distinguish between samples with short
  and long range scatterers

abstract:
  Applying a quasiclassical equation to carriers in graphene we found a way how
to distinguish between samples with the domination of short and long range
scatterers from the conductivity measurements. The model proposed explains
recent transport experiments with chemically doped as well as suspended
graphene.


title: A selector for structural isomers of neutral molecules

abstract:
  We have selected and spatially separated the two conformers of 3-aminophenol
(C$_6$H$_7$NO) present in a molecular beam. Analogous to the separation of ions
based on their mass-to-charge ratios in a quadrupole mass filter, the neutral
conformers are separated based on their different mass-to-dipole-moment ratios
in an ac electric quadrupole selector. For a given ac frequency, the individual
conformers experience different focusing forces, resulting in different
transmissions through the selector. These experiments demonstrate that
conformer-selected samples of large molecules can be prepared, offering new
possibilities for the study of gas-phase biomolecules.


title:
Gravitational collapse in an expanding background and the role of
  substructure II: Excess power at small scales and its effect of collapse of
  structures at larger scales

abstract:
  We study the interplay of clumping at small scales with the collapse and
relaxation of perturbations at larger scales using N-Body simulations. We
quantify the effect of collapsed haloes on perturbations at larger scales using
two point correlation function, moments of counts in cells and mass function.
The purpose of the study is twofold and the primary aim is to quantify the role
played by collapsed low mass haloes in the evolution of perturbations at large
scales, this is in view of the strong effect seen when the large scale
perturbation is highly symmetric. Another reason for this study is to ask
whether features or a cutoff in the initial power spectrum can be detected
using measures of clustering at scales that are already non-linear. The final
aim is to understand the effect of ignoring perturbations at scales smaller
than the resolution of N-Body simulations. We find that these effects are
ignorable if the scale of non-linearity is larger than the average
inter-particle separation in simulations. Features in in the initial power
spectrum can be detected easily if the scale of these features is in the linear
regime, detecting such features becomes difficult as the relevant scales become
non-linear. We find no effect of features in initial power spectra at small
scales on the evolved power spectra at large scales. We may conclude that in
general, the effect on evolution of perturbations at large scales of clumping
on small scales is very small and may be ignored in most situations.


title: Probing isotope effects in chemical reactions using single ions

abstract:
  Isotope effects in reactions between Mg+ in the 3p 2P3/2 excited state and
molecular hydrogen at thermal energies are studied through single reaction
events. From only ~250 reactions with HD, the branching ratio between formation
of MgD+ and MgH+ is found to be larger than 5. From additional 65 reactions
with H2 and D2 we find that the overall decay probability of the intermediate
MgH2+, MgHD+ or MgD2+ complexes is the same. Our study shows that few single
ion reactions can provide quantitative information on ion-neutral reactions.
Hence, the method is well-suited for reaction studies involving rare species,
e.g., rare isotopes or short-lived unstable elements.


title:
Differences between normal and shuffled texts: structural properties of
  weighted networks

abstract:
  In this paper we deal with the structural properties of weighted networks.
Starting from an empirical analysis of a linguistic network, we analyse the
differences between the statistical properties of a real and a shuffled network
and we show that the scale free degree distribution and the scale free weight
distribution are induced by the scale free strength distribution, that is
Zipf's law. We test the result on a scientific collaboration network, that is a
social network, and we define a measure, the vertex selectivity, that can
easily distinguish a real network from a shuffled network. We prove, via an
ad-hoc stochastic growing network with second order correlations, that this
measure can effectively capture the correlations within the topology of the
network.


title:
Theoretical and experimental investigations of Coulomb blockade in
  coupled quantum dot systems

abstract:
  Two strongly coupled quantum dots are theoretically and experimentally
investigated. In the conductance measurements of a GaAs based low-dimensional
system additional features to the Coulomb blockade have been detected at low
temperatures. These regions of finite conductivity are compared with
theoretical investigations of a strongly coupled quantum dot system and good
agreement of the theoretical and the experimental results has been found.


title:
Kernel regression uniform rate estimation for censored data under
  $\alpha$-mixing condition

abstract:
  In this paper, we study the behavior of a kernel estimator of the regression
function in the right censored model with $\alpha$-mixing data . The uniform
strong consistency over a real compact set of the estimate is established along
with a rate of convergence. Some simulations are carried out to illustrate the
behavior of the estimate with different examples for finite sample sizes.


title: Remarks on Fourier multipliers and applications to the Wave equation

abstract:
  Exploiting continuity properties of Fourier multipliers on modulation spaces
and Wiener amalgam spaces, we study the
  Cauchy problem for the NLW equation. Local wellposedness for rough data in
modulation spaces and Wiener amalgam spaces is shown. The results formulated in
the framework of modulation spaces refine those in [3]. The same arguments may
apply to obtain local wellposedness for the NLKG equation.


title: Coupling Constant for $\mathbf{N^*(1535)N\rho}$

abstract:
  The value of the $N^*(1535)N\rho$ coupling constant $g_{N^*N\rho}$ derived
from the $N^*(1535) \to N\rho \to N \pi \pi$ decay is compared with that
deduced from the radiative decay $N^*(1535) \to N \gamma$ using the
vector-meson-dominance model. On the basis of an effective Lagrangian approach,
we show that the value of $g_{N^*N\rho}$ extracted from the available
experimental data on the two decays are consistent, though the error bars are
rather large.


title:
Quiver representations of maximal rank type and an application to
  representations of a quiver with three vertices

abstract:
  We introduce the notion of ''maximal rank type'' for representations of
quivers, which requires certain collections of maps involved in the
representation to be of maximal rank. We show that real root representations of
quivers are of maximal rank type. By using the maximal rank type property and
universal extension functors we construct all real root representations of a
particular wild quiver with three vertices. From this construction it follows
that real root representations of this quiver are tree modules. Moreover,
formulae given by Ringel can be applied to compute the dimension of the
endomorphism ring of a given real root representation.


title: Magnetizing the universe

abstract:
  The origin of cosmic magnetism is an issue of fundamental importance in
astrophysics. We review here some of the ideas of how large scale magnetic
fields in the universe, particularly in galaxies and galaxy clusters could
arise. The popular paradigm involves the generation of a seed magnetic field
followed by turbulent dynamo amplification of the seed field. We first outline
various seed field generation mechanisms including Biermann batteries. These in
general give a field much smaller than the observed field and so they require
further amplification by dynamo action. The basic idea behind fluctuation
dynamos, as applied to cluster magnetism and the mean-field helical dynamo as
applied to disk galaxies, are outlined. Major difficulties with the dynamo
paradigm are considered. It is particularly important to understand the
nonlinear saturation of dynamos, and whether the fields produced are coherent
enough on large-scales to explain the observed fields in galaxies and clusters.
At the same time the alternative possibility of a primordial field lacks firm
theoretical support but can have very interesting observational consequences.


title: Developments in physics of massive stars

abstract:
  New constraints on stellar models are provided by large surveys of massive
stars, interferometric observations and asteroseismology. After a review of the
main results so far obtained, we present new results from rotating models and
discuss comparisons with observed features. We conclude that rotation is a key
feature of massive star physics.


title:
Symbolic lumping of some catenary, mamillary and circular compartmental
  systems

abstract:
  Some of the most important compartmental systems, such as irreversible
catenary, mamillary and circular systems are symbolically simplified by the
method of exact linear lumping. A few symbolically unmanageable systems are
numerically lumped. Transformation of the qualitative properties under lumping
are also traced.


title:
Diversity of reproduction rate supports cooperation in the prisoner's
  dilemma game on complex networks

abstract:
  In human societies the probability of strategy adoption from a given person
may be affected by the personal features. Now we investigate how an
artificially imposed restricted ability to reproduce, overruling ones fitness,
affects an evolutionary process. For this purpose we employ the evolutionary
prisoner's dilemma game on different complex graphs. Reproduction restrictions
can have a facilitative effect on the evolution of cooperation that sets in
irrespective of particularities of the interaction network. Indeed, an
appropriate fraction of less fertile individuals may lead to full supremacy of
cooperators where otherwise defection would be widespread. By studying
cooperation levels within the group of individuals having full reproduction
capabilities, we reveal that the recent mechanism for the promotion of
cooperation is conceptually similar to the one reported previously for
scale-free networks. Our results suggest that the diversity in the reproduction
capability, related to inherently different attitudes of individuals, can
enforce the emergence of cooperative behavior among selfish competitors.


title: Charge-memory polaron effect in molecular junctions

abstract:
  The charge-memory effect, bistability and switching between charged and
neutral states of a molecular junction, as observed in recent STM experiments,
is considered within a minimal polaron model. We show that in the case of
strong electron-vibron interaction the rate of spontaneous quantum switching
between charged and neutral states is exponentially suppressed at zero bias
voltage but can be tuned through a wide range of finite switching timescales
upon changing the bias. We further find that, while junctions with symmetric
voltage drop give rise to random switching at finite bias, asymmetric junctions
exhibit hysteretic behavior enabling controlled switching. Lifetimes and
charge-voltage curves are calculated by the master equation method for weak
coupling to the leads and at stronger coupling by the equation-of-motion method
for nonequilibrium Green functions.


title: Compact heterotic orbifolds in blow-up

abstract:
  We compare heterotic string models on orbifolds with supergravity models on
smooth compact spaces, obtained by resolving the orbifold singularities. Our
main focus is on heterotic E8xE8 models on the resolution of the compact
T^6/Z_3 orbifold with Wilson lines. We explain how different gauge fluxes at
various resolved fixed points can be interpreted in blow down as Wilson lines.
Even when such Wilson lines are trivial from the orbifold perspective, they can
still lead to additional symmetry breaking in blow-up. Full agreement is
achieved between orbifold and resolved models, at the level of gauge
interactions, massless spectrum and anomaly cancellation. In this matching the
blow-up modes are of crucial importance: they play the role of model-dependent
axions involved in the cancellation of multiple anomalous U(1)'s on the
resolution. We illustrate various aspects by investigating blow-ups of a Z_3
MSSM model with two Wilson lines: if all its fixed points are resolved
simultaneously, the SM gauge group is necessarily broken. Finally, we explore
in detail the anomaly cancellation on the complex two dimensional resolution of
C^2/Z_2.


title: Why Does Zipf's Law Break Down in Rank-Size Distribution of Cities?

abstract:
  We study rank-size distribution of cities in Japan on the basis of data
analysis. From the census data after World War II, we find that the rank-size
distribution of cities is composed of two parts, each of which has independent
power exponent. In addition, the power exponent of the head part of the
distribution changes in time and Zipf's law holds only in a restricted period.
We show that Zipf's law broke down due to both of Showa and Heisei great
mergers and recovered due to population growth in middle-sized cities after the
great Showa merger.


title: Effective-interaction approach to the many-boson problem

abstract:
  We show that the convergence behavior of the many-body numerical
diagonalization scheme for strongly interacting bosons in a trap can be
significantly improved by the Lee-Suzuki method adapted from nuclear physics:
One can construct an effective interaction that acts in a space much smaller
than the original Hilbert space. In particular for short-ranged forces and
strong correlations, the method offers a good estimate of the energy and the
excitation spectrum, at a computational cost several orders of magnitude
smaller than that required by the standard method.


title:
On the Fredholm Solvability for a Class of Multidimensional Hyperbolic
  Problems

abstract:
  We prove the Fredholm alternative for a class of two-dimensional first-order
hyperbolic systems with periodic-Dirichlet boundary conditions. Our approach is
based on a regularization via a right parametrix.


title:
Evidence for the formation of a Mott state in potassium-intercalated
  pentacene

abstract:
  We investigate electronic transport through pentacene thin-films intercalated
with potassium. From temperature-dependent conductivity measurements we find
that potassium-intercalated pentacene shows metallic behavior in a broad range
of potassium concentrations. Surprisingly, the conductivity exhibits a
re-entrance into an insulating state when the potassium concentration is
increased past one atom per molecule. We analyze our observations theoretically
by means of electronic structure calculations, and we conclude that the
phenomenon originates from a Mott metal-insulator transition, driven by
electron-electron interactions.


title:
Transmittance and near-field characterization of sub-wavelength tapered
  optical fibers

abstract:
  We have produced high transmission sub-wavelength tapered optical fibers for
the purpose of whispering gallery mode coupling in fused silica microcavities
at 780 nm. A detailed analysis of the fiber transmittance evolution during
tapering is demonstrated to reflect precisely the mode coupling and cutoff in
the fiber. This allows to control the final size, the number of guided modes
and their effective index. These results are checked by evanescent wave mapping
measurements on the resulting taper.


title: Quantum integrability and nonintegrability in the spin-boson model

abstract:
  We study the spectral properties of a spin-boson Hamiltonian that depends on
two continuous parameters $0\leq\Lambda<\infty$ (interaction strength) and
$0\leq\alpha\leq\pi/2$ (integrability switch). In the classical limit this
system has two distinct integrable regimes, $\alpha=0$ and $\alpha=\pi/2$. For
each integrable regime we can express the quantum Hamiltonian as a function of
two action operators. Their eigenvalues (multiples of $\hbar$) are the natural
quantum numbers for the complete level spectrum. This functional dependence
cannot be extended into the nonintegrable regime $(0<\alpha<\pi/2)$. Here level
crossings are prohibited and the level spectrum is naturally described by a
single (energy sorting) quantum number. In consequence, the tracking of
individual eigenstates along closed paths through both regimes leads to
conflicting assignments of quantum numbers. This effect is a useful and
reliable indicator of quantum chaos -- a diagnostic tool that is independent of
any level-statistical analysis.


title: Numerical Simulation of Gluey Particles

abstract:
  We propose here a model and a numerical scheme to compute the motion of rigid
particles interacting through the lubrication force. In the case of a particle
approaching a plane, we propose an algorithm and prove its convergence towards
the solutions to the gluey particle model proposed by B. Maury. We propose a
multi-particle version of this gluey model which is based on the projection of
the velocities onto a set of admissible velocities. Then, we describe a
multi-particle algorithm for the simulation of such systems and present
numerical results.


title: Lorentz symmetry violation and an Analog of Landau levels

abstract:
  Within the context of Lorentz violating extended electrodynamics, we study an
analog of Landau quantization for a system where a neutral particle moves in
the presence of an electromagnetic field and a constant four-vector that breaks
Lorentz symmetry. The nonrelativistic Hamiltonian associated to this system is
obtained using the Foldy-Wouthuysen transformation for a Dirac spinor. The
degenerated energy spectrum is obtained for a time-like and a space-like
parameter Lorentz-breaking vector. The energy dependence of the cyclotron
rotation direction in terms of supersymmetric quantum mechanics is analyzed.


title:
Effect of top quark spin on the unparticle couplings in \gamma\gamma \to
  t\bar{t}

abstract:
  We investigate the potential of $\gamma\gamma$ collisions to probe scalar
unparticle couplings via top-antitop quark pair production. We find 95%
confidence level limits on the unparticle couplings with an integrated
luminosity of $500 fb^{-1}$ and $\sqrt{s}=1$ TeV energy. We investigate the
effect of top quark spin polarization on the unparticle couplings. It is shown
that spin polarization of the top quark leads to a significant improvement in
the sensitivity limits.


title:
The Effects of Variations in Nuclear Processes on Type I X-Ray Burst
  Nucleosynthesis

abstract:
  Type I X-ray bursts are violent stellar events that take place on the
H/He-rich envelopes of accreting neutron stars. We have investigated the role
played by uncertainties in nuclear processes on the nucleosynthesis
accompanying these explosive phenomena. Two different approaches have been
adopted, in the framework of post-processing calculations. In the first one,
nuclear rates are varied individually within uncertainties. Ten different
models, covering the characteristic parameter space for these stellar events,
have been considered. The second, somewhat complementary approach involves a
Monte Carlo code in which all nuclear rates are randomly varied within
uncertainty limits simultaneously. All in all, about 50,000 post-processing
calculations, with a network containing 606 nuclides (H to 113Xe) and more than
3500 nuclear processes, have been performed in this work. A brief comparison
between both procedures is outlined together with an overall account of the key
nuclear reactions whose uncertainties have the largest impact in our X-ray
burst nucleosynthesis studies.


title: Lagrangian and Hamiltonian two-scale reduction

abstract:
  Studying high-dimensional Hamiltonian systems with microstructure, it is an
important and challenging problem to identify reduced macroscopic models that
describe some effective dynamics on large spatial and temporal scales. This
paper concerns the question how reasonable macroscopic Lagrangian and
Hamiltonian structures can by derived from the microscopic system.
  In the first part we develop a general approach to this problem by
considering non-canonical Hamiltonian structures on the tangent bundle. This
approach can be applied to all Hamiltonian lattices (or Hamiltonian PDEs) and
involves three building blocks: (i) the embedding of the microscopic system,
(ii) an invertible two-scale transformation that encodes the underlying scaling
of space and time, (iii) an elementary model reduction that is based on a
Principle of Consistent Expansions.
  In the second part we exemplify the reduction approach and derive various
reduced PDE models for the atomic chain. The reduced equations are either
related to long wave-length motion or describe the macroscopic modulation of an
oscillatory microstructure.


title:
Wilson lines and transverse-momentum dependent parton distribution
  functions: A renormalization-group analysis

abstract:
  The renormalization-group properties of gauge-invariant transverse-momentum
dependent (TMD) parton distribution functions (PDF) in QCD are addressed. We
perform an analysis of their leading-order anomalous dimensions, which are
local quantities, making use of the renormalization properties of
contour-dependent composite operators in QCD. We argue that attaching
individual gauge links with transverse segments to quark fields in the
light-cone gauge, the associated gauge contours are joined at light-cone
infinity through a cusp-like junction point. We find that the renormalization
effect on the junction point creates an anomalous dimension which has to be
compensated in order to recover the results in a covariant gauge. To this end,
we include in the definition of the TMD PDF an additional soft counter term
(gauge link) along that cusped contour. We show that the eikonal factors
entering this counter term are peculiar to the Mandelstam field formalism and
are absent when one uses a direct gauge contour.


title: A new approach to characterize qubit channels

abstract:
  We analyze qubit channels by exploiting the possibility of representing
two-level quantum systems in terms of characteristic functions. To do so, we
use functions of non-commuting variables (Grassmann variables), defined in
terms of generalized displacement operators, following an approach which
resemble the one adopted for continuous-variable (Bosonic) systems. It allows
us to introduce the notion of qubit Gaussian channels and to show that they
share similar properties with the corresponding continuous-variable
counterpart. Some examples of qubit channels are investigated using this
approach.


title: On the decomposition of k-valued rational relations

abstract:
  We give a new, and hopefully more easily understandable, structural proof of
the decomposition of a $k$-valued transducer into $k$ unambiguous functional
ones, a result established by A. Weber in 1996. Our construction is based on a
lexicographic ordering of computations of automata and on two coverings that
can be build by means of this ordering. The complexity of the construction,
measured as the number of states of the transducers involved in the
decomposition, improves the original one by one exponential. Moreover, this
method allows further generalisation that solves the problem of decomposition
of rational relations with bounded length-degree, which was left open in
Weber's paper.


title: A Gelfand Model for Wreath Products

abstract:
  A Gelafand model for wreath products $\Z_r\wr S_n$ is constructed. The proof
relies on a combinatorial interpretation of the characters of the model,
extending a classical result of Frobenius and Schur.


title:
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous
  Logspace

abstract:
  The isomorphism problem for planar graphs is known to be efficiently
solvable. For planar 3-connected graphs, the isomorphism problem can be solved
by efficient parallel algorithms, it is in the class $AC^1$. In this paper we
improve the upper bound for planar 3-connected graphs to unambiguous logspace,
in fact to $UL \cap coUL$. As a consequence of our method we get that the
isomorphism problem for oriented graphs is in $NL$. We also show that the
problems are hard for $L$.


title: Efficient Minimization of DFAs with Partial Transition Functions

abstract:
  Let PT-DFA mean a deterministic finite automaton whose transition relation is
a partial function. We present an algorithm for minimizing a PT-DFA in $O(m \lg
n)$ time and $O(m+n+\alpha)$ memory, where $n$ is the number of states, $m$ is
the number of defined transitions, and $\alpha$ is the size of the alphabet.
Time consumption does not depend on $\alpha$, because the $\alpha$ term arises
from an array that is accessed at random and never initialized. It is not
needed, if transitions are in a suitable order in the input. The algorithm uses
two instances of an array-based data structure for maintaining a refinable
partition. Its operations are all amortized constant time. One instance
represents the classical blocks and the other a partition of transitions. Our
measurements demonstrate the speed advantage of our algorithm on PT-DFAs over
an $O(\alpha n \lg n)$ time, $O(\alpha n)$ memory algorithm.


title:
Design by Measure and Conquer, A Faster Exact Algorithm for Dominating
  Set

abstract:
  The measure and conquer approach has proven to be a powerful tool to analyse
exact algorithms for combinatorial problems, like Dominating Set and
Independent Set. In this paper, we propose to use measure and conquer also as a
tool in the design of algorithms. In an iterative process, we can obtain a
series of branch and reduce algorithms. A mathematical analysis of an algorithm
in the series with measure and conquer results in a quasiconvex programming
problem. The solution by computer to this problem not only gives a bound on the
running time, but also can give a new reduction rule, thus giving a new,
possibly faster algorithm. This makes design by measure and conquer a form of
computer aided algorithm design. When we apply the methodology to a Set Cover
modelling of the Dominating Set problem, we obtain the currently fastest known
exact algorithms for Dominating Set: an algorithm that uses $O(1.5134^n)$ time
and polynomial space, and an algorithm that uses $O(1.5063^n)$ time.


title: Structural aspects of tilings

abstract:
  In this paper, we study the structure of the set of tilings produced by any
given tile-set. For better understanding this structure, we address the set of
finite patterns that each tiling contains. This set of patterns can be analyzed
in two different contexts: the first one is combinatorial and the other
topological. These two approaches have independent merits and, once combined,
provide somehow surprising results. The particular case where the set of
produced tilings is countable is deeply investigated while we prove that the
uncountable case may have a completely different structure. We introduce a
pattern preorder and also make use of Cantor-Bendixson rank. Our first main
result is that a tile-set that produces only periodic tilings produces only a
finite number of them. Our second main result exhibits a tiling with exactly
one vector of periodicity in the countable case.


title: Understanding maximal repetitions in strings

abstract:
  The cornerstone of any algorithm computing all repetitions in a string of
length n in O(n) time is the fact that the number of runs (or maximal
repetitions) is O(n). We give a simple proof of this result. As a consequence
of our approach, the stronger result concerning the linearity of the sum of
exponents of all runs follows easily.


title: In-beam tests of scintillating fibre detectors at MAMI and at GSI

abstract:
  The performance of scintillating fibre detectors was studied with electrons
at the spectrometer facility of the Mainz microtron MAMI, as well as in a C-12
beam of 2 AGeV energy and in a beam of different particle species at GSI.
Multi-anode photomultipliers were used to read out one or more bundles of 128
fibres each in different geometries. For electrons a time resolution of FWHM =
1 ns was measured in a single detector plane with a detection efficiency
epsilon > 99%. A time resolution of 310 ps (FWHM) between two planes of fibres
was achieved for carbon ions, leading to a FWHM = 220 ps for a single detector.
The hit position residual was measured with a width of FWHM = 0.27 mm. The
variation in the measured energy deposition was Delta E/E= 15-20% (FWHM) for
carbon ions. In addition, the energy response to p/pi/d particles was studied.
Based on the good detector performance fibre hodoscopes will be constructed for
the KAOS/A1 spectrometer at MAMI and for the HypHI experiment at GSI.


title: Equilibria, Fixed Points, and Complexity Classes

abstract:
  Many models from a variety of areas involve the computation of an equilibrium
or fixed point of some kind. Examples include Nash equilibria in games; market
equilibria; computing optimal strategies and the values of competitive games
(stochastic and other games); stable configurations of neural networks;
analysing basic stochastic models for evolution like branching processes and
for language like stochastic context-free grammars; and models that incorporate
the basic primitives of probability and recursion like recursive Markov chains.
It is not known whether these problems can be solved in polynomial time. There
are certain common computational principles underlying different types of
equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP.
Representative complete problems for these classes are respectively, pure Nash
equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria
in 2-player normal form games, and (mixed) Nash equilibria in normal form games
with 3 (or more) players. This paper reviews the underlying computational
principles and the corresponding classes.


title: Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

abstract:
  In the Multislope Ski Rental problem, the user needs a certain resource for
some unknown period of time. To use the resource, the user must subscribe to
one of several options, each of which consists of a one-time setup cost
(``buying price''), and cost proportional to the duration of the usage
(``rental rate''). The larger the price, the smaller the rent. The actual usage
time is determined by an adversary, and the goal of an algorithm is to minimize
the cost by choosing the best option at any point in time. Multislope Ski
Rental is a natural generalization of the classical Ski Rental problem (where
the only options are pure rent and pure buy), which is one of the fundamental
problems of online computation. The Multislope Ski Rental problem is an
abstraction of many problems where online decisions cannot be modeled by just
two options, e.g., power management in systems which can be shut down in parts.
In this paper we study randomized algorithms for Multislope Ski Rental. Our
results include the best possible online randomized strategy for any additive
instance, where the cost of switching from one option to another is the
difference in their buying prices; and an algorithm that produces an
$e$-competitive randomized strategy for any (non-additive) instance.


title: Limit complexities revisited

abstract:
  The main goal of this paper is to put some known results in a common
perspective and to simplify their proofs. We start with a simple proof of a
result from (Vereshchagin, 2002) saying that $\limsup_n\KS(x|n)$ (here
$\KS(x|n)$ is conditional (plain) Kolmogorov complexity of $x$ when $n$ is
known) equals $\KS^{\mathbf{0'}(x)$, the plain Kolmogorov complexity with
$\mathbf{0'$-oracle. Then we use the same argument to prove similar results for
prefix complexity (and also improve results of (Muchnik, 1987) about limit
frequencies), a priori probability on binary tree and measure of effectively
open sets. As a by-product, we get a criterion of $\mathbf{0'}$ Martin-L\"of
randomness (called also 2-randomness) proved in (Miller, 2004): a sequence
$\omega$ is 2-random if and only if there exists $c$ such that any prefix $x$
of $\omega$ is a prefix of some string $y$ such that $\KS(y)\ge |y|-c$. (In the
1960ies this property was suggested in (Kolmogorov, 1968) as one of possible
randomness definitions; its equivalence to 2-randomness was shown in (Miller,
2004) while proving another 2-randomness criterion (see also (Nies et al.
2005)): $\omega$ is 2-random if and only if $\KS(x)\ge |x|-c$ for some $c$ and
infinitely many prefixes $x$ of $\omega$. Finally, we show that the low-basis
theorem can be used to get alternative proofs for these results and to improve
the result about effectively open sets; this stronger version implies the
2-randomness criterion mentioned in the previous sentence.


title: Trimmed Moebius Inversion and Graphs of Bounded Degree

abstract:
  We study ways to expedite Yates's algorithm for computing the zeta and
Moebius transforms of a function defined on the subset lattice. We develop a
trimmed variant of Moebius inversion that proceeds point by point, finishing
the calculation at a subset before considering its supersets. For an
$n$-element universe $U$ and a family $\scr F$ of its subsets, trimmed Moebius
inversion allows us to compute the number of packings, coverings, and
partitions of $U$ with $k$ sets from $\scr F$ in time within a polynomial
factor (in $n$) of the number of supersets of the members of $\scr F$. Relying
on an intersection theorem of Chung et al. (1986) to bound the sizes of set
families, we apply these ideas to well-studied combinatorial optimisation
problems on graphs of maximum degree $\Delta$. In particular, we show how to
compute the Domatic Number in time within a polynomial factor of
$(2^{\Delta+1-2)^{n/(\Delta+1)$ and the Chromatic Number in time within a
polynomial factor of $(2^{\Delta+1-\Delta-1)^{n/(\Delta+1)$. For any constant
$\Delta$, these bounds are $O\bigl((2-\epsilon)^n\bigr)$ for $\epsilon>0$
independent of the number of vertices $n$.


title:
Aplicando modelos de granos de polvo con propiedades meteoriticas al
  continuo ionizante de algunos Nucleos Activos de Galaxias

abstract:
  We construct extinction curves based on Mie's theory for spherical dust grain
with size distributions between 50-2500 A and composed by elements found in
meteorites. We explore the issue of whether the observed spectral energy
distribution might be dust absorbed in the far and near-UV by this kind of dust
grains. Using this approach, satisfactory fits to the 11 spectra can be
obtained.
  -----
  En este trabajo, presentamos las diversas curvas de extincion que hemos
calculado con base a la teoria Mie para granos de polvo esfericos, con
distribuciones de acuerdo a su tamano (entre 50-2500 A) y con diversos
compuestos quimicos hallados en meteoritos. Bajo el posible paradigma que hemos
desarrollado, estas curvas de extincion al ser aplicadas a un continuo
ionizante teorico y comparadas con 11 espectros observados de quasares, hemos
encontrado de manera exitosa reproducir tanto el quiebre UV asi como el
problema de suavidad presentes en el continuo ionizante de algunos Nucleos
Activos de Galaxias.


title: Minimizing Flow Time in the Wireless Gathering Problem

abstract:
  We address the problem of efficient data gathering in a wireless network
through multi-hop communication. We focus on the objective of minimizing the
maximum flow time of a data packet. We prove that no polynomial time algorithm
for this problem can have approximation ratio less than $\Omega(m^{1/3)$ when
$m$ packets have to be transmitted, unless $P = NP$. We then use resource
augmentation to assess the performance of a FIFO-like strategy. We prove that
this strategy is 5-speed optimal, i.e., its cost remains within the optimal
cost if we allow the algorithm to transmit data at a speed 5 times higher than
that of the optimal solution we compare to.


title: On amenability of automata groups

abstract:
  We show that the group of bounded automatic automorphisms of a rooted tree is
amenable, which implies amenability of numerous classes of groups generated by
finite automata. The proof is based on reducing the problem to showing
amenability just of a certain explicit family of groups ("Mother groups") which
is done by analyzing the asymptotic properties of random walks on these groups.


title: Factoring Polynomials over Finite Fields using Balance Test

abstract:
  We study the problem of factoring univariate polynomials over finite fields.
Under the assumption of the Extended Riemann Hypothesis (ERH), (Gao, 2001)
designed a polynomial time algorithm that fails to factor only if the input
polynomial satisfies a strong symmetry property, namely square balance. In this
paper, we propose an extension of Gao's algorithm that fails only under an even
stronger symmetry property. We also show that our property can be used to
improve the time complexity of best deterministic algorithms on most input
polynomials. The property also yields a new randomized polynomial time
algorithm.


title: On Termination for Faulty Channel Machines

abstract:
  A channel machine consists of a finite controller together with several fifo
channels; the controller can read messages from the head of a channel and write
messages to the tail of a channel. In this paper, we focus on channel machines
with insertion errors, i.e., machines in whose channels messages can
spontaneously appear. Such devices have been previously introduced in the study
of Metric Temporal Logic. We consider the termination problem: are all the
computations of a given insertion channel machine finite? We show that this
problem has non-elementary, yet primitive recursive complexity.


title: 2T Physics and Quantum Mechanics

abstract:
  We use a local scale invariance of a classical Hamiltonian and describe how
to construct six different formulations of quantum mechanics in spaces with two
time-like dimensions. All these six formulations have the same classical limit
described by the same Hamiltonian. One of these formulations is used as a basis
for a complementation of the usual quantum mechanics when in the presence of
gravity.


title: Stackelberg Network Pricing Games

abstract:
  We study a multi-player one-round game termed Stackelberg Network Pricing
Game, in which a leader can set prices for a subset of $m$ priceable edges in a
graph. The other edges have a fixed cost. Based on the leader's decision one or
more followers optimize a polynomial-time solvable combinatorial minimization
problem and choose a minimum cost solution satisfying their requirements based
on the fixed costs and the leader's prices. The leader receives as revenue the
total amount of prices paid by the followers for priceable edges in their
solutions, and the problem is to find revenue maximizing prices. Our model
extends several known pricing problems, including single-minded and unit-demand
pricing, as well as Stackelberg pricing for certain follower problems like
shortest path or minimum spanning tree. Our first main result is a tight
analysis of a single-price algorithm for the single follower game, which
provides a $(1+\epsilon) \log m$-approximation for any $\epsilon >0$. This can
be extended to provide a $(1+\epsilon)(\log k + \log m)$-approximation for the
general problem and $k$ followers. The latter result is essentially best
possible, as the problem is shown to be hard to approximate within
$\mathcal{O(\log^\epsilon k + \log^\epsilon m)$. If followers have demands, the
single-price algorithm provides a $(1+\epsilon)m^2$-approximation, and the
problem is hard to approximate within $\mathcal{O(m^\epsilon)$ for some
$\epsilon >0$. Our second main result is a polynomial time algorithm for
revenue maximization in the special case of Stackelberg bipartite vertex cover,
which is based on non-trivial max-flow and LP-duality techniques. Our results
can be extended to provide constant-factor approximations for any constant
number of followers.


title: Weak index versus Borel rank

abstract:
  We investigate weak recognizability of deterministic languages of infinite
trees. We prove that for deterministic languages the Borel hierarchy and the
weak index hierarchy coincide. Furthermore, we propose a procedure computing
for a deterministic automaton an equivalent minimal index weak automaton with a
quadratic number of states. The algorithm works within the time of solving the
emptiness problem.


title:
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a
  Related Lower Bound

abstract:
  We study the one-way number-on-the-forehead (NOF) communication complexity of
the $k$-layer pointer jumping problem with $n$ vertices per layer. This classic
problem, which has connections to many aspects of complexity theory, has seen a
recent burst of research activity, seemingly preparing the ground for an
$\Omega(n)$ lower bound, for constant $k$. Our first result is a surprising
sublinear -- i.e., $o(n)$ -- upper bound for the problem that holds for $k \ge
3$, dashing hopes for such a lower bound. A closer look at the protocol
achieving the upper bound shows that all but one of the players involved are
collapsing, i.e., their messages depend only on the composition of the layers
ahead of them. We consider protocols for the pointer jumping problem where all
players are collapsing. Our second result shows that a strong $n - O(\log n)$
lower bound does hold in this case. Our third result is another upper bound
showing that nontrivial protocols for (a non-Boolean version of) pointer
jumping are possible even when all players are collapsing. Our lower bound
result uses a novel proof technique, different from those of earlier lower
bounds that had an information-theoretic flavor. We hope this is useful in
further study of the problem.


title: Analytic aspects of the shuffle product

abstract:
  There exist very lucid explanations of the combinatorial origins of rational
and algebraic functions, in particular with respect to regular and context free
languages. In the search to understand how to extend these natural
correspondences, we find that the shuffle product models many key aspects of
D-finite generating functions, a class which contains algebraic. We consider
several different takes on the shuffle product, shuffle closure, and shuffle
grammars, and give explicit generating function consequences. In the process,
we define a grammar class that models D-finite generating functions.


title: Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

abstract:
  Let $G$ be a directed planar graph of complexity $n$, each arc having a
nonnegative length. Let $s$ and $t$ be two distinct faces of $G$; let
$s_1,...,s_k$ be vertices incident with $s$; let $t_1,...,t_k$ be vertices
incident with $t$. We give an algorithm to compute $k$ pairwise vertex-disjoint
paths connecting the pairs $(s_i,t_i)$ in $G$, with minimal total length, in
$O(kn\log n)$ time.


title: Geodesic Fr\'echet Distance Inside a Simple Polygon

abstract:
  We unveil an alluring alternative to parametric search that applies to both
the non-geodesic and geodesic Fr\'echet optimization problems. This randomized
approach is based on a variant of red-blue intersections and is appealing due
to its elegance and practical efficiency when compared to parametric search. We
present the first algorithm for the geodesic Fr\'echet distance between two
polygonal curves $A$ and $B$ inside a simple bounding polygon $P$. The geodesic
Fr\'echet decision problem is solved almost as fast as its non-geodesic sibling
and requires $O(N^{2\log k)$ time and $O(k+N)$ space after $O(k)$
preprocessing, where $N$ is the larger of the complexities of $A$ and $B$ and
$k$ is the complexity of $P$. The geodesic Fr\'echet optimization problem is
solved by a randomized approach in $O(k+N^{2\log kN\log N)$ expected time and
$O(k+N^{2)$ space. This runtime is only a logarithmic factor larger than the
standard non-geodesic Fr\'echet algorithm (Alt and Godau 1995). Results are
also presented for the geodesic Fr\'echet distance in a polygonal domain with
obstacles and the geodesic Hausdorff distance for sets of points or sets of
line segments inside a simple polygon $P$.


title: On Dynamic Breadth-First Search in External-Memory

abstract:
  We provide the first non-trivial result on dynamic breadth-first search (BFS)
in external-memory: For general sparse undirected graphs of initially $n$ nodes
and O(n) edges and monotone update sequences of either $\Theta(n)$ edge
insertions or $\Theta(n)$ edge deletions, we prove an amortized
high-probability bound of $O(n/B^{2/3}+\sort(n)\cdot \log B)$ I/Os per update.
In contrast, the currently best approach for static BFS on sparse undirected
graphs requires $\Omega(n/B^{1/2}+\sort(n))$ I/Os.


title: The universal sl(2) cohomology via webs and foams

abstract:
  We construct the universal sl(2)-tangle cohomology using an approach with
webs and dotted foams. This theory depends on two parameters, and for the case
of links it is a categorification of the unnormalized Jones polynomial of the
link.


title: Scattering problem for the local parametric resonance equation

abstract:
  In this paper we present the solution of local parametric resonance equation
in terms of parabolic cylinder functions and solve the scattering problem for
this equation.


title:
Deterministically Isolating a Perfect Matching in Bipartite Planar
  Graphs

abstract:
  We present a deterministic way of assigning small (log bit) weights to the
edges of a bipartite planar graph so that the minimum weight perfect matching
becomes unique. The isolation lemma as described in (Mulmuley et al. 1987)
achieves the same for general graphs using a randomized weighting scheme,
whereas we can do it deterministically when restricted to bipartite planar
graphs. As a consequence, we reduce both decision and construction versions of
the matching problem to testing whether a matrix is singular, under the promise
that its determinant is 0 or 1, thus obtaining a highly parallel SPL algorithm
for bipartite planar graphs. This improves the earlier known bounds of
non-uniform SPL by (Allender et al. 1999) and $NC^2$ by (Miller and Naor 1995,
Mahajan and Varadarajan 2000). It also rekindles the hope of obtaining a
deterministic parallel algorithm for constructing a perfect matching in
non-bipartite planar graphs, which has been open for a long time. Our
techniques are elementary and simple.


title:
An Improved Randomized Truthful Mechanism for Scheduling Unrelated
  Machines

abstract:
  We study the scheduling problem on unrelated machines in the mechanism design
setting. This problem was proposed and studied in the seminal paper (Nisan and
Ronen 1999), where they gave a 1.75-approximation randomized truthful mechanism
for the case of two machines. We improve this result by a 1.6737-approximation
randomized truthful mechanism. We also generalize our result to a
$0.8368m$-approximation mechanism for task scheduling with $m$ machines, which
improve the previous best upper bound of $0.875m(Mu'alem and Schapira 2007).


title: Tight Bounds for Blind Search on the Integers

abstract:
  We analyze a simple random process in which a token is moved in the interval
$A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,n\$.
Initially, the token is placed in a random position in $A$. In round $t$, a
random value $d$ is chosen according to $\mu$. If the token is in position
$a\geq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$
be the number of rounds until the token reaches position 0. We show tight
bounds for the expectation of $T$ for the optimal distribution $\mu$. More
precisely, we show that $\min_\mu\{E_\mu(T)\=\Theta((\log n)^2)$. For the
proof, a novel potential function argument is introduced. The research is
motivated by the problem of approximating the minimum of a continuous function
over $[0,1]$ with a ``blind'' optimization strategy.


title: Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps

abstract:
  This paper presents a formalized proof of a discrete form of the Jordan Curve
Theorem. It is based on a hypermap model of planar subdivisions, formal
specifications and proofs assisted by the Coq system. Fundamental properties
are proven by structural or noetherian induction: Genus Theorem, Euler's
Formula, constructive planarity criteria. A notion of ring of faces is
inductively defined and a Jordan Curve Theorem is stated and proven for any
planar hypermap.


title: Trimming of Graphs, with Application to Point Labeling

abstract:
  For $t,g>0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable
if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$
and with no simple path of more than $g$ edges. A family of graphs is trimmable
if for each constant $t>0$, there is a constant $g=g(t)$ such that every
vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every
family of graphs of bounded domino treewidth is trimmable. This implies that
every family of graphs of bounded degree is trimmable if the graphs in the
family have bounded treewidth or are planar. Based on this result, we derive a
polynomial-time approximation scheme for the problem of labeling weighted
points with nonoverlapping sliding labels of unit height and given lengths so
as to maximize the total weight of the labeled points. This settles one of the
last major open questions in the theory of map labeling.


title: Computing Minimum Spanning Trees with Uncertainty

abstract:
  We consider the minimum spanning tree problem in a setting where information
about the edge weights of the given graph is uncertain. Initially, for each
edge $e$ of the graph only a set $A_e$, called an uncertainty area, that
contains the actual edge weight $w_e$ is known. The algorithm can `update' $e$
to obtain the edge weight $w_e \in A_e$. The task is to output the edge set of
a minimum spanning tree after a minimum number of updates. An algorithm is
$k$-update competitive if it makes at most $k$ times as many updates as the
optimum. We present a 2-update competitive algorithm if all areas $A_e$ are
open or trivial, which is the best possible among deterministic algorithms. The
condition on the areas $A_e$ is to exclude degenerate inputs for which no
constant update competitive algorithm can exist. Next, we consider a setting
where the vertices of the graph correspond to points in Euclidean space and the
weight of an edge is equal to the distance of its endpoints. The location of
each point is initially given as an uncertainty area, and an update reveals the
exact location of the point. We give a general relation between the edge
uncertainty and the vertex uncertainty versions of a problem and use it to
derive a 4-update competitive algorithm for the minimum spanning tree problem
in the vertex uncertainty model. Again, we show that this is best possible
among deterministic algorithms.


title:
Convergence Thresholds of Newton's Method for Monotone Polynomial
  Equations

abstract:
  Monotone systems of polynomial equations (MSPEs) are systems of fixed-point
equations $X_1 = f_1(X_1, ..., X_n),$ $..., X_n = f_n(X_1, ..., X_n)$ where
each $f_i$ is a polynomial with positive real coefficients. The question of
computing the least non-negative solution of a given MSPE $\vec X = \vec f(\vec
X)$ arises naturally in the analysis of stochastic models such as stochastic
context-free grammars, probabilistic pushdown automata, and back-button
processes. Etessami and Yannakakis have recently adapted Newton's iterative
method to MSPEs. In a previous paper we have proved the existence of a
threshold $k_{\vec f}$ for strongly connected MSPEs, such that after $k_{\vec
f}$ iterations of Newton's method each new iteration computes at least 1 new
bit of the solution. However, the proof was purely existential. In this paper
we give an upper bound for $k_{\vec f}$ as a function of the minimal component
of the least fixed-point $\mu\vec f$ of $\vec f(\vec X)$. Using this result we
show that $k_{\vec f}$ is at most single exponential resp. linear for strongly
connected MSPEs derived from probabilistic pushdown automata resp. from
back-button processes. Further, we prove the existence of a threshold for
arbitrary MSPEs after which each new iteration computes at least $1/w2^h$ new
bits of the solution, where $w$ and $h$ are the width and height of the DAG of
strongly connected components.


title: Lower bounds for adaptive linearity tests

abstract:
  Linearity tests are randomized algorithms which have oracle access to the
truth table of some function f, and are supposed to distinguish between linear
functions and functions which are far from linear. Linearity tests were first
introduced by (Blum, Luby and Rubenfeld, 1993), and were later used in the PCP
theorem, among other applications. The quality of a linearity test is described
by its correctness c - the probability it accepts linear functions, its
soundness s - the probability it accepts functions far from linear, and its
query complexity q - the number of queries it makes. Linearity tests were
studied in order to decrease the soundness of linearity tests, while keeping
the query complexity small (for one reason, to improve PCP constructions).
Samorodnitsky and Trevisan (Samorodnitsky and Trevisan 2000) constructed the
Complete Graph Test, and prove that no Hyper Graph Test can perform better than
the Complete Graph Test. Later in (Samorodnitsky and Trevisan 2006) they prove,
among other results, that no non-adaptive linearity test can perform better
than the Complete Graph Test. Their proof uses the algebraic machinery of the
Gowers Norm. A result by (Ben-Sasson, Harsha and Raskhodnikova 2005) allows to
generalize this lower bound also to adaptive linearity tests. We also prove the
same optimal lower bound for adaptive linearity test, but our proof technique
is arguably simpler and more direct than the one used in (Samorodnitsky and
Trevisan 2006). We also study, like (Samorodnitsky and Trevisan 2006), the
behavior of linearity tests on quadratic functions. However, instead of
analyzing the Gowers Norm of certain functions, we provide a more direct
combinatorial proof, studying the behavior of linearity tests on random
quadratic functions...


title:
A New Framework for Multijet Predictions and its application to Higgs
  Boson production at the LHC

abstract:
  We present a new framework for calculating multi-jet observables through
resummation. The framework is based on the factorisation of scattering
amplitudes in an asymptotic limit. By imposing simple constraints on the
analytic behaviour of the result when applied away from this limit, we get good
agreement with the known lowest order perturbative behaviour of the scattering
amplitude, and predictions for the behaviour to all orders in the perturbative
series. As an example of application we study predictions for Higgs Boson
production through gluon fusion at the LHC in association with at least two
jets.


title: Bang-Bang control of a qubit coupled to a quantum critical spin bath

abstract:
  We analytically and numerically study the effects of pulsed control on the
decoherence of a qubit coupled to a quantum spin bath. When the environment is
critical, decoherence is faster and we show that the control is relatively more
effective. Two coupling models are investigated, namely a qubit coupled to a
bath via a single link and a spin star model, yielding results that are similar
and consistent.


title: A Theory for Valiant's Matchcircuits (Extended Abstract)

abstract:
  The computational function of a matchgate is represented by its character
matrix. In this article, we show that all nonsingular character matrices are
closed under matrix inverse operation, so that for every $k$, the nonsingular
character matrices of $k$-bit matchgates form a group, extending the recent
work of Cai and Choudhary (2006) of the same result for the case of $k=2$, and
that the single and the two-bit matchgates are universal for matchcircuits,
answering a question of Valiant (2002).


title: Geometric Set Cover and Hitting Sets for Polytopes in $R^3$

abstract:
  Suppose we are given a finite set of points $P$ in $\R^3$ and a collection of
polytopes $\mathcal{T}$ that are all translates of the same polytope $T$. We
consider two problems in this paper. The first is the set cover problem where
we want to select a minimal number of polytopes from the collection
$\mathcal{T}$ such that their union covers all input points $P$. The second
problem that we consider is finding a hitting set for the set of polytopes
$\mathcal{T}$, that is, we want to select a minimal number of points from the
input points $P$ such that every given polytope is hit by at least one point.
We give the first constant-factor approximation algorithms for both problems.
We achieve this by providing an epsilon-net for translates of a polytope in
$R^3$ of size $\bigO(\frac{1{\epsilon)$.


title:
Compatibility of Shelah and Stupp's and Muchnik's iteration with
  fragments of monadic second order logic

abstract:
  We investigate the relation between the theory of the iterations in the sense
of Shelah-Stupp and of Muchnik, resp., and the theory of the base structure for
several logics. These logics are obtained from the restriction of set
quantification in monadic second order logic to certain subsets like, e.g.,
finite sets, chains, and finite unions of chains. We show that these theories
of the Shelah-Stupp iteration can be reduced to corresponding theories of the
base structure. This fails for Muchnik's iteration.


title: New Combinatorial Complete One-Way Functions

abstract:
  In 2003, Leonid A. Levin presented the idea of a combinatorial complete
one-way function and a sketch of the proof that Tiling represents such a
function. In this paper, we present two new one-way functions based on
semi-Thue string rewriting systems and a version of the Post Correspondence
Problem and prove their completeness. Besides, we present an alternative proof
of Levin's result. We also discuss the properties a combinatorial problem
should have in order to hold a complete one-way function.


title: On Geometric Spanners of Euclidean and Unit Disk Graphs

abstract:
  We consider the problem of constructing bounded-degree planar geometric
spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay
subgraph is a planar geometric spanner with stretch factor $C_{del\approx
2.42$; however, its degree may not be bounded. Our first result is a very
simple linear time algorithm for constructing a subgraph of the Delaunay graph
with stretch factor $\rho =1+2\pi(k\cos{\frac{\pi{k)^{-1$ and degree bounded by
$k$, for any integer parameter $k\geq 14$. This result immediately implies an
algorithm for constructing a planar geometric spanner of a Euclidean graph with
stretch factor $\rho \cdot C_{del$ and degree bounded by $k$, for any integer
parameter $k\geq 14$. Moreover, the resulting spanner contains a Euclidean
Minimum Spanning Tree (EMST) as a subgraph. Our second contribution lies in
developing the structural results necessary to transfer our analysis and
algorithm from Euclidean graphs to unit disk graphs, the usual model for
wireless ad-hoc networks. We obtain a very simple distributed, {\em
strictly-localized algorithm that, given a unit disk graph embedded in the
plane, constructs a geometric spanner with the above stretch factor and degree
bound, and also containing an EMST as a subgraph. The obtained results
dramatically improve the previous results in all aspects, as shown in the
paper.


title: Quantifying Homology Classes

abstract:
  We develop a method for measuring homology classes. This involves three
problems. First, we define the size of a homology class, using ideas from
relative homology. Second, we define an optimal basis of a homology group to be
the basis whose elements' size have the minimal sum. We provide a greedy
algorithm to compute the optimal basis and measure classes in it. The algorithm
runs in $O(\beta^4 n^3 \log^2 n)$ time, where $n$ is the size of the simplicial
complex and $\beta$ is the Betti number of the homology group. Third, we
discuss different ways of localizing homology classes and prove some hardness
results.


title: Cardinality and counting quantifiers on omega-automatic structures

abstract:
  We investigate structures that can be represented by omega-automata, so
called omega-automatic structures, and prove that relations defined over such
structures in first-order logic expanded by the first-order quantifiers `there
exist at most $\aleph_0$ many', 'there exist finitely many' and 'there exist
$k$ modulo $m$ many' are omega-regular. The proof identifies certain algebraic
properties of omega-semigroups. As a consequence an omega-regular equivalence
relation of countable index has an omega-regular set of representatives. This
implies Blumensath's conjecture that a countable structure with an
$\omega$-automatic presentation can be represented using automata on finite
words. This also complements a very recent result of Hj\"orth, Khoussainov,
Montalban and Nies showing that there is an omega-automatic structure which has
no injective presentation.


title:
Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and
  Compatible Supertrees

abstract:
  Consider a set of labels $L$ and a set of trees ${\mathcal T} = \{{\mathcal
T}^{(1), {\mathcal T}^{(2), ..., {\mathcal T}^{(k) \$ where each tree
${\mathcal T}^{(i)$ is distinctly leaf-labeled by some subset of $L$. One
fundamental problem is to find the biggest tree (denoted as supertree) to
represent $\mathcal T}$ which minimizes the disagreements with the trees in
${\mathcal T}$ under certain criteria. This problem finds applications in
phylogenetics, database, and data mining. In this paper, we focus on two
particular supertree problems, namely, the maximum agreement supertree problem
(MASP) and the maximum compatible supertree problem (MCSP). These two problems
are known to be NP-hard for $k \geq 3$. This paper gives the first polynomial
time algorithms for both MASP and MCSP when both $k$ and the maximum degree $D$
of the trees are constant.


title:
Efficient Algorithms for Membership in Boolean Hierarchies of Regular
  Languages

abstract:
  The purpose of this paper is to provide efficient algorithms that decide
membership for classes of several Boolean hierarchies for which efficiency (or
even decidability) were previously not known. We develop new forbidden-chain
characterizations for the single levels of these hierarchies and obtain the
following results: - The classes of the Boolean hierarchy over level $\Sigma_1$
of the dot-depth hierarchy are decidable in $NL$ (previously only the
decidability was known). The same remains true if predicates mod $d$ for fixed
$d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, then
the classes of the Boolean hierarchy over level $\Sigma_1$ are decidable. - For
the restricted case of a two-letter alphabet, the classes of the Boolean
hierarchy over level $\Sigma_2$ of the Straubing-Th\'erien hierarchy are
decidable in $NL$. This is the first decidability result for this hierarchy. -
The membership problems for all mentioned Boolean-hierarchy classes are
logspace many-one hard for $NL$. - The membership problems for quasi-aperiodic
languages and for $d$-quasi-aperiodic languages are logspace many-one complete
for $PSPACE$.


title: Succinctness of the Complement and Intersection of Regular Expressions

abstract:
  We study the succinctness of the complement and intersection of regular
expressions. In particular, we show that when constructing a regular expression
defining the complement of a given regular expression, a double exponential
size increase cannot be avoided. Similarly, when constructing a regular
expression defining the intersection of a fixed and an arbitrary number of
regular expressions, an exponential and double exponential size increase,
respectively, can in worst-case not be avoided. All mentioned lower bounds
improve the existing ones by one exponential and are tight in the sense that
the target expression can be constructed in the corresponding time class, i.e.,
exponential or double exponential time. As a by-product, we generalize a
theorem by Ehrenfeucht and Zeiger stating that there is a class of DFAs which
are exponentially more succinct than regular expressions, to a fixed
four-letter alphabet. When the given regular expressions are one-unambiguous,
as for instance required by the XML Schema specification, the complement can be
computed in polynomial time whereas the bounds concerning intersection continue
to hold. For the subclass of single-occurrence regular expressions, we prove a
tight exponential lower bound for intersection.


title: The Physics Program at MAMI-C

abstract:
  In February 2007, the fourth stage of the Mainz Microtron, MAMI-C, started
operations with a first experiment. The new Harmonic Double-Sided Microtron
delivers an electron beam with energies up to 1.5 GeV while preserving the
excellent beam quality of the previous stages. The experimental program at MAMI
is focused on studies of the hadron structure in the domain of non-perturbative
QCD. In this paper, a few prominent selections of the extensive physics program
at MAMI-C will be presented.