Σεμινάριο Αλγορίθμων

Algorithms Seminar

Τμήμα Πληροφορικής και Τηλεπικοινωνιών

Πανεπιστήμιο Αθηνών

Department of Informatics and Telecommunications

University of Athens

Υπεύθυνος : Άγγελος Κιαγιάς

Αίθουσα Τηλεσυσκέψεων,

2ος Οροφος Κέντρο Δικτύων

2nd Floor, NOC Building

Επόμενη Ομιλία(ες)

Next Talk(s)

Προηγούμενες Ομιλίες

Previous Talks:

Δευτέρα 16.12.2013, 18:00

Monday 16.12.2013, 18:00

Practical Dynamic Proofs of Retrievability

Charalampos Papamanthou

(University of Maryland, College Park)

[The talk will take place at Room A56 (1st floor above Unix lab) ]

AbstractProofs of Retrievability (PoR) enable a client to store a number of file blocks with a cloud server so that later the server can prove possession of all the data in a very efficient manner (i.e., with constant computation and bandwidth). Although many efficient PoR schemes for static data have been constructed, only two dynamic PoR schemes exist, which have various disadvantages such as large client storage or practical inefficiency.

We propose the first dynamic PoR scheme that is both theoretically and practically efficient. Specifically (i) all complexity measures involved are at most logarithmic in the number of the outsourced blocks; (ii) our system implementation is very practical.

Joint work with Elaine Shi and Emil Stefanov (CCS 2013)

Παρασκευή 21.06.2013, 15:00

Friday 21.06.2013, 15:00

Cryptography in a big data world: the case of streaming

Periklis Papakonstantinou

(Tsinghua University, China)

[The talk will take place at Room A56 (1st floor above Unix lab) ]

AbstractWe consider the computation of cryptographic primitives using streaming devices (not to be confused with stream ciphers). In this setting everything: keys, messages, ciphertexts, seeds, etc, are huge compared to the internal memory of the streaming device which computes over Big Data. These data  are thought to be stored in hard disks, or disk arrays or other sequentially  accessed devices. In particular, our streaming algorithms operate using:

i. a small, typically of O(logn) size, local memory and

ii. a constant number of external tapes (aka streams) on which they are making

a constant number of passes; initially, one (or more) of these streams contain

the input

Using such a streaming algorithm is it possible to compute a cryptographic  primitive, where at the end of the computation the results will appear in one of the  external streams?

One can show that in such a setting it is (unconditionally) impossible to multiply  two large integers, it is impossible to multiply a matrix by a vector, and other  elementary operations. Assuming e.g. that FACTORING is hard, although a  streaming algorithm cannot multiply integers, is it possible to do cryptography  (e.g. compute a one-way function) based on the hardness of FACTORING?

The possibility of such a construction sounds highly unlikely  (how to do crypto based on the hardness of factoring in a world where multiplication is impossible?), but using non-black-box techniques we can show that indeed this is possible.

In this talk I'll outline such non-black-box constructions, explain why and how these  circumvent previous black-box separation results, then I'll show how to construct  pseudorandom generators in a streaming setting starting from the assumption that  one-way functions exist in some standard complexity class (which includes the vast  majority of cryptographic assumptions). If time permits I'll show how one can obtain streaming Public-Key Encryption systems based on standard lattice assumptions.

This is joint work with Guang Yang.

Παρασκευή 24.5.2013, 14:00

Friday 24.5.2013, 14:00

Approximate Strategyproof Mechanisms for Facility Location Games

Dimitris Fotakis

(NTUA, Greece)

[Η ομιλία θα γίνει στην Αίθουσα Δ’]

AbstractWe consider k-Facility Location games, where n strategic agents report their locations in a metric space, and a mechanism maps them to k facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may misreport their location. We are interested in (deterministic or randomized) mechanisms that are strategyproof, i.e., ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and achieve a good approximation ratio to either the total connection cost or their maximum connection cost of the agents.

We present an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with n \geq 5 agents, any such mechanism either admits a unique dictator, or places the facilities at the leftmost and the rightmost location of the instance. As a corollary, we obtain that the best  approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating 2 facilities on the line to minimize the total connection cost is precisely n-2.

