Page 3 of 5

Re: Theory Tea - 2010-2011

Posted: Wed Dec 22, 2010 5:47 pm
by maria nefeli
Και μια απορία, γιατί με 38.5 πυρετό δεν είμαι και πολύ σίγουρη :oops: : όταν λέμε "στην αίθουσα 606" εννοούμε; (στο κτίριο των μεταπτυχιακών λογικά, ε ; )

PS : Αν θες, σου κρατώ σημειώσεις ;)

Re: Theory Tea - 2010-2011

Posted: Wed Dec 22, 2010 5:47 pm
by enum21
maria nefeli wrote:Και μια απορία, γιατί με 38.5 πυρετό δεν είμαι και πολύ σίγουρη :oops: : όταν λέμε "στην αίθουσα 606" εννοούμε; (στο κτίριο των μεταπτυχιακών λογικά, ε ; )

PS : Αν θες, σου κρατώ σημειώσεις ;)
ναι

Re: Theory Tea - 2010-2011

Posted: Thu Jan 13, 2011 11:04 am
by sandra
Αύριο θα συνεχιστεί η ομιλία του κ.Παπαδημητρίου
Kalhspera se olous kai kalh xronia!

Authn thn Paraskeuh, sta plaisia tou metaptuxiakou mathimatos
"Domes Dedomenwn kai Analush Algorithmwn" tha milhsei o Christos Papadimitriou
me thema "Olikes (total) synarthseis sto NP kai isorropia kata Nash".

H omilia tha ginei sto ktirio Euelpidwn, sthn aithousa 601, kai wra 3:30-6.

Re: Theory Tea - 2010-2011

Posted: Thu Jan 20, 2011 10:24 am
by sandra
Ws sunexeia ths omilias tou Xristou Papadhmhtriou thn prohgoumenh ebdomada, tha milhsw authn thn Paraskeuh gia
"Algorithms for computing ε-Nash equilibria",
to thema dhladh sto opoio anaferthikame periliptika sto telos thn prohgoumenh Paraskeuh.

Epistrefoume sth sinithismenh aithousa kai wra: A36 stis 4.

Re: Theory Tea - 2010-2011

Posted: Fri Feb 11, 2011 12:57 am
by darkness
Το γράφω κι εδώ αν κάποιος δεν το έχει δει:
Tha exoume thn ekshs omilia thn Paraskeuh sto theory tea.
A36 stis 4.

Speaker: Maria Polukarov, University of Southampton
Title: Congestion-Averse Games

Abstract:


Congestion games---in which players strategically choose from a set of
``resources'' and derive utilities that depend on the congestion on each
resource---are important in a wide range of applications. However, to
date, such games have been constrained to use utility functions that are
linear sums with respect to resources. To remove this restriction, we consider
a generalisation to the case where a player's payoff can be given by any
real-valued function over the set of possible congestion vectors. Under weak
assumptions on the structure of player strategy spaces, we constructively prove
the existence of a pure strategy equilibrium for the very wide class of these
generalised games in which player utility functions are
congestion-averse---i.e.,
monotonic, submodular and independent of irrelevant alternatives.
Although, as we
show, these games do not admit a generalised ordinal potential function
(and hence---the finite improvement property), any such game does possess
a Nash equilibrium in pure strategies. A polynomial time algorithm for computing
such an equilibrium is presented. Moreover, we show that if a player
utility function does not satisfy any one of the congestion-averse
conditions, then a pure strategy equilibrium need not to exist, and in fact
the determination of whether or not a game has a pure strategy Nash
equilibrium is NP-complete. We further prove analogous results for our
assumed properties of player strategy spaces, thus showing that current
assumptions on strategy and utility structures in this model cannot be
relaxed anymore.

Re: Theory Tea - 2010-2011

Posted: Thu Feb 17, 2011 11:14 pm
by darkness
Aythn thn Paraskeuh tha mas milhsei o Panagiwths Xeilarhs apo to Ben Gurion
University.
Opws panta A36 stis 4.

