- CQT CS Talk by Aarthi Sundaram, CQT — Wed 03 Sep, 2:00 PM
CQT CS Talk by Aarthi Sundaram, CQT Date/Time: Wednesday, 03 Sep at 2:00 pm Venue: CQT Seminar Room, S15-03-15
Title: On the complexity of Trial and Error for Constraint Satisfaction Problems
Abstract: In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying. In this paper we initiate a systematic study of constraint satisfaction problems in the trial and error model. To achieve this, we first adopt a formal framework for CSPs, and based on this framework we define several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle, under a broad class of parameters. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another, potentially harder CSP in the normal setting, such that their complexities are polynomial time equivalent. This in principle transfers the study of a large class of hidden CSPs, possibly with a promise on the instances, to the study of CSPs in the normal setting. We then apply the transfer theorems to get polynomial-time algorithms or hardness results for hidden CSPs, including satisfaction problems, monotone graph properties, isomorphism problems, and the exact version of the Unique Games problem. - CQT Colloquium by Guenter Werth, Johannes Gutenberg University, Mainz/Germany — Thu 04 Sep, 4:00 PM
CQT Colloquium by Guenter Werth, Johannes Gutenberg University, Mainz/Germany Date/Time: Thursday, 04 Sep at 4:00 pm Venue: CQT Seminar Room, S15-03-15
Title: A single ion in a Penning Trap: Test of QED and a new value for the electronÂ´s mass
Abstract: The magnetic moment of the electron bound in hydrogen-like ions has been measured with high precision. We perform Zeeman-spectroscopy using single ions confined in a triple-Penning trap. The results are compared with QED calculations and represent to date the most precise QED test in bound systems. From a comparison of theory and experiment in C5+ where QED contributions are small and well known, we derive a value for the electronÂ´s atomic mass which is more than one order of magnitude more precise than previously known.
References: S. Sturm et al., g Factor of Hydrogen-like 28Si13+, Phys. Rev. Lett. 107, 023002 (2011) S. Sturm et a,, High precision measurement of the atomic mass of the electron, Nature 506, 467 (2014) - CQT Talk by Lopez Mago Dorilian , ETH — Tue 09 Sep, 4:00 PM
CQT Talk by Lopez Mago Dorilian , ETH Date/Time: Tuesday, 09 Sep at 4:00 pm Venue: CQT Level 3 Seminar Room, S15-03-15
Title: Quantum-Optical Coherence Tomography
Abstract: Quantum-Optical Coherence Tomography (QOCT) combines the correlation properties of frequency-entangled photon pairs with the principles of optical coherence tomography. Compared with its classical counterpart, QOCT has several advantages such as resolution enhancement and dispersion-free measurements. QOCT has gained interest because of its potential applications. However, the current configuration of QOCT imposes practical limitations. QOCT implements a Hong-Ou-Mandel (HOM) interferometer and uses entangled photons generated by Spontaneous Parametric Down-Conversion (SPDC). The HOM interferometer requires non-collinear photon pairs. This requirement complicates the alignment and balancing of the interferometer arms. In addition, SPDC sources with non-collinear emission are highly inefficient. In this work, we demonstrate the implementation of QOCT with collinear down-converted photons using a Michelson interferometer combined with a coincidence detector. We show th at by Fourier processing the fourth-order interference pattern, we can obtain the same information than with the HOM interferometer. - CQT CS Talk by Ved Prakash, CQT — Wed 17 Sep, 2:00 PM
CQT CS Talk by Ved Prakash, CQT Date/Time: Wednesday, 17 Sep at 2:00 pm Venue: CQT Level 3 Seminar Room, S15-03-15
Title: An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
Abstract: The exact computation of the number of distinct elements (frequency moment F_0) is a fundamental problem in the study of data streaming algorithms. We denote the length of the stream by n where each symbol is drawn from a universe of size m. While it is well known that the moments F_0,F_1,F_2 can be approximated by efficient streaming algorithms, it is easy to see that exact computation of F_0 and F_2 requires space Omega(m). In previous work, Cormode et al. therefore considered a model where the data stream is also processed by a powerful helper, who provides an interactive proof of the result. They gave such protocols with a polylogarithmic number of rounds of communication between helper and verifier for all functions in NC. This number of rounds (O(log^2 m) in the case of F_0) can quickly make such protocols impractical.
Cormode et al. also gave a protocol with log m +1 rounds for the exact computation of F_0 where the space complexity is O(log m log n + log^2 m) but the total communication O(sqrt(n) log m (log n + log m )). They managed to give log m round protocols with polylog(m,n) complexity for many other interesting problems which includes F_2, Inner product and Range-sum, but computing F_0 exactly with polylogarithmic space and communication and O(log m) rounds remained open.
In this work, we give a streaming interactive protocol with log m rounds for exact computation of F_0 using O(log m (log n + (log m)(loglog m))) bits of space and the communication is O(log m (log n + (log^3 m)(loglog m)^2 )). The update time of the verifier per symbol received is O(log^2 m).
More events |