Prof. Amnon Ta-Shma

amnon.tashma@gmail.com

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:

  1. 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.
  2. The first provable quantum coin tossing protocol (with Aharonov, Vazirani and Yao)
  3. Proving that QED is QSZK-complete (together with Ben-Aroya)
  4. 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.
  5. 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.
Tel Aviv University, P.O. Box 39040, Tel Aviv 6997801, Israel
UI/UX Basch_Interactive