Theory Tea 2016-2017

[XaviannNJ]

Καλησπέρα σε όλους!
Αύριο ξεκινάνε οι ομιλίες του theory tea για την ακαδημαικη χρονια 2016-2017. Η ομιλια θα πραγματοποιηθεί στην Α36,στις 17.15 από τον κ.Μαρκακη.
Παραθέτω την ανακοίωση του στην συνεχεια:

Καλησπέρα και καλή ακαδημαική χρονιά σε όλους!
Το theory tea ξεκινάει και φέτος αυτή την Παρασκευή, 14/10.
Θα κάνω εγώ την πρώτη ομιλία, πάνω σε μια πρόσφατη δουλειά μας (πληροφορίες παρακάτω), και ως συνήθως θα είμαστε στην αίθουσα Α36, και ώρες 5-7.
Ενημερώστε με αν υπάρχουν κι άλλοι φοιτητές που θέλουν να είναι στη λίστα για να παίρνουν τις ανακοινώσεις καθώς και αν υπάρχουν άτομα που θα ήθελαν να παρουσιάσουν κάτι ή να μας μιλήσουν για προβλήματα στα οποία δουλεύουν και σχετίζονται με θεωρητική πληροφορική.
Ακολουθούν οι πληροφορίες για την ομιλία της Παρασκευής
Αίθουσα Α36, 5:15 μμ,
Title:
Inequity aversion pricing over social networks: Approximation algorithms and hardness results
Abstract:
We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (2013) that captures inequity aversion, i.e., prices offered to neighboring vertices should not be significantly different. We first provide approximation algorithms for a natural class of instances, referred to as the class of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for example, to settings where the seller will only consider a fixed number of discount types or special offers. We then resolve one of the open questions posed in Alon et al., by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be relatively large. Finally, we also provide some extensions on the model, regarding either the allowed set of prices, or the demand type of the clients.
This is joint work with Georgios Amanatidis and Krzysztof Sornat

[XaviannNJ]

Η επόμενη ομιλία θα γίνει αύριο στις 17:00, στην αίθουσα Α36.
Λεπτομέρειες στην συνέχεια

Αυτη την Παρασκευή θα μας μιλήσει ο Γιώργος Μπίρμπας, υποψήφιος διδάκτορας του τμήματος μας, για fair division problems (προβλήματα ανάθεσης αγαθών με βάση κάποια fairness criteria). Θα ξεκινήσει με μια μικρή εισαγωγή για αυτή την κατηγορία προβλημάτων και στη συνέχεια θα παρουσιάσει μια πρόσφατη δημοσίευση μας

Αίθουσα Α36, 17:00

Title: On Truthful Mechanisms for Maximin Share Allocations
Abstract:
We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of n players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem mostly algorithmically, providing constant factor approximation algorithms. In this work we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.

This is joint work with Georgios Amanatidis and Evangelos Markakis

[XaviannNJ]

Αυτή την εβδομάδα δεν θα έχουμε theory tea, λόγω και της αργίας.
Υπάρχει όμως μια σχετική ομιλία την Δευτέρα στο Σεμινάριο του Τμήματος.
Δείτε λεπτομέρειες παρακάτω. Αφορά κβαντική κρυπτογραφία και δεν απαιτείται πρότερη γνώση στο αντικείμενο.

Room A41, at 13:00

Speaker: Iordanis Kerenidis, CNRS - Universite Paris, Diderot


Title: Quantum communications and cryptography

Quantum Information Processing has the potential to revolutionise the future of information and communication technologies. Our long-term vision is a network of quantum and classical devices, where individual agents have the ability to communicate efficiently in a variety of ways with trusted and untrusted parties and securely delegate computational tasks to a number of untrusted large-scale quantum computing servers.

In this talk, I will describe some fundamental results in quantum cryptography, including the existence of unconditionally secure key distribution and the optimal quantum protocols for coin flipping and bit commitment. In addition, I will show examples where quantum communication can be exponentially more efficient than classical communication and also, explain how the study of quantum communication can bring new insight in the study of classical information.

No previous knowledge of quantum information is needed.


CV: Iordanis Kerenidis received his PhD in 2004 from the Computer Science department at the University of California, Berkeley. After a two-year postdoc position at the Massachusetts Institute of Technology, he joined the Centre National de Recherche Scientifique in Paris as a permanent researcher. He is a recipient of an ERC starting grant and he was recently appointed Director of the Paris Centre for Quantum Computing.

[XaviannNJ]

Αυτη την Παρασκευή θα μας μιλήσει ο Γιώργος Αμανατίδης,
υποψήφιος διδάκτορας του τμήματος μας για μια πρόσφατη εργασία μας,

Ως συνηθως, Α36 στις 5

Ακολουθούν οι πληροφορίες για την ομιλία

