Theory Tea - 2010-2011

Εδώ μπορείτε να ενημερώνετε ή να ενημερώνεστε για τη διοργάνωση διαφόρων συνεδρίων και σεμιναρίων.
User avatar
maria nefeli
Kilobyte level
Kilobyte level
Posts: 171
Joined: Tue Nov 28, 2006 4:57 pm
Location: Κάπου μακριά !

Re: Theory Tea - 2010-2011

Post by maria nefeli » Wed Dec 22, 2010 5:47 pm

Και μια απορία, γιατί με 38.5 πυρετό δεν είμαι και πολύ σίγουρη :oops: : όταν λέμε "στην αίθουσα 606" εννοούμε; (στο κτίριο των μεταπτυχιακών λογικά, ε ; )

PS : Αν θες, σου κρατώ σημειώσεις ;)
Ωφελείν ή μη βλάπτειν (Ιπποκράτης)
User avatar
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

Post by enum21 » Wed Dec 22, 2010 5:47 pm

maria nefeli wrote:Και μια απορία, γιατί με 38.5 πυρετό δεν είμαι και πολύ σίγουρη :oops: : όταν λέμε "στην αίθουσα 606" εννοούμε; (στο κτίριο των μεταπτυχιακών λογικά, ε ; )

PS : Αν θες, σου κρατώ σημειώσεις ;)
ναι
User avatar
sandra
Wow! Terabyte level
Wow! Terabyte level
Posts: 4917
Joined: Mon Oct 02, 2006 11:37 am
Academic status: Alumnus/a
Gender:
Location: στη φωλιά μου κοιτώντας ένα χωράφι με στάρι...

Re: Theory Tea - 2010-2011

Post by sandra » Thu Jan 13, 2011 11:04 am

Αύριο θα συνεχιστεί η ομιλία του κ.Παπαδημητρίου
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.
Από εδώ κι εμπρός θα είσαι για πάντα υπεύθυνος για εκείνο που έχεις ημερώσει.
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
User avatar
sandra
Wow! Terabyte level
Wow! Terabyte level
Posts: 4917
Joined: Mon Oct 02, 2006 11:37 am
Academic status: Alumnus/a
Gender:
Location: στη φωλιά μου κοιτώντας ένα χωράφι με στάρι...

Re: Theory Tea - 2010-2011

Post by sandra » Thu Jan 20, 2011 10:24 am

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.
Από εδώ κι εμπρός θα είσαι για πάντα υπεύθυνος για εκείνο που έχεις ημερώσει.
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
User avatar
darkness
Kilobyte level
Kilobyte level
Posts: 301
Joined: Fri Jan 30, 2009 1:30 pm
Academic status: Alumnus/a
Gender:

Re: Theory Tea - 2010-2011

Post by darkness » Fri Feb 11, 2011 12:57 am

Το γράφω κι εδώ αν κάποιος δεν το έχει δει:
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.
User avatar
darkness
Kilobyte level
Kilobyte level
Posts: 301
Joined: Fri Jan 30, 2009 1:30 pm
Academic status: Alumnus/a
Gender:

Re: Theory Tea - 2010-2011

Post by darkness » Thu Feb 17, 2011 11:14 pm

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.
User avatar
darkness
Kilobyte level
Kilobyte level
Posts: 301
Joined: Fri Jan 30, 2009 1:30 pm
Academic status: Alumnus/a
Gender:

Re: Theory Tea - 2010-2011

Post by darkness » Thu Feb 24, 2011 10:03 pm

Για αύριο:
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.
User avatar
XaviannNJ
Gbyte level
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

Post by XaviannNJ » Tue Mar 01, 2011 1:57 am

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.
Cause we all live under the same sun......

http://www.youtube.com/watch?v=MwyXnft6ZVk
User avatar
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

Post by cypher » Tue Mar 01, 2011 1:58 am

Ειναι το wroclaw αντι για τη. :-p :-p
ImageImageImageImageImageImageImage
User avatar
darkness
Kilobyte level
Kilobyte level
Posts: 301
Joined: Fri Jan 30, 2009 1:30 pm
Academic status: Alumnus/a
Gender:

Re: Theory Tea - 2010-2011

Post by darkness » Thu Mar 10, 2011 10:25 pm

Authn thn Paraskeuh tha mas milhsei o k. Papadhmhtriou.
Epistrefoume sthn A36, stis 4.
Ξέρει κανείς αν θα γίνει αύριο; Το χάνουμε λογικά έτσι; :???:
For science. You monster.
The Punisher
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

