TY - JOUR
AB - We consider N × N Hermitian random matrices with independent identically distributed entries (Wigner matrices). The matrices are normalized so that the average spacing between consecutive eigenvalues is of order 1/ N. Under suitable assumptions on the distribution of the single matrix element, we first prove that, away from the spectral edges, the empirical density of eigenvalues concentrates around the Wigner semicircle law on energy scales η ≫ N -1. This result establishes the semicircle law on the optimal scale and it removes a logarithmic factor from our previous result [6]. We then show a Wegner estimate, i.e., that the averaged density of states is bounded. Finally, we prove that the eigenvalues of a Wigner matrix repel each other, in agreement with the universality conjecture.
AU - László Erdös
AU - Schlein, Benjamin
AU - Yau, Horng-Tzer
ID - 2701
IS - 3
JF - International Mathematics Research Notices
TI - Wegner estimate and level repulsion for Wigner random matrices
ER -
TY - CONF
AB - Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, Σ-protocols for proving knowledge of discrete logarithms in known and hidden order groups are of prime importance. Yet, while these proofs can be performed very efficiently within groups of known order, for hidden order groups the respective proofs are far less efficient.
This paper shows strong evidence that this efficiency gap cannot be bridged. Namely, while there are efficient protocols allowing a prover to cheat only with negligibly small probability in the case of known order groups, we provide strong evidence that for hidden order groups this probability is bounded below by 1/2 for all efficient Σ-protocols not using common reference strings or the like.
We prove our results for a comprehensive class of Σ-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model.
AU - Bangerter, Endre
AU - Camenisch, Jan
AU - Stephan Krenn
ED - Micciancio, Daniele
ID - 2978
TI - Efficiency Limitations for Σ-Protocols for Group Homomorphisms
VL - 5978
ER -
TY - CONF
AB - Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks for numerous cryptographic applications. Although ZK-PoK have a high potential impact, their real world deployment is typically hindered by their significant complexity compared to other (non-interactive) crypto primitives. Moreover, their design and implementation are time-consuming and error-prone.
We contribute to overcoming these challenges as follows: We present a comprehensive specification language and a compiler for ZK-PoK protocols based on Σ-protocols. The compiler allows the fully automatic translation of an abstract description of a proof goal into an executable implementation. Moreover, the compiler overcomes various restrictions of previous approaches, e.g., it supports the important class of exponentiation homomorphisms with hidden-order co-domain, needed for privacy-preserving applications such as DAA. Finally, our compiler is certifying, in the sense that it automatically produces a formal proof of the soundness of the compiled protocol for a large class of protocols using the Isabelle/HOL theorem prover.
AU - Almeida, José Bacelar
AU - Bangerter, Endre
AU - Barbosa, Manuel
AU - Stephan Krenn
AU - Sadeghi, Ahmad-Reza
AU - Schneider, Thomas
ED - Gritzalis, Dimitris
ED - Preneel, Bart
ED - Theoharidou, Marianthi
ID - 2979
TI - A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols
VL - 6345
ER -
TY - JOUR
AB - The epitaxial growth of germanium on silicon leads to the self-assembly of SiGe nanocrystals by a process that allows the size, composition and position of the nanocrystals to be controlled. This level of control, combined with an inherent compatibility with silicon technology, could prove useful in nanoelectronic applications. Here, we report the confinement of holes in quantum-dot devices made by directly contacting individual SiGe nanocrystals with aluminium electrodes, and the production of hybrid superconductor- semiconductor devices, such as resonant supercurrent transistors, when the quantum dot is strongly coupled to the electrodes. Charge transport measurements on weakly coupled quantum dots reveal discrete energy spectra, with the confined hole states displaying anisotropic gyromagnetic factors and strong spin-orbit coupling with pronounced dependences on gate voltage and magnetic field.
AU - Georgios Katsaros
AU - Spathis, Panayotis N
AU - Stoffel, Mathieu
AU - Fournel, Frank
AU - Mongillo, Massimo
AU - Bouchiat, Vincent
AU - Lefloch, François
AU - Rastelli, Armando
AU - Schmidt, Oliver G
AU - De Franceschi, Silvano
ID - 1752
IS - 6
JF - Nature Nanotechnology
TI - Hybrid superconductor-semiconductor devices made from self-assembled SiGe nanocrystals on silicon
VL - 5
ER -
TY - JOUR
AB - We investigate electronic transport in n-i-n GaN nanowires with and without AlN double barriers. The nanowires are grown by catalyst-free, plasma-assisted molecular beam epitaxy enabling abrupt GaN/AlN interfaces as well as longitudinal n-type doping modulation. At low temperature, transport in n-i-n GaN nanowires is dominated by the Coulomb blockade effect. Carriers are confined in the undoped middle region, forming single or multiple islands with a characteristic length of ∼100 nm. The incorporation of two AlN tunnel barriers causes confinement to occur within the GaN dot in between. In the case of a 6 nm thick dot and 2 nm thick barriers, we observe characteristic signatures of Coulomb-blockaded transport in single quantum dots with discrete energy states. For thinner dots and barriers, Coulomb-blockade effects do not play a significant role while the onset of resonant tunneling via the confined quantum levels is accompanied by a negative differential resistance surviving up to ∼150 K.
AU - Songmuang, Rudeeson
AU - Georgios Katsaros
AU - Monroy, Eva
AU - Spathis, Panayotis N
AU - Bougerol, Catherine
AU - Mongillo, Massimo
AU - De Franceschi, Silvano
ID - 1753
IS - 9
JF - Nano Letters
TI - Quantum transport in GaN/AlN double-barrier heterostructure nanowires
VL - 10
ER -
TY - JOUR
AB - The quantum properties of electromagnetic, mechanical or other harmonic oscillators can be revealed by investigating their strong coherent coupling to a single quantum two level system in an approach known as cavity quantum electrodynamics (QED). At temperatures much lower than the characteristic energy level spacing the observation of vacuum Rabi oscillations or mode splittings with one or a few quanta asserts the quantum nature of the oscillator. Here, we study how the classical response of a cavity QED system emerges from the quantum one when its thermal occupation-or effective temperature-is raised gradually over 5 orders of magnitude. In this way we explore in detail the continuous quantum-to-classical crossover and demonstrate how to extract effective cavity field temperatures from both spectroscopic and time-resolved vacuum Rabi measurements.
AU - Johannes Fink
AU - Steffen, L. Kraig
AU - Studer, Peter
AU - Bishop, Lev S
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Bozyigit, Deniz
AU - Lang, C
AU - Filipp, Stefan
AU - Leek, Peter J
AU - Wallraff, Andreas
ID - 1773
IS - 16
JF - Physical Review Letters
TI - Quantum-to-classical transition in cavity quantum electrodynamics
VL - 105
ER -
TY - JOUR
AB - A number of superconducting qubits, such as the transmon or the phase qubit, have an energy level structure with small anharmonicity. This allows for convenient access of higher excited states with similar frequencies. However, special care has to be taken to avoid unwanted higher-level populations when using short control pulses. Here we demonstrate the preparation of arbitrary three level superposition states using optimal control techniques in a transmon. Performing dispersive readout, we extract the populations of all three levels of the qutrit and study the coherence of its excited states. Finally we demonstrate full quantum state tomography of the prepared qutrit states and evaluate the fidelities of a set of states, finding on average 95%.
AU - Bianchetti, R
AU - Filipp, Stefan
AU - Baur, Matthias P
AU - Johannes Fink
AU - Lang, C
AU - Steffen, L. Kraig
AU - Boissonneault, Maxime
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1774
IS - 22
JF - Physical Review Letters
TI - Control and tomography of a three level superconducting artificial atom
VL - 105
ER -
TY - JOUR
AB - This paper describes a passive stereo system for capturing the 3D geometry of a face in a single-shot under standard light sources. The system is low-cost and easy to deploy. Results are submillimeter accurate and commensurate with those from state-ofthe-art systems based on active lighting, and the models meet the quality requirements of a demanding domain like the movie industry. Recovered models are shown for captures from both high-end cameras in a studio setting and from a consumer binocular-stereo camera, demonstrating scalability across a spectrum of camera deployments, and showing the potential for 3D face modeling to move beyond the professional arena and into the emerging consumer market in stereoscopic photography. Our primary technical contribution is a modification of standard stereo refinement methods to capture pore-scale geometry, using a qualitative approach that produces visually realistic results. The second technical contribution is a calibration method suited to face capture systems. The systemic contribution includes multiple demonstrations of system robustness and quality. These include capture in a studio setup, capture off a consumer binocular-stereo camera, scanning of faces of varying gender and ethnicity and age, capture of highly-transient facial expression, and scanning a physical mask to provide ground-truth validation.
AU - Beeler, Thabo
AU - Bernd Bickel
AU - Beardsley, Paul A
AU - Sumner, Bob
AU - Groß, Markus S
ID - 2095
IS - 4
JF - ACM Transactions on Graphics
TI - High-quality single-shot capture of facial geometry
VL - 29
ER -
TY - JOUR
AB - We develop a theory of Malliavin calculus for Banach space-valued random variables. Using radonifying operators instead of symmetric tensor products we extend the Wiener-Itô isometry to Banach spaces. In the white noise case we obtain two sided Lp-estimates for multiple stochastic integrals in arbitrary Banach spaces. It is shown that the Malliavin derivative is bounded on vector-valued Wiener-Itô chaoses. Our main tools are decoupling inequalities for vector-valued random variables. In the opposite direction we use Meyer's inequalities to give a new proof of a decoupling result for Gaussian chaoses in UMD Banach spaces.
AU - Jan Maas
ID - 2124
IS - 2
JF - Journal of Mathematical Analysis and Applications
TI - Malliavin calculus and decoupling inequalities in Banach spaces
VL - 363
ER -
TY - JOUR
AB - We develop an analytic model of vector correlations in rotationally inelastic atom-diatom collisions and test it against the much examined Ar-NO (X2Π) system. Based on the Fraunhofer scattering of matter waves, the model furnishes complex scattering amplitudes needed to evaluate the polarization moments characterizing the quantum stereodynamics. The analytic polarization moments are found to be in an excellent agreement with experimental results and with close-coupling calculations available at thermal energies. The model reveals that the stereodynamics is governed by diffraction from the repulsive core of the Ar-NO potential, which can be characterized by a single Legendre moment.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2194
IS - 5
JF - Physical Chemistry Chemical Physics
TI - An analytic model of the stereodynamics of rotationally inelastic molecular collisions
VL - 12
ER -
TY - JOUR
AB - Following upon our recent work on vector correlations in the Ar-NO collisions [Lemeshko and Friedrich, Phys. Chem. Chem. Phys. 12, 1038 (2010)], we compare model results with close-coupling calculations for a range of channels and collision energies for the He-NO system. The striking agreement between the model and exact polarization moments indicates that the stereodynamics of rotationally inelastic atom-molecule collisions at thermal energies is governed by diffraction of matter waves from a two-dimensional repulsive core of the atom-molecule potential. Furthermore, the model polarization moments characterizing the He-NO, He- O2, He-OH, and He-CaH stereodynamics are found to coalesce into a single, distinctive pattern, which can serve as a "fingerprint" to identify diffraction-driven stereodynamics in future work.
AU - Mikhail Lemeshko
AU - Jambrina, Pablo G
AU - De Miranda, Marcelo P
AU - Friedrich, Břetislav
ID - 2195
IS - 16
JF - Journal of Chemical Physics
TI - Communications: When diffraction rules the stereodynamics of rotationally inelastic collisions
VL - 132
ER -
TY - JOUR
AB - We evaluate the shifts imparted to vibrational and rotational levels of a linear molecule by a nonresonant laser field at intensities of up to 10 12 W/cm2. Both types of shift are found to be either positive or negative, depending on the initial rotational state acted upon by the field. An adiabatic field-molecule interaction imparts a rotational energy shift which is negative and exceeds the concomitant positive vibrational shift by a few orders of magnitude. The rovibrational states are thus pushed downward in such a field. A nonresonant pulsed laser field that interacts nonadiabatically with the molecule is found to impart rotational and vibrational shifts of the same order of magnitude. The nonadiabatic energy transfer occurs most readily at a pulse duration which amounts to about a tenth of the molecule's rotational period and vanishes when the sudden regime is attained for shorter pulses. We applied our treatment to the much-studied 87Rb2 molecule in the last bound vibrational levels of its lowest singlet and triplet electronic states. Our calculations indicate that 15 and 1.5 ns laser pulses of an intensity in excess of 5 × 109 W/cm2 are capable of dissociating the molecule due to the vibrational shift. Lesser shifts can be used to fine-tune the rovibrational levels and thereby affect collisional resonances by the nonresonant light. The energy shifts due to laser intensities of 109 W/cm2 may be discernible spectroscopically, with a 10 MHz resolution.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2196
IS - 36
JF - Journal of Physical Chemistry A
TI - Fine-tuning molecular energy levels by nonresonant laser pulses
VL - 114
ER -
TY - JOUR
AB - We present an analytic model of the refractive index for matter waves propagating through atomic or molecular gases. The model, which combines the Wentzel-Kramers-Brillouin (WKB) treatment of the long-range attraction with the Fraunhofer model treatment of the short-range repulsion, furnishes a refractive index in compelling agreement with recent experiments of Jacquey [Phys. Rev. Lett.PRLTAO0031-900710.1103/PhysRevLett.98.240405 98, 240405 (2007)] on Li atom matter waves passing through dilute noble gases. We show that the diffractive contribution, which arises from scattering by a two-dimensional "hard core" of the potential, is essential for obtaining a correct imaginary part of the refractive index.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2197
IS - 2
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Multiple scattering of matter waves: An analytic model of the refractive index for atomic and molecular gases
VL - 82
ER -
TY - CONF
AB - Streaming string transducers [1] define (partial) functions from input strings to output strings. A streaming string transducer makes a single pass through the input string and uses a finite set of variables that range over strings from the output alphabet. At every step, the transducer processes an input symbol, and updates all the variables in parallel using assignments whose right-hand-sides are concatenations of output symbols and variables with the restriction that a variable can be used at most once in a right-hand-side expression. It has been shown that streaming string transducers operating on strings over infinite data domains are of interest in algorithmic verification of list-processing programs, as they lead to PSPACE decision procedures for checking pre/post conditions and for checking semantic equivalence, for a well-defined class of heap-manipulating programs. In order to understand the theoretical expressiveness of streaming transducers, we focus on streaming transducers processing strings over finite alphabets, given the existence of a robust and well-studied class of "regular" transductions for this case. Such regular transductions can be defined either by two-way deterministic finite-state transducers, or using a logical MSO-based characterization. Our main result is that the expressiveness of streaming string transducers coincides exactly with this class of regular transductions.
AU - Alur, Rajeev
AU - Cerny, Pavol
ID - 488
TI - Expressiveness of streaming string transducers
VL - 8
ER -
TY - CONF
AB - Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.
AU - Cristau, Julien
AU - David, Claire
AU - Horn, Florian
ID - 489
T2 - Proceedings of GandALF 2010
TI - How do we remember the past in randomised strategies?
VL - 25
ER -
TY - GEN
AB - We present an algorithmic method for the synthesis of concurrent programs that are optimal with respect to quantitative performance measures. The input consists of a sequential sketch, that is, a program that does not contain synchronization constructs, and of a parametric performance model that assigns costs to actions such as locking, context switching, and idling. The quantitative synthesis problem is to automatically introduce synchronization constructs into the sequential sketch so that both correctness is guaranteed and worst-case (or average-case) performance is optimized. Correctness is formalized as race freedom or linearizability.
We show that for worst-case performance, the problem can be modeled
as a 2-player graph game with quantitative (limit-average) objectives, and
for average-case performance, as a 2 1/2 -player graph game (with probabilistic transitions). In both cases, the optimal correct program is derived from an optimal strategy in the corresponding quantitative game. We prove that the respective game problems are computationally expensive (NP-complete), and present several techniques that overcome the theoretical difficulty in cases of concurrent programs of practical interest.
We have implemented a prototype tool and used it for the automatic syn- thesis of programs that access a concurrent list. For certain parameter val- ues, our method automatically synthesizes various classical synchronization schemes for implementing a concurrent list, such as fine-grained locking or a lazy algorithm. For other parameter values, a new, hybrid synchronization style is synthesized, which uses both the lazy approach and coarse-grained locks (instead of standard fine-grained locks). The trade-off occurs because while fine-grained locking tends to decrease the cost that is due to waiting for locks, it increases cache size requirements.
AU - Chatterjee, Krishnendu
AU - Cerny, Pavol
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Singh, Rohit
ID - 5388
SN - 2664-1690
TI - Quantitative synthesis for concurrent programs
ER -
TY - GEN
AB - Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of “fit” or “desirability.” We extend the simulation preorder to the quantitative setting, by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the im- plementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes.
AU - Cerny, Pavol
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
ID - 5389
SN - 2664-1690
TI - Simulation distances
ER -
TY - GEN
AB - The class of ω regular languages provide a robust specification language in verification. Every ω-regular condition can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. In this work we consider the finitary parity and Streett (fairness) conditions. We present the topological, automata-theoretic and logical characterization of finitary languages defined by finitary parity and Streett conditions. We (a) show that the finitary parity and Streett languages are Σ2-complete; (b) present a complete characterization of the expressive power of various classes of automata with finitary and infinitary conditions (in particular we show that non-deterministic finitary parity and Streett automata cannot be determinized to deterministic finitary parity or Streett automata); and (c) show that the languages defined by non-deterministic finitary parity automata exactly characterize the star-free fragment of ωB-regular languages.
AU - Chatterjee, Krishnendu
AU - Fijalkow, Nathanaël
ID - 5390
SN - 2664-1690
TI - Topological, automata-theoretic and logical characterization of finitary languages
ER -
TY - GEN
AB - Concurrent data structures with fine-grained synchronization are notoriously difficult to implement correctly. The difficulty of reasoning about these implementations does not stem from the number of variables or the program size, but rather from the large number of possible interleavings. These implementations are therefore prime candidates for model checking. We introduce an algorithm for verifying linearizability of singly-linked heap-based concurrent data structures. We consider a model consisting of an unbounded heap where each node consists an element from an unbounded data domain, with a restricted set of operations for testing and updating pointers and data elements. Our main result is that linearizability is decidable for programs that invoke a fixed number of methods, possibly in parallel. This decidable fragment covers many of the common implementation techniques — fine-grained locking, lazy synchronization, and lock-free synchronization. We also show how the technique can be used to verify optimistic implementations with the help of programmer annotations. We developed a verification tool CoLT and evaluated it on a representative sample of Java implementations of the concurrent set data structure. The tool verified linearizability of a number of implementations, found a known error in a lock-free imple- mentation and proved that the corrected version is linearizable.
AU - Cerny, Pavol
AU - Radhakrishna, Arjun
AU - Zufferey, Damien
AU - Chaudhuri, Swarat
AU - Alur, Rajeev
ID - 5391
SN - 2664-1690
TI - Model checking of linearizability of concurrent list implementations
ER -
TY - JOUR
AB - It is not well understood how the human Mediator complex, transcription factor IIH and RNA polymerase II (Pol II) work together with activators to initiate transcription. Activator binding alters Mediator structure, yet the functional consequences of such structural shifts remain unknown. The p53 C terminus and its activation domain interact with different Mediator subunits, and we find that each interaction differentially affects Mediator structure; strikingly, distinct p53-Mediator structures differentially affect Pol II activity. Only the p53 activation domain induces the formation of a large pocket domain at the Mediator-Pol II interaction site, and this correlates with activation of stalled Pol II to a productively elongating state. Moreover, we define a Mediator requirement for TFIIH-dependent Pol II C-terminal domain phosphorylation and identify substantial differences in Pol II C-terminal domain processing that correspond to distinct p53-Mediator structural states. Our results define a fundamental mechanism by which p53 activates transcription and suggest that Mediator structural shifts trigger activation of stalled Pol II complexes.
AU - Meyer, Krista
AU - Lin, Shih
AU - Bernecky, Carrie A
AU - Gao, Yuefeng
AU - Taatjes, Dylan
ID - 598
IS - 6
JF - Nature Structural and Molecular Biology
TI - P53 activates transcription by directing structural shifts in Mediator
VL - 17
ER -