Name: Panagiotis Cheilaris

Affiliation:
Center for Advanced Studies in Mathematics,
Ben Gurion University

Title: The potential to improve the choice

Abstract:
---------

Given a hypergraph H=(V,E), a vertex coloring C:V->IN is said to be unique-maximum (um for short) if for every hyperedge S in E, the maximum color occurring in S, i.e. max{C(v)|v in S}, occurs in exactly one vertex of S. Um-coloring has several applications, e.g., in frequency assignment in cellular networks.

We study the list version of um-coloring. Given is a hypergraph H=(V,E) and a family L of |V| lists of colors, where each vertex in V is associated with a list. We denote the list associated with v by L(v). We say that hypergraph H admits a um-coloring from family L if there exists a um-coloring C such that C(v) in L(v) for every v in V. Intuitively, each v can only be colored with colors from its list L(v). The minimum integer x such that "for any family L with |L(v)| >= x for every v in V, H admits a um-coloring from L" is called the um-choice number of H and is denoted by chum(H).

We prove that if a hypergraph H with n vertices is hereditarily k-colorable (in the classic non-monochromatic sense), where k is a constant, then chum(H) = O(logn) and this bound is asymptotically tight. The proof is constructive and uses a suitable potential function for constructing a um-coloring and analyzing the size of lists needed. As a corollary, we get algorithms for um-coloring hypergraphs induced by geometric shapes, given lists of colors of logarithmic size.

Joint work with Shakhar Smorodinsky and Marek Sulovský.

Re: Theory Tea - 2010-2011

Posted: Thu Feb 24, 2011 10:03 pm
by darkness
Για αύριο:
Authn thn paraskeyh sumplhrwnetai 1 xronos apo tote pou ksekinhsame to
seminario auto, opote tha dwsoume ki ena pio eortastiko tono:)
Tha exoume 2 syntomes paroysiaseis apo tis omades poy hr8an prwtes ston
programmatistiko diagwnismo toy ma8hmatos algori8mwn toy metaptyxiakoy
programmatos
episthmhs ypologistwn. O diagwnismos htan na xrhsimopoihsoyn
opoiadhpote texnikh antimetwpishs NP-plhrothtas gia na lysoyn to
NP-complete problhma eyreshs ypografhmatos megistoy ba8moy ka8ws kai
na broyn dyskola stigmiotypa toy problhmatos aytoy.
Gia perissoteres leptomereies deite edw:
http://eclass.aueb.gr/modules/document/ ... /mmeby.pdf

Epishs an prolabainoyme o bassilhs triantafyloy (ths idias takshs) 8a
mas milhsei syntoma gia thn polyplokothta toy factoring.

A36 stis 4!

Re: Theory Tea - 2010-2011

Posted: Tue Mar 01, 2011 1:57 am
by XaviannNJ
Thn Paraskeuh tha mas milhsei o Jarek Byrka apo to panepisthmio ths Wroclaw, sthn Polwnia.
O Jarek einai epikouros kathighths sthn Wroclaw kai h ergasia gia thn opoia tha mas milhsei phre perusi to kalutero brabeio sto sunedrio STOC 2010.

H omilia einai stis 4 ALLA h aithousa tha einai h A41 anti gia A36.