Post by The Punisher » Thu Mar 10, 2011 10:46 pm

Απ' ότι κατάλαβα, δε θα γίνουν τα μαθήματα. Η ανακοίνωση λέει ότι το κτήριο θα είναι κλειστό;
User avatar
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

Post by enum21 » Thu Mar 10, 2011 10:48 pm

Όχι από ό,τι λέει μόνο τα μαθήματα και οι Διοικητικές υπηρεσίες του Πανεπιστημίου δεν θα λειτουργήσουν.
User avatar
maria nefeli
Kilobyte level
Kilobyte level
Posts: 171
Joined: Tue Nov 28, 2006 4:57 pm
Location: Κάπου μακριά !

Re: Theory Tea - 2010-2011

Post by maria nefeli » Fri Mar 11, 2011 10:59 am

Ο κύριος Μαρκάκης έστειλε οτι:
[Theorygroup] Mataiwsh omilias Papadimitriou

Dedomenou oti ekleise h sxolh gia shmera, h omilia tou k. Papadimitriou tha ginei thn allh Paraskeuh
Ωφελείν ή μη βλάπτειν (Ιπποκράτης)
User avatar
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

Post by enum21 » Fri Mar 18, 2011 12:04 pm

Ypenthumizw oti shmera tha mas milhsei o k. Papadimitriou stis 4, sthn
aithousa A41
User avatar
mpatsis
Gbyte level
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

Post by mpatsis » Thu Mar 31, 2011 5:18 pm

Έχουμε κάτι για αύριο?
I'm Starting With The Man In The Mirror. I'm Asking Him To Change His Ways...
Aueb's NLP Group!
Image
Image May the foss be with you!!!
The Punisher
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

Post by The Punisher » Thu Mar 31, 2011 5:25 pm

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
User avatar
elsupreme
Gbyte level
Gbyte level
Posts: 1573
Joined: Mon Nov 21, 2005 10:16 pm
Academic status: N>4
Gender:

Re: Theory Tea - 2010-2011

Post by elsupreme » Thu Mar 31, 2011 9:14 pm

:-D
"Must float like lotus on river... and kill old lady!"
User avatar
PaP
Venus Project Founder
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

Post by PaP » Mon Apr 04, 2011 11:20 am

Hey guys, παίζει για την Πέμπτη αυτή η ομιλία;
Crowdsourcing using Amazon Mechanical Turk: Quality Management and Scalability at AUEB
Γιατί δε τη βλέπω πλεόν στο site.
User avatar
elsupreme
Gbyte level
Gbyte level
Posts: 1573
Joined: Mon Nov 21, 2005 10:16 pm
Academic status: N>4
Gender:

Re: Theory Tea - 2010-2011

Post by elsupreme » Mon Apr 04, 2011 11:39 am

Για Theory Tea μιλάς ?
"Must float like lotus on river... and kill old lady!"
User avatar
PaP
Venus Project Founder
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

Post by PaP » Mon Apr 04, 2011 1:08 pm

Νομίζω πως ναί, αλλού είναι;
User avatar
elsupreme
Gbyte level
Gbyte level
Posts: 1573
Joined: Mon Nov 21, 2005 10:16 pm
Academic status: N>4
Gender:

Re: Theory Tea - 2010-2011

Post by elsupreme » Mon Apr 04, 2011 3:51 pm

Εδώ πάντως http://pages.cs.aueb.gr/othersites/Theo ... talks.html δεν είναι. Δεν ξέρω παραπάνω δυστυχώς...
"Must float like lotus on river... and kill old lady!"
User avatar
Gewitter
Venus Former Team Member
Posts: 1609
Joined: Mon Jan 19, 2009 11:42 am
Academic status: PhD
Gender:

Re: Theory Tea - 2010-2011

Post by Gewitter » Mon Apr 04, 2011 3:54 pm

πιθανόν πρόκειται για διαφορετική ομιλία/σεμινάριο/ομάδα.. :smt001
Spoiler: εμφάνιση/απόκρυψη
[i][b][color=#004080]No,no...Listen...He said that if they dug his father's body up, it would be gone. They planted a seed over his grave. The seed became a tree. Moses said his father became a part of that tree. He grew into the wood, into the bloom. And when a sparrow ate the tree's fruit, his father flew with the birds. He said... death was his father's road to awe!.[/color][/i][/b]
Post Reply

Return to “Συνέδρια - Σεμινάρια”