Font size: Αα Αα Αα hide gadgets
You are here: Defenses » September 2016 » Aggeliki Chalki Anonymously browsing from at 11:31:46, 21-04-2019. login
download defense details: { pdf }

MSc thesis defense presentation

Aggeliki Chalki defends her MSc thesis.

Date: Monday, 12 Sep 2016
Time: 17:00
Location: School of Electrical and Computer Engineering (old buildings), 1.1.31
Thesis title: Counting below #P: Classes, problems and Descriptive Complexity

Thesis abstract

In this thesis, we study counting classes that lie below #P. One approach, the most regular in Computational Complexity Theory, is the machine-based approach. Classes like #L, span-L and TotP, #PE are defined establishing space and time restrictions on Turing machine's computational resources.

A second approach is Descriptive Complexity's approach. It characterizes complexity classes by the type of logic needed to express the languages in them. Classes deriving from this viewpoint, like #FO, #RHΠ_1, #RΣ_2, are equivalent to #P, the class of AP-interriducible problems to #BIS, and some subclass of the problems owning an FPRAS.

A great objective of such an investigation is to gain an understanding of how “efficient counting” relates to these already defined classes. By “efficient counting” we mean counting solutions of a problem using a polynomial time algorithm or an FPRAS.

Many other interesting properties of the classes considered and their problems have been examined. For example alternative definitions of counting classes using relation-based operators, and the computational difficulty of complete problems, since complete problems capture the difficulty of the corresponding class. Moreover, in Section 3.5 we define the log-space analog of the class TotP and explore how and to what extent results can be transferred from polynomial time to logarithmic space computation.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2019 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.