Title: Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
Abstract:
We study a type of reverse (procurement) auction problems in the presence of budget constraints. The general algorithmic problem is to purchase a set of resources, which come at a cost, so as not to exceed a given budget and at the same time maximize a given valuation function. This framework captures the budgeted version of several well known optimization problems, and when the resources are owned by strategic agents the goal is to design truthful and budget feasible mechanisms, i.e. elicit the true cost of the resources and ensure the payments of the mechanism do not exceed the budget. Budget feasibility introduces more challenges in mechanism design, and we study instantiations of this problem for certain classes of submodular and XOS valuation functions. We first obtain mechanisms with an improved approximation ratio for weighted coverage valuations, a special class of submodular functions that has already attracted attention in previous works. We then provide a general scheme for designing randomized and deterministic polynomial time mechanisms for a class of XOS problems. This class contains problems whose feasible set forms an independence system (a more general structure than matroids), and some representative problems include, among others, finding maximum weighted matchings, maximum weighted matroid members, and maximum weighted 3D-matchings. For most of these problems, only randomized mechanisms with very high approximation ratios were known prior to our results.

This is joint work with Georgios Birmpas and Evangelos Markakis

[XaviannNJ]

Παρασκευή, Α36,17:00

Καλησπέρα σε όλους,

Επανερχόμαστε αυτή την Παρασκευή, και θα μας μιλήσει η
μεταδιδακτορική ερευνήτρια Αγγελίνα Βιδάλη για σχεδίαση μηχανισμών σε scheduling problems.

Ως συνηθως στην αίθουσα Α36 στις 17:00.

Ακολουθούν οι πληροφορίες για την ομιλία

Speaker: Angelina Vidali

Title: Mechanism Design for Scheduling with Uncertain Execution Time

Abstract:

Crowdsourcing tasks to agents, in the context of processing big data, creates a lot of uncertainty about the execution times. We study the problem where a task (or multiple unrelated tasks) must be executed, there are multiple machines/agents that can potentially perform the task, and our objective is to minimize the expected sum of the agents' processing times. Each agent does not know exactly how long it will take him to finish the task; he only knows the distribution from which this time is drawn. Agents are selfish and will lie about their distributions if this increases their expected utility. We construct a mechanism that makes it an ex-post equilibrium for the agents to both truthfully report their distributions and exert full effort. We would further like to characterize all possible mechanisms.



Joint work with Vincent Conitzer, (Duke University, USA)

[Georgemanif]

Αυτή την Παρασκευή θα μας δώσει ομιλία ένας επισκέπτης μας από Πολωνία, από το University of Wroclaw.
Η ομιλία αφορά αλγορίθμους για εκλογικούς κανόνες που χρησιμοποιούν approval voting.

Αίθουσα A36, στις 17:00

Speaker: Krzysztof Sornat
Title: Approximation and Parameterized Complexity of Minimax Approval Voting.

Abstract:
We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time O*(2^o(d\log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d^(2d)) algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/eps)^(2d)), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time n^O(log(1/eps)/eps^2) * poly(m), almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].

This is joint work with Marek Cygan, Łukasz Kowalik, Arkadiusz Socała.

[XaviannNJ]

Καλησπέρα σε όλους,

Δεν θα έχουμε άλλο theory tea μες στον Δεκέμβρη,
Όμως, αυτη τη Δευτέρα υπάρχει μια ενδιαφέρουσα ομιλία σε αντίστοιχο σεμινάριο στο ΕΜΠ.

Παραθέτω τις πληροφορίες για την ομιλία παρακάτω.

Τη Δευτέρα 19/12 θα μας μιλήσει ο Βασίλης Γκατζέλης. Η ομιλία θα δοθεί στις 5μμ στην αίθουσα 1.1.31. Λεπτομέρειες ακολουθούν.

Speaker: Vasilis Gkatzelis

Title: Deferred-Acceptance Auctions: Performance and Generalizations

Abstract: Deferred-acceptance auctions are mechanisms whose allocation rule can be implemented using an adaptive reverse greedy algorithm. These auctions were introduced by Milgrom and Segal, who proved that they satisfy remarkable incentive guarantees that previously studied mechanisms do not possess. We first provide an overview of social welfare approximation bounds regarding the performance of deferred-acceptance auctions in the presence of single-minded bidders. Then, we generalize the definition of deferred-acceptance auctions beyond single-minded bidder settings and provide examples of generalized deferred-acceptance auctions.

[Georgemanif]

Καλησπέρα και καλή χρονιά σε όλους!

Αυτη την Παρασκευή δεν έχουμε κανονίσει κάποια ομιλία,
θα μαζευτούμε όμως για να κόψουμε πιτα και να ευχηθούμε καλή χρονιά.

Αν σκέφτεστε να πάρετε τα Ειδικά Θέματα Αλγορίθμων στο εαρινό εξάμηνο, είναι μια καλή ευκαιρία να ρωτήσετε πράγματα π.χ. για την ύλη, όπως επίσης αν σκέφτεστε να δώσετε τα ειδικά θέματα στην έκτακτη εξεταστική μπορείτε να περάσετε για απορίες.

Θα ξεκινήσουμε τη συνηθισμένη ώρα,
17:15 στην αίθουσα Α36.

[Georgemanif]

Επιστρεφει το theory tea αυτή την Παρασκευή. Και θα μας μιλήσει η Αλκμήνη Σγουρίτσα, υποψήφια διδάκτορας στο University of Liverpool.

