Search

We study the problem of enumerating Tarski fixed points, focusing on the relational lattices of equivalences, quasiorders and binary relations. We present a polynomial space enumeration algorithm for Tarski fixed points on these lattices and other lattices of polynomial height. It achieves polynomial delay when enumerating fixed points of increasing isotone maps on all three lattices, as well as decreasing isotone maps on the lattice of binary relations. In those cases in which the enumeration algorithm does not guarantee polynomial delay on the three relational lattices on the other hand, we prove exponential lower bounds for deciding the existence of three fixed points when the isotone map is given as an oracle, and that it is NP-hard to find three or more Tarski fixed points. More generally, we show that any deterministic or bounded-error randomized algorithm must perform a number of queries asymptotically at least as large as the lattice width to decide the existence of three fixed points when the isotone map is given as an oracle. Finally, we demonstrate that our findings yield a polynomial delay and space algorithm for listing bisimulations and instances of some related models of behavioral or role equivalence.

We present measurements of the electron helicity asymmetry in quasi-elastic proton knockout from $^{2}$H and $^{12}$C nuclei by polarized electrons. This asymmetry depends on the fifth structure function, is antisymmetric with respect to the scattering plane, and vanishes in the absence of final-state interactions, and thus it provides a sensitive tool for their study. Our kinematics cover the full range in off-coplanarity angle $\phi_{pq}$, with a polar angle $\theta_{pq}$ coverage up to about 8 degrees. The missing energy resolution enabled us to determine the asymmetries for knock-out resulting in different states of the residual $^{11}$B system. We find that the helicity asymmetry for $p$-shell knockout from $^{12}$C depends on the final state of the residual system and is relatively large (up to $\approx 0.16$), especially at low missing momentum. It is considerably smaller (up to $\approx 0.01$) for $s$-shell knockout from both $^{12}$C and $^2$H. The data for $^2$H are in very good agreement with theoretical calculations, while the predictions for $^{12}$C exhibit differences with respect to the data.

An effective approach to improve the detection efficiency of nanoscale light sources relies on a planar antenna configuration, which beams the emitted light into a narrow cone. Planar antennas operate like optical Yagi-Uda antennas, where reflector and director elements are made of metal films. Here we introduce and investigate, both theoretically and experimentally, a scanning implementation of a planar antenna. Using a small ensemble of molecules contained in fluorescent nanobeads placed in the antenna, we independently address the intensity, the radiation pattern and the decay rate as a function of distance between a flat-tip scanning gold wire (reflector) and a thin gold film coated on a glass coverslip (director). The scanning planar antenna changes the radiation pattern of a single fluorescent bead and it beams light into a narrow cone down to angles of 45{\deg} (full width at half maximum). Moreover, the collected signal compared to the case of a glass coverslip is larger than a factor of 3, which is mainly due to the excitation enhancement. These results offer a better understanding of the modification of light-matter interaction by planar antennas and they hold promise for applications, such as sensing, imaging and diagnostics.