Building on the techniques used for the characterization, we also show that:

-- For every k \geq 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for k-Facility Location on the line, even for simple instances with k+1 agents.

-- There do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on general metric spaces, which is true even for simple instances with 3 agents located in a star.

On the positive side, we present a randomized mechanism for locating k facilities on the line that achieves an approximation ratio of 2 for the objective of maximum cost and an approximation ratio of n for the objective of total cost.

Τhis is joint work with Christos Tzamos (CSAIL, MIT).

Πεμπτη 11.4.2013, 11:00

Friday 11.4.2013, 11:00

Lexicographic Orderings

Zoltan Esik

(University of Szeged, Hungary)

[Η ομιλία θα γίνει στην Αίθουσα Z’]

AbstractEach countable linear ordering may be represented as the lexicographic ordering of a language over some finite alphabet. But which linear orderings can be represented as lexicographic orderings of regular, context-free, or deterministic context-free languages? Can we decide whether the lexicographic ordering of a regular or (deterministic) context-free language is a well-ordering, or a scattered linear ordering, or a dense ordering? Do lexicographic orderings of these languages have decidable first-order or monadic second-order theories? Is it decidable whether the lexicographic orderings of two given regular or context-free languages are isomorphic?

In the talk I will present answers to the above questions.

Παρασκευή 23.3.2012, 12:00

Friday 23.3.2012, 12:00

Computational Modelling of Self-Control Behaviour with Neural Networks Playing Games

Chris Christodoulou

(University of Cyprus)

[Η ομιλία θα γίνει στην Αίθουσα Ε’]

Abstract.  Self-control can be defined as choosing a large delayed reward, while precommitment is the making of a choice with the specific aim of denying oneself future choices. Problems in exercising self control, suggest a conflict between cognition and motivation, which has been linked to competition between higher and lower brain functions or different value systems in the brain; in particular, parts of the limbic system are preferentially activated by decisions involving instant rewards, whereas regions of the prefrontal cortex are engaged uniformly by intertemporal choices irrespective of delay. This premise of an internal process model lead to a behaviour model being proposed, based on which we designed and implemented a computational model of self-control with two spiking or non-spiking neural networks with reinforcement learning representing the higher and lower brain systems viewed as cooperating for the benefit of the organism. As the structure of the self-control problem can be likened to the Iterated Prisoner’s Dilemma (IPD) game in that cooperation is to defection what self-control is to impulsiveness or what compromising is to insisting, we implemented the neural networks as two players, learning simultaneously but independently, competing in the IPD game. With a technique resembling the precommitment effect, whereby the payoffs for the dilemma cases in the IPD payoff matrix are differentially biased (increased or decreased), we showed that increasing the precommitment effect (through increasing the differential bias) increases the probability of cooperating with oneself in the future, irrespective of whether the implementation is with spiking or non-spiking neural networks. The contribution of this work to multiagent reinforcement learning will also be highlighted. The talk will finish with an attempt to interpret our results on self-control through recent findings reported in the literature supporting that conflicts involving the delay of gratification, such as self-control problems lead to systematic changes in 'subjective experience' or consciousness. Can perturbations in consciousness, be related to the process of learning self-control behaviour by the brain in order to resolve the conscious conflict?

Παρασκευή 13.1.2012, 13:00

Friday 13.1.2012, 13:00

Μεταπτυχιακές Σπουδές σε ΗΠΑ και Καναδά

Dimitris Paparas

(Columbia University)

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

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

Τετάρτη 11.1.2012, 14:00

Wednesday 11.1.2012, 14:00

Solving the At-Most-Once Problem with Nearly Optimal Effectiveness

Sotiris Kentros

(University of Connecticut)

