Seminar: Scaled-down Rice's Theorem And Connections With Satisfiability Problem

Shadab Romani
M.Sc. Candidate
Co-supervisors: Dr. Miklos Bartha & Dr. Antonina Kolokolova

Scaled-down Rice's Theorem And Connections With Satisfiability Problem

Wednesday, February 17, 2016, 3:00 pm, Room EN 2022
Department of Computer Science


Abstract

Scaled-down Rice's theorem is a conjecture about the hardness of deciding semantic properties of Boolean circuits. According to this conjecture, having access to succinct description of a circuit does not give any significant computational advantage compared to pure oracle access when we want to decide a property that only depends on the input-output behavior of circuit. We investigate what implications the scaled-down Rice's theorem being true or false have for hardness of satisfiability problem. Additionally, we analyze variants of this conjecture by restricting its original statement to computationally limited sub-classes of general Boolean circuits.

 

Contact

Department of Computer Science

230 Elizabeth Ave

St. John's, NL A1B 3X9 CANADA

Tel: (709) 864-2530

Fax: (709) 864-2552

becomestudent@mun.ca