Προσεξτε ότι η ομιλία θα είναι στις 15:00 και όχι στις 17:00 που το έχουμε συνήθως.

Ακολουθούν οι λεπτομέρειες για την ομιλία


Speaker: Alkmini Sgouritsa, University of Liverpool
Title: Designing networks with good equilibria under uncertainty

Abstract:
We consider the problem of designing network cost-sharing protocols with good equilibria under uncertainty. The underlying game is a multicast game in a rooted undirected graph with nonnegative edge costs. A set of terminal vertices or players need to establish connectivity with the root. The social optimum is the Minimum Steiner Tree. We are interested in situations where the designer has incomplete information about the input. The designer has prior knowledge of the underlying metric, but the requested subset of the players is not known and is activated in an adversarial manner. The goal of the designer is to choose a single, universal cost-sharing protocol that has low Price of Anarchy (PoA) for all possible requested subsets of players. The main question we address is: to what extent can prior knowledge of the underlying metric help in the design? We first demonstrate that there exist classes of graphs where knowledge of the underlying metric can dramatically improve the performance of good network cost-sharing design. Then, we show that there exist graph metrics, for which knowing the underlying metric does not help. We attack this problem by developing new techniques that employ powerful tools from extremal combinatorics, and more specifically Ramsey Theory in high dimensional hypercubes.

Joint work with George Christodoulou

[Georgemanif]

Αυτη την Παρασκευή,
αν και δεν έχουμε theory tea, υπάρχει μια ενδιαφέρουσα ομιλία σε σεμινάριο του τμήματος, η οποία σχετίζεται και με θέματα που έχουμε αναφέρει κατά καιρούς.
Δείτε παρακάτω περισσότερες λεπτομέρειες για την επισκέπτρια και την ομιλία της.
Για όσους δεν μπορέσουν να έρθουν ευχόμαστε καλό Πάσχα και θα επιστρέψουμε, με μερικές ακόμα ομιλίες μες στον Μάιο.
ΕΡΕΥΝΗΤΙΚΟ ΣΕΜΙΝΑΡΙΟ
Παρασκευή 7 Απριλίου, 3μμ
Αίθουσα A41, πτέρυγα Αντωνιάδου
“Cross-layer estimation and control for Cognitive Radio:
Exploiting Sparse Network Dynamics”
Urbashi Mitra,
Ming Hsieh Department of Electrical Engineering,
University of Southern California
Περίληψη: Cognitive radio was introduced in the late 1990s as a concept to improve efficiency of spectrum use. Opportunistic users would sense spectral holes and exploit unused spectrum. The original strategy suggested that spectrum being employed by primary, legacy users should be strictly avoided in order to ensure no interference to the primary users. However, this strict ``white space’’ approach is also inherently spectrally inefficient. In this talk, we review several strategies that limit interference to primary users while significantly improving the throughput of secondary, opportunistic users. The basic idea of the new approach is to exploit the fact that, typically the primary channel is not fully loaded by the primary user service, thus leaving a non-negligible margin to accommodate the cognitive transmission. Furthermore, the exploitation of such a load margin can be optimized in a variety of ways including shaping the spectrum of the secondary user, optimizing retransmission protocols and jointly designing methods by which to do dynamic spectrum sensing and allocation via cross-layer approaches. Sensing and access are jointly controlled to maximize the secondary user throughput. The sparsity of the spectrum dynamics is exploited: leveraging a prior spectrum occupancy estimate, the central controller needs to estimate only a residual uncertainty vector via sparse recovery techniques. Sparse recovery methods tailored to the Markov Decision Process modeling of the system are provided and shown to offer strong performance improvement over prior approaches. Our framework yields sensing-scheduling schemes that are most informative for network control, yielding energy efficient resource utilization. The new methods are summarized and performance gains are highlighted.

[Georgemanif]

Αυτη την Παρασκευή θα μας μιλήσει ο Γιάννης Μωυσόγλου, απόφοιτος απο το ΕΚΠΑ,
για ένα μέρος της διατριβής του,

Παρασκευή 5/5, και ώρα 15:00,
στην αιθουσα Α36

Ακολουθούν οι πληροφορίες για την ομιλία.


Title: Limitations of Linear Programs: Locality and Size

Abstract: Linear Programming (LP) has great modeling power when it comes
to planning, routing and scheduling problems. It is, arguably, the most
widely used tool in the design of approximation algorithms. In recent
years, however, the strength of linear programming as a universal problem
solver has been disputed. Two well-studied measures of complexity of
linear programs are the locality of the constraint and the size. Some
research directions that have received great attention from the
optimization community are concerned with the power of linear programming
based algorithms with respect to the aforementioned parameters. In this
talk we focus on LPs for the capacitated facility location problem (CFL),
a problem that has proven to be notorious for linear programming, under
the lens of locality and size. In particular, by building on the idea of
fooling local constraints, we show that the so-called submodular
inequalities for CFL fail to reduce the integrality gap to constant,
giving a negative answer to a long-standing conjecture of Levi, Shmoys and
Swamy. Moreover, we develop a method for deriving lower bounds to the size
of linear programs that achieve a certain quality of solution and present
an application of the method to CFL.