Phone: 054-2322706
School for Computer Science, Faculty of Exact Science
I am interested in computational complexity in general and quantum computation in particular. Among the results I have obtained in quantum complexity I would mention:
- Random access codes, (together with Ambainis, Nayak and Vazirani) where we defined and studied the extent to which one can (or cannot) compactly encode classical information in quantum messages in a way that allows answering local queries.
- The first provable quantum coin tossing protocol (with Aharonov, Vazirani and Yao)
- Proving that QED is QSZK-complete (together with Ben-Aroya)
- Showing that Trevisan's extractor is quantum proof. This was the first proof for a short seed quantum extractor and it was later improved and simplified.
- Showing a BQL algorithm (approximately) inverting Hermitian matrices. This is the first problem that seems to be in BQL but not in BPL.
In general, I am interested in
- the power of quantum classes (recently, I looked at the power of QIP(2)),
- in quantum-proof extractors, and,
- in the power of BQL, the space bounded quantum class.