Title: An Improved LP-based Approximation for Steiner Tree
Abstract:
---
The Steiner tree problem is: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from $2$ to the current best $1.55$ [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than $2$ [Vazirani,Rajagopalan-SODA'99].

In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, \emph{iterative randomized rounding} technique. We consider a directed-component cut relaxation for the $k$-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the ampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most $\ln(4)$ times the cost of an optimal $k$-restricted Steiner tree. This directly implies a $\ln(4)+\varepsilon<1.39$ approximation for Steiner tree. As a byproduct of our analysis, we also show that the integrality gap of our LP is at most $1.55$, hence answering the mentioned open question.

In the talk I will describe a slightly weaker, but less technical argument that provides 1.5-approximation for Steiner tree.

Re: Theory Tea - 2010-2011

Posted: Tue Mar 01, 2011 1:58 am
by cypher
Ειναι το wroclaw αντι για τη. :-p :-p

Re: Theory Tea - 2010-2011

Posted: Thu Mar 10, 2011 10:25 pm
by darkness
Authn thn Paraskeuh tha mas milhsei o k. Papadhmhtriou.
Epistrefoume sthn A36, stis 4.
Ξέρει κανείς αν θα γίνει αύριο; Το χάνουμε λογικά έτσι; :???:

Re: Theory Tea - 2010-2011

Posted: Thu Mar 10, 2011 10:46 pm
by The Punisher
Απ' ότι κατάλαβα, δε θα γίνουν τα μαθήματα. Η ανακοίνωση λέει ότι το κτήριο θα είναι κλειστό;

Re: Theory Tea - 2010-2011

Posted: Thu Mar 10, 2011 10:48 pm
by enum21
Όχι από ό,τι λέει μόνο τα μαθήματα και οι Διοικητικές υπηρεσίες του Πανεπιστημίου δεν θα λειτουργήσουν.

Re: Theory Tea - 2010-2011

Posted: Fri Mar 11, 2011 10:59 am
by maria nefeli
Ο κύριος Μαρκάκης έστειλε οτι:
[Theorygroup] Mataiwsh omilias Papadimitriou

Dedomenou oti ekleise h sxolh gia shmera, h omilia tou k. Papadimitriou tha ginei thn allh Paraskeuh

Re: Theory Tea - 2010-2011

Posted: Fri Mar 18, 2011 12:04 pm
by enum21
Ypenthumizw oti shmera tha mas milhsei o k. Papadimitriou stis 4, sthn
aithousa A41

Re: Theory Tea - 2010-2011

Posted: Thu Mar 31, 2011 5:18 pm
by mpatsis
Έχουμε κάτι για αύριο?

Re: Theory Tea - 2010-2011

Posted: Thu Mar 31, 2011 5:25 pm
by The Punisher
Auth thn Paraskeuh tha mas milhsei o Ioannis Sorokos gia thn ptuxiakh tou ergasia pou afora
"coalitional manipulation under the maximin voting rule",
dhladh pws synaspismoi apo voters mporoun na ephreazoun to apotelesma mias pshfoforias se kapoia voting systems,

H parousiash tha einai sthn A41, stis 4, (auto to elksamhno den tha ksanakanoume sthn A36, kathws mas prolabe allo seminario)
elsupreme on the decks :-D

Re: Theory Tea - 2010-2011

Posted: Thu Mar 31, 2011 9:14 pm
by elsupreme
:-D

Re: Theory Tea - 2010-2011

Posted: Mon Apr 04, 2011 11:20 am
by PaP
Hey guys, παίζει για την Πέμπτη αυτή η ομιλία;
Crowdsourcing using Amazon Mechanical Turk: Quality Management and Scalability at AUEB
Γιατί δε τη βλέπω πλεόν στο site.

Re: Theory Tea - 2010-2011

Posted: Mon Apr 04, 2011 11:39 am
by elsupreme
Για Theory Tea μιλάς ?

Re: Theory Tea - 2010-2011

Posted: Mon Apr 04, 2011 1:08 pm
by PaP
Νομίζω πως ναί, αλλού είναι;

Re: Theory Tea - 2010-2011

Posted: Mon Apr 04, 2011 3:51 pm
by elsupreme
Εδώ πάντως http://pages.cs.aueb.gr/othersites/Theo ... talks.html δεν είναι. Δεν ξέρω παραπάνω δυστυχώς...

Re: Theory Tea - 2010-2011

Posted: Mon Apr 04, 2011 3:54 pm
by Gewitter
πιθανόν πρόκειται για διαφορετική ομιλία/σεμινάριο/ομάδα.. :smt001