Abstract.  We present and analyze a wait-free deterministic algorithm for solving the at-most-once problem: how m shared-memory fail-prone processes perform asynchronously n tasks at most once. Our algorithmic strategy provides for the first time nearly optimal effectiveness, which is a measure that expresses the total number of tasks completed in the worst case. The effectiveness of our algorithm equals n-2m+2. This is up to an additive factor of m close to the known effectiveness upper bound n-m+1 over all possible algorithms and improves on the previously best known deterministic solutions that have effectiveness only n - log m o(n). We also present an iterated version of our algorithm that for any m = O((n/log n)^(1/(3+\epsilon))) is both effectiveness-optimal and work-optimal, for any constant \epsilon > 0. We then employ this algorithm to provide a new explicit algorithmic solution for the Write-All problem which is work optimal for any m=O((n/log n)^(1/(3+\epsilon))) improving the previously best known result of m = O((n/log n)^(1/4)).

X-THEORY DAY!

December 19th 2011

Program

Foteini Baldimtsi (Brown University) 1:15pm-2

George Christodoulou (University of Liverpool) 2:00pm-3

Break

Dimitris Diochnos (U. of Illinois Chicago) 3:30pm-4:15.

Neal Immerman (University of Massachusetts) 4:15pm-5:15

link will become current shortly before talks

On The Security of Unique-Witness Blind Signature Schemes

Foteini Baldimtsi

(Brown University)

Abstract.  A blind signature scheme is an interactive protocol between a user and a signer which allows the user to get a message signed by the signer without revealing this message (blindness)

while the user cannot compute any additional signature without the help of the signer

(unforgeability). Any third party should be able to verify the validity of the signature. Blind

signatures constitute the main building block for emerging applications like electronic-cash

and electronic-voting. Although the first blind signature scheme was proposed by Chaum back in '83, the first formal  definitions appeared in '00 by Pointcheval and Stern. The most challenging part when proving  security of a blind signature is how to show the unforgeability of the scheme. Pointcheval and  Stern proposed a generic reduction technique called "oracle replay attack" to prove

unforgeability in the Random Oracle model. In this talk we will show that all the unique-witness blind signature schemes that were  constructed using the Fiat-Shamir heuristic cannot be proven unforgeable (and thus secure)  in the RO model  under any security assumption using the currently known techniques.  Finally, we provide an instantiation of our general result on the blind signature proposed  by Brands which gives rise to his famous e-cash scheme.

Coordination Mechanisms for Selfish Routing Games

George Christodoulou

(University of Liverpool)

Abstract.  We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already  for a simple network of two parallel links, known as Pigou's network. We improve upon the value 4/3 by means of Coordination Mechanisms. We first exhibit a simple coordination mechanism that achieves for any network of parallel links a Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4 = 1.25. Then, for the case of two parallel links, we describe an {\em optimal} mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.

On Multiple-Instance Learning of Halfspaces

Dimitris Diochnos

(University of Illinois, Chicago)

Abstract.  In multiple-instance learning the learner receives bags, i.e., sets of instances. A bag is labelled positive if it contains a positive example of the target. An $\Omega(d \log r)$ lower bound is given for the VC-dimension of bags of size $r$ for $d$-dimensional halfspaces and it is shown that the same lower bound holds for halfspaces over any large point set in general position. This lower bound improves an $\Omega(\log r)$ lower bound of Sabato and Tishby, and it is sharp in order of magnitude. We also show that the hypothesis finding problem is NP-complete. Closing we will discuss some open problems. Joint work with R. Sloan and Gy Turan.

P versus NP: Approaches, Rebuttals, and Does It Matter?

Neal Immerman

(University of Massachusetts)

Abstract.  NP contains all those problems that we could efficiently solve if "guessing were free", i.e., all those problems whose solutions we could recognize as correct if they were given to us in an appropriate format and context.  We've known since 1971 that a large class of important combinatorial problems including boolean satisfiability (SAT) are NP complete, i.e, hardest problems in NP.  If any of these had a solution in P, then so would all other problems in NP. How hard is SAT, or any other NP-complete problem?  It is well believed that P is not equal to NP and that SAT requires exponential time on some hard instances.  However, SAT solvers are now in practical use as general problem solvers, currently working even on instances with a million variables. I will explain some of these issues, laying out what we do know, what we do not know, and what we hope to understand once the P versus NP question, together       with many similar but less famous open questions, are finally resolved.  At the same time, this talk will present a survey of descriptive complexity -- the logical approach to complexity that I have been pursuing for years