Theory Tea - 2010-2011
- maria nefeli
- Kilobyte level
- Posts: 171
- Joined: Tue Nov 28, 2006 4:57 pm
- Location: Κάπου μακριά !
Re: Theory Tea - 2010-2011
Και μια απορία, γιατί με 38.5 πυρετό δεν είμαι και πολύ σίγουρη : όταν λέμε "στην αίθουσα 606" εννοούμε; (στο κτίριο των μεταπτυχιακών λογικά, ε ; )
PS : Αν θες, σου κρατώ σημειώσεις
PS : Αν θες, σου κρατώ σημειώσεις
Ωφελείν ή μη βλάπτειν (Ιπποκράτης)
- enum21
- Venus Former Team Member
- Posts: 5436
- Joined: Mon Feb 16, 2009 9:06 pm
- Academic status: Alumnus/a
- Gender: ♀
- Location: Underworld
Re: Theory Tea - 2010-2011
ναιmaria nefeli wrote:Και μια απορία, γιατί με 38.5 πυρετό δεν είμαι και πολύ σίγουρη : όταν λέμε "στην αίθουσα 606" εννοούμε; (στο κτίριο των μεταπτυχιακών λογικά, ε ; )
PS : Αν θες, σου κρατώ σημειώσεις
- sandra
- Wow! Terabyte level
- Posts: 4917
- Joined: Mon Oct 02, 2006 11:37 am
- Academic status: Alumnus/a
- Gender: ♀
- Location: στη φωλιά μου κοιτώντας ένα χωράφι με στάρι...
Re: Theory Tea - 2010-2011
Αύριο θα συνεχιστεί η ομιλία του κ.Παπαδημητρίου
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.
Από εδώ κι εμπρός θα είσαι για πάντα υπεύθυνος για εκείνο που έχεις ημερώσει.
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
- sandra
- Wow! Terabyte level
- Posts: 4917
- Joined: Mon Oct 02, 2006 11:37 am
- Academic status: Alumnus/a
- Gender: ♀
- Location: στη φωλιά μου κοιτώντας ένα χωράφι με στάρι...
Re: Theory Tea - 2010-2011
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.
Από εδώ κι εμπρός θα είσαι για πάντα υπεύθυνος για εκείνο που έχεις ημερώσει.
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
- darkness
- Kilobyte level
- Posts: 301
- Joined: Fri Jan 30, 2009 1:30 pm
- Academic status: Alumnus/a
- Gender: ♂
Re: Theory Tea - 2010-2011
Το γράφω κι εδώ αν κάποιος δεν το έχει δει:
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.
For science. You monster.
- darkness
- Kilobyte level
- Posts: 301
- Joined: Fri Jan 30, 2009 1:30 pm
- Academic status: Alumnus/a
- Gender: ♂
Re: Theory Tea - 2010-2011
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ý.
For science. You monster.
- darkness
- Kilobyte level
- Posts: 301
- Joined: Fri Jan 30, 2009 1:30 pm
- Academic status: Alumnus/a
- Gender: ♂
Re: Theory Tea - 2010-2011
Για αύριο:
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!
For science. You monster.
- XaviannNJ
- Gbyte level
- Posts: 1413
- Joined: Wed Oct 14, 2009 11:59 am
- Academic status: N>4
- Gender: ♀
- Location: city of insanity....
Re: Theory Tea - 2010-2011
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.
- cypher
- Venus Former Team Member
- Posts: 6207
- Joined: Mon Sep 29, 2008 9:12 pm
- Academic status: Alumnus/a
- Gender: ♂
Re: Theory Tea - 2010-2011
Ειναι το wroclaw αντι για τη.
- darkness
- Kilobyte level
- Posts: 301
- Joined: Fri Jan 30, 2009 1:30 pm
- Academic status: Alumnus/a
- Gender: ♂
Re: Theory Tea - 2010-2011
Ξέρει κανείς αν θα γίνει αύριο; Το χάνουμε λογικά έτσι;Authn thn Paraskeuh tha mas milhsei o k. Papadhmhtriou.
Epistrefoume sthn A36, stis 4.
For science. You monster.
-
- Venus Former Team Member
- Posts: 7561
- Joined: Thu Oct 27, 2005 1:43 pm
- Academic status: Alumnus/a
- Gender: ♂
- Location: Boston, MA
Re: Theory Tea - 2010-2011
Απ' ότι κατάλαβα, δε θα γίνουν τα μαθήματα. Η ανακοίνωση λέει ότι το κτήριο θα είναι κλειστό;
- enum21
- Venus Former Team Member
- Posts: 5436
- Joined: Mon Feb 16, 2009 9:06 pm
- Academic status: Alumnus/a
- Gender: ♀
- Location: Underworld
Re: Theory Tea - 2010-2011
Όχι από ό,τι λέει μόνο τα μαθήματα και οι Διοικητικές υπηρεσίες του Πανεπιστημίου δεν θα λειτουργήσουν.
- maria nefeli
- Kilobyte level
- Posts: 171
- Joined: Tue Nov 28, 2006 4:57 pm
- Location: Κάπου μακριά !
Re: Theory Tea - 2010-2011
Ο κύριος Μαρκάκης έστειλε οτι:
[Theorygroup] Mataiwsh omilias Papadimitriou
Dedomenou oti ekleise h sxolh gia shmera, h omilia tou k. Papadimitriou tha ginei thn allh Paraskeuh
Ωφελείν ή μη βλάπτειν (Ιπποκράτης)
- enum21
- Venus Former Team Member
- Posts: 5436
- Joined: Mon Feb 16, 2009 9:06 pm
- Academic status: Alumnus/a
- Gender: ♀
- Location: Underworld
Re: Theory Tea - 2010-2011
Ypenthumizw oti shmera tha mas milhsei o k. Papadimitriou stis 4, sthn
aithousa A41
- mpatsis
- Gbyte level
- Posts: 1030
- Joined: Mon Nov 03, 2008 8:18 pm
- Academic status: MSc
- Gender: ♂
- Location: Riding the train of thought!!!
Re: Theory Tea - 2010-2011
Έχουμε κάτι για αύριο?
I'm Starting With The Man In The Mirror. I'm Asking Him To Change His Ways...
Aueb's NLP Group!
May the foss be with you!!!
Aueb's NLP Group!
May the foss be with you!!!
-
- Venus Former Team Member
- Posts: 7561
- Joined: Thu Oct 27, 2005 1:43 pm
- Academic status: Alumnus/a
- Gender: ♂
- Location: Boston, MA
Re: Theory Tea - 2010-2011
elsupreme on the decksAuth 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)
Re: Theory Tea - 2010-2011
"Must float like lotus on river... and kill old lady!"
- PaP
- Venus Project Founder
- Posts: 1077
- Joined: Wed Apr 21, 2004 12:06 am
- Academic status: Alumnus/a
- Location: San Francisco
- Contact:
Re: Theory Tea - 2010-2011
Hey guys, παίζει για την Πέμπτη αυτή η ομιλία;
Γιατί δε τη βλέπω πλεόν στο site.Crowdsourcing using Amazon Mechanical Turk: Quality Management and Scalability at AUEB
Re: Theory Tea - 2010-2011
Για Theory Tea μιλάς ?
"Must float like lotus on river... and kill old lady!"
Re: Theory Tea - 2010-2011
Εδώ πάντως http://pages.cs.aueb.gr/othersites/Theo ... talks.html δεν είναι. Δεν ξέρω παραπάνω δυστυχώς...
"Must float like lotus on river... and kill old lady!"
- Gewitter
- Venus Former Team Member
- Posts: 1609
- Joined: Mon Jan 19, 2009 11:42 am
- Academic status: PhD
- Gender: ♀
Re: Theory Tea - 2010-2011
πιθανόν πρόκειται για διαφορετική ομιλία/σεμινάριο/ομάδα..
- Spoiler: εμφάνιση/απόκρυψη