Seminar of the Department of Physics

[marzolino at ts.infn.it]

Dear professors, researchers and students

I would like to announce the seminar held by Prof. Antonello Scardicchio on
Thursday, 13 May, at 3pm in Room 204 of the Department of Physics
(Leonardo Building).
Everyone who is interested is welcome.

TITLE:
Typical case complexity in QSAT formulas and the most constraining
classical SAT formulas


ABSTRACT:
Quantum Satisfiability (QSAT) is a decision problem introduced by S.Bravyi
in 2006 which is believed to be difficult for a quantum computer. I will
present some results on the statistics of random quantum formulas, show
the presence of two phase transitions (one SAT-UNSAT and one
difficult-easy) and present an interesting connection between this problem
and that of finding the most constraining classical satisfiability
formulas on random graphs.


Best regards,
Ugo Marzolino.


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.