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).
CQT PhD Thesis Oral Defence by Markus Baden
Date/Time: Friday, 26 Sep at 9:00 pm
Venue: CQT Level 3 Conference Room, S15-03-18
Title: Quantum optics with cavity-assisted Raman transition
Abstract: We demonstrate that cavity-assisted Raman transitions between hyperfine ground states are a flexible way to create effective atom-photon interactions. We use them to create an effective Tavis-Cummings model and an effective Dicke model. In both
situation we have full control over all model parameters. In the Tavis-Cummings
model we reach strong coupling and observe a normal mode splitting in the cavity
transmission around the dispersively shifted cavity resonance. In the Dicke model we
reach the regime of the phase transition and observe the onset of superradiant
scattering into the cavity above critical coupling.