Venus AUEB Forum

ΣΕΜΙΝΑΡΙΟ ΛΟΓΙΚΗΣ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ


Ομιλητής: Γ. Μοσχοβάκης, ΜΠΛΑ και UCLA
Θέμα: Borel determinacy
Ημερομηνία: Παρασκευή, 29-6-2007, 6 μ.μ.
Αίθουσα: Γ33 Τμήματος Μαθηματικών


ΠΕΡΙΛΗΨΗ

Donald A. Martin's proof of the determinacy of Borel sets in 1975 was a critical event in the development of set theory, and it influenced fundamentally the subsequent development of the field. My aim in this talk is to describe the state of affairs at the
time of Martin's proof; explain the result and the method of Martin's (second) proof; and discuss its foundational significance. This is an expository and historical talk, and it is only towards the end that I will turn (briefly) to some new observations on the interesting relation between Borel determinacy and the Axiom of Choice.

ΣΕΜΙΝΑΡΙΟ ΛΟΓΙΚΗΣ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ


Ομιλητής: A. S. Kechris, California Institute of Technology
Θέμα: Set Theory and Dynamical Systems
Ημερομηνία: Παρασκευή, 13-7-2007, 6 μ.μ.
Αίθουσα: Γ33 Τμήματος Μαθηματικών (νέο κτήριο)


ΠΕΡΙΛΗΨΗ

In this talk, I will give an introduction to some recent work in set theory, whose goal is a theory of complexity of classification problems in mathematics, and discuss its connections with aspects of dynamical systems and in particular rigidity phenomena in the context of ergodic theory.

ΣΕΜΙΝΑΡΙΟ ΛΟΓΙΚΗΣ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ


Ομιλητής: A. S. Kechris, California Institute of Technology
Θέμα: Set Theory and Dynamical Systems
Ημερομηνία: Παρασκευή, 13-7-2007, 6 μ.μ.
Αίθουσα: Γ33 Τμήματος Μαθηματικών (νέο κτήριο)

Να συνεχίσω να ποστάρω επί του θέματος;;

ΣΕΜΙΝΑΡΙΟ ΛΟΓΙΚΗΣ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ


Ομιλητής: Ε. Ζάχος, Ε. Μ. Π.
Θέμα: Hierarchies of complexity classes
Ημερομηνία: Παρασκευή, 20-7-2007, 6 μ.μ.
Αίθουσα: Γ33 Τμήματος Μαθηματικών


ΠΕΡΙΛΗΨΗ

Computational Complexity deals with the classification of problems into classes of hardness, called complexity classes. Complexity classes are defined by modifying
structural parameters, such as the model of computation (Turing Machine, RAM, Finite Automaton, PDA, LBA, PRAM, Monotone Circuits), the mode of computation (deterministic, nondeterministic, probabilistic, alternating, uniform parallel), the kind of the automaton (Decider, Acceptor, Generator, Transducer, Counting), the resources (time, space, # of processors, circuit size and depth) and others: randomness, oracles, interactivity, promise, advice, operators. Some of the most important questions concern inclusion and separation relations among complexity classes. This line of research has led to numerous definitions of complexity classes, as well as inclusion sequences of classes known as "complexity hierarchies". We will review some of the most interesting ones, including the Polynomial-Time Hierarchy, a Counting Hierarchy and an Approximability Hierarchy.

AnINffected wrote:Πού βρίσκεται η αίθουσα Γ33 του τμ.Μαθηματικών (σε ποιά περιοχή);

Πανεπιστημιούπολη (Ζωγράφου) --> Στάση Γεωλογίας(για το εσωτερικό
                                                                λεωφορειάκι)
                             --> Κτήριο Μαθηματικού(ακριβώς απέναντι) 
                             --> Πτέρυγα Γ
                             --> 2ος ή 3ος όροφος νομίζω 
                                 (αλλά έχει και χάρτη και φοιτητές για 
                                  ερωτήσεις  ώς προς την ακριβή θέση της
                                  αίθουσας....ξεχνάω δυστυχώς εύκολα, 
                                  μέρη & δρόμους) 

ΣΕΜΙΝΑΡΙΟ ΛΟΓΙΚΗΣ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ


Ομιλητής: Fedor V. Fomin, University of Bergen (Norway)
Θέμα: Exact algorithms for NP-hard problems
Ημερομηνία: Παρασκευή, 12-10-2007, 6 μ.μ.
Αίθουσα: Γ33 Τμήματος Μαθηματικών



ΠΕΡΙΛΗΨΗ

It is a common belief that exponential time algorithms are unavoidable when we want to find an exact solution of an NP hard problem. The design of exact (moderately exponential) algorithms has a long history dating back to Held and Karp's paper on the traveling salesman problem in the early sixties. The last years have seen an emerging interest in constructing exact algorithms for combinatorial problems like Coloring, Max-Cut, 3-SAT, Minimum Dominating Set, Treewidth, and Maximum Independent Set. In this talk we overview some recent results and techniques in the area of exact algorithms and conclude with several open problems.

AXIOMS FOR ELEMENTARY ALGORITHMS, AND THE DERIVATION OF ABSOLUTE LOWER BOUNDS

YIANNIS N. MOSCHOVAKIS

Abstract. In previous work (joint with Lou van den Dries and reported
in the ΜΠΛΑ seminar), we have established lower bounds for arithmetical
problems which, we claimed, hold for all algorithms from specified prim-
itives, based on a Church-Turing Thesis for algorithms. My purpose in
this lecture is to show how these lower bounds can be derived from four
very simple axioms for elementary algorithms, which are both plausible
and easy to verify for all the standard computational models.

DEPARTMENT OF MATHEMATICS, UCLA, and ΜΠΛΑ

Unless otherwise stated, all lectures take place in room Γ33 of the Mathematics Department, at 6p.m..