We report measurements of the induced polarization $\vec P$ of protons knocked out from $^2$H and $^{12}$C via the $A(e,e'\vec p\,)$ reaction. We have studied the dependence of $\vec P$ on two kinematic variables: the missing momentum $p_{\rm miss}$ and the "off-coplanarity" angle $\phi_{pq}$ between the scattering and reaction planes. For the full 360$\degree$ range in $\phi_{pq}$, both the normal ($P_y$) and, for the first time, the transverse ($P_x$) components of the induced polarization were measured with respect to the coordinate system associated with the scattering plane. $P_x$ vanishes in coplanar kinematics, however in non-coplanar kinematics, it is on the same scale as $P_y$. We find that the dependence on $\phi_{pq}$ is sine-like for $P_x$ and cosine-like for $P_y$. For carbon, the magnitude of the induced polarization is especially large when protons are knocked out from the $p_{3/2}$ shell at very small $p_{\rm miss}$. For the deuteron, the induced polarization is near zero at small $|p_{\rm miss}|$, and its magnitude increases with $|p_{\rm miss}|$. For both nuclei such behavior is reproduced qualitatively by theoretical results, driven largely by the spin-orbit part of the final-state interactions. However, for both nuclei, sizeable discrepancies exist between experiment and theory.

Au and Pt do not form homogeneous bulk alloys as they are thermodynamically not miscible. However, we show that anodic TiO$_2$ nanotubes (NTs) can in-situ be uniformly decorated with homogeneous AuPt alloy nanoparticles (NPs) during their anodic growth. For this, a metallic Ti substrate containing low amounts of dissolved Au (0.1 at%) and Pt (0.1 at%) is used for anodizing. The matrix metal (Ti) is converted to oxide while at the oxide/metal interface direct noble metal particle formation and alloying of Au and Pt takes place; continuously these particles are then picked up by the growing nanotube wall. In our experiments the AuPt alloy NPs have an average size of 4.2 nm and, at the end of the anodic process, are regularly dispersed over the TiO$_2$ nanotubes. These alloyed AuPt particles act as excellent co-catalyst in photocatalytic H2 generation - with a H2 production of 12.04 {\mu}L h-1 under solar light. This represents a strongly enhanced activity as compared with TiO$_2$ NTs decorated with monometallic particles of Au (7 {\mu}L h-1) or Pt (9.96 {\mu}L h-1).

Few-layer molybdenum disulfide (FL-MoS$_2$) films have been integrated into amorphous silicon (a-Si:H) pin photodetectors. To achieve this, vertical a-Si:H photodiodes were grown by plasma-enhanced chemical vapor deposition (PE-CVD) on top of large-scale synthesized and transferred homogeneous FL-MoS$_2$. This novel detector array exhibits long-term stability (more than six month) and outperforms conventional silicon-based pin photodetectors in the infrared range (IR, $\lambda$ = 2120 nm) in terms of sensitivities by up to 50 mAW$^{-1}$. Photodetectivities of up to 2 x 10$^{10}$ Jones and external quantum efficiencies of 3 % are achieved. The detectors further feature the additional functionality of bias-dependent responsivity switching between the different spectral ranges. The realization of such scalable detector arrays is an essential step towards pixelated and wavelength-selective sensors operating in the IR spectral range.

We present measurements of the polarization-transfer components in the $^2$H$(\vec e,e'\vec p)$ reaction, covering a previously unexplored kinematic region with large positive (anti-parallel) missing momentum, $p_{\rm miss}$, up to 220 MeV$/c$, and $Q^2=0.65$ $({\rm GeV}/c)^2$. These measurements, performed at the Mainz Microtron (MAMI), were motivated by theoretical calculations which predict small final-state interaction (FSI) effects in these kinematics, making them favorable for searching for medium modifications of bound nucleons in nuclei. We find in this kinematic region that the measured polarization-transfer components $P_x$ and $P_z$ and their ratio agree with the theoretical calculations, which use free-proton form factors. Using this, we establish upper limits on possible medium effects that modify the bound proton's form factor ratio $G_E/G_M$ at the level of a few percent. We also compare the measured polarization-transfer components and their ratio for $^2$H to those of a free (moving) proton. We find that the universal behavior of $^2$H, $^4$He and $^{12}$C in the double ratio $\frac{(P_x/P_z)^A}{(P_x/P_z)^{^1\rm H}}$ is maintained in the positive missing-momentum region.

We prove that the constructive weighted coalitional manipulation problem for the Schulze voting rule can be solved in polynomial time for an unbounded number of candidates and an unbounded number of manipulators., Comment: Accepted manuscript; proof of Lemma 8 corrected

Sliding window approaches have been widely used for object recognition tasks in recent years. They guarantee an investigation of the entire input image for the object to be detected and allow a localization of that object. Despite the current trend towards deep neural networks, sliding window methods are still used in combination with convolutional neural networks. The risk of overlooking an object is clearly reduced compared to alternative detection approaches which detect objects based on shape, edges or color. Nevertheless, the sliding window technique strongly increases the computational effort as the classifier has to verify a large number of object candidates. This paper proposes a sliding window approach which also uses depth information from a stereo camera. This leads to a greatly decreased number of object candidates without significantly reducing the detection accuracy. A theoretical investigation of the conventional sliding window approach is presented first. Other publications to date only mentioned rough estimations of the computational cost. A mathematical derivation clarifies the number of object candidates with respect to parameters such as image and object size. Subsequently, the proposed disparity sliding window approach is presented in detail. The approach is evaluated on pedestrian detection with annotations and images from the KITTI object detection benchmark. Furthermore, a comparison with two state-of-the-art methods is made. Code is available in C++ and Python https://github.com/julimueller/ disparity-sliding-window., Comment: Submitted to IROS 2018

Recent improvements in object detection are driven by the success of convolutional neural networks (CNN). They are able to learn rich features outperforming hand-crafted features. So far, research in traffic light detection mainly focused on hand-crafted features, such as color, shape or brightness of the traffic light bulb. This paper presents a deep learning approach for accurate traffic light detection in adapting a single shot detection (SSD) approach. SSD performs object proposals creation and classification using a single CNN. The original SSD struggles in detecting very small objects, which is essential for traffic light detection. By our adaptations it is possible to detect objects much smaller than ten pixels without increasing the input image size. We present an extensive evaluation on the DriveU Traffic Light Dataset (DTLD). We reach both, high accuracy and low false positive rates. The trained model is real-time capable with ten frames per second on a Nvidia Titan Xp. Code has been made available at https://github.com/julimueller/tl_ssd., Comment: Submitted to International Conference on Intelligent Transportation Systems (ITSC2018)

The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework of modal dependence logic MDL and team semantics. We show that modal team logic MTL, extending MDL by classical negation, captures exactly the FO-definable bisimulation invariant properties of Kripke structures and teams. We also compare the expressive power of MTL to most of the variants and extensions of MDL recently studied in the area.

This paper introduces modal independence logic MIL, a modal logic that can explicitly talk about independence among propositional variables. Formulas of MIL are not evaluated in worlds but in sets of worlds, so called teams. In this vein, MIL can be seen as a variant of V\"a\"an\"anen's modal dependence logic MDL. We show that MIL embeds MDL and is strictly more expressive. However, on singleton teams, MIL is shown to be not more expressive than usual modal logic, but MIL is exponentially more succinct. Making use of a new form of bisimulation, we extend these expressivity results to modal logics extended by various generalized dependence atoms. We demonstrate the expressive power of MIL by giving a specification of the anonymity requirement of the dining cryptographers protocol in MIL. We also study complexity issues of MIL and show that, though it is more expressive, its satisfiability and model checking problem have the same complexity as for MDL.

The classes Delay-FPT and Total-FPT recently have been introduced into parameterized complexity in order to capture the notion of efficiently solvable parameterized enumeration problems. In this paper we focus on ordered enumeration and will show how to obtain Delay-FPT and Total-FPT enumeration algorithms for several important problems. We propose a generic algorithmic strategy, combining well-known principles stemming from both parameterized algorithmics and enumeration, which shows that, under certain preconditions, the existence of a so-called neighbourhood function among the solutions implies the existence of a Delay-FPT algorithm which outputs all ordered solutions. In many cases, the cornerstone to obtain such a neighbourhood function is a Total-FPT algorithm that outputs all minimal solutions. This strategy is formalized in the context of graph modification problems, and shown to be applicable to numerous other kinds of problems., Comment: 15 pages

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First we define formally different notions of efficient enumeration in the context of parameterized complexity. Second we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems., Comment: Accepted for MFCS 2013; long version of the paper

In this paper we investigate an extended version of modal dependence logic by allowing arbitrary Boolean connectives. Modal dependence logic was recently introduced by Jouko V\"a\"an\"anen by extending modal logic by a the dependence atom dep(.). In this paper we study the computational complexity of the model checking problem. For a complete classification of arbitrary Boolean functions we are using a Lattice approach introduced by Emil Post. This classification is done for all fragments of the logical language allowing modalities $\Diamond$ and $\Box$, the dependence atom, and logical symbols for arbitrary Boolean functions.

In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D-Horn* and show that over finite successor structures it captures the complexity class P of all sets decidable in polynomial time. Furthermore we study the question which of our results can ge generalized to the case of open formulae of D-Horn* and so-called downwards monotone polynomial time properties of teams.