Events and news relevant to the Laboratory for Foundations of Computer Science

[Ohad Kammar <ohad.kammar@ed.ac.uk>]

Hi,

This week's LFCS seminar will start shortly:

  Tuesday, 23 Sep, 4.10pm

  Paul Goldberg, University of Oxford

  The seminar will take place in-person only.

We're synchronising the seminar time with the teaching timetable, and

plan to start the talk at the advertised time, so please arrive a minute or two

earlier.

In detail:

----------------------------------------------------------------------

Paul Goldberg, University of Oxford

https://www.cs.ox.ac.uk/people/paul.goldberg/index1.html

  Tue, 23 Sep, 4.10pm

  Venue: IF G.03

Title: Complexity of Unambiguous Problems in Σ^P_2

Abstract

An unambiguous problem is a computational search problem for which any

instance has at most one solution. We are interested in particular in

problems where this uniqueness of solutions is due to the structure of

the problem itself, as opposed to being due to a (hard to verify) promise

that any solution is unique. There are not many such problems in the

class NP (amongst problems that are not known to be polynomial-time

solvable), but there are various interesting ones in the class Σ^P_2.

For example, some are based on the idea that we can design competitions

for which there is at most one winner. With exponentially-many

competitors, we seek a competitor that beats all his opponents: if

"beats" is checkable in polynomial time, we have a Σ^P_2 problem having

at most one solution. Towards classifying the complexity of these

problems, we introduce complexity classes "Polynomial Tournament

Winner" and "Polynomial Condorcet Winner". This is joint work in

progress with Matan Gilboa, Elias Koutsoupias, and Noam Nisan. I will

try to include reminders of definitions of any complexity classes I

refer to, apart from P and NP.

----------------------------------------------------------------------

Upcoming seminars:

------------------

29 Sep **Monday**, special AIAI & LFCS seminar, Andrew Gordon, Cogna and 

        University of Edinburgh: Vibe Checking: From Prompt to Protection

30 Sep: Leslie Ann Goldberg, University of Oxford: Instability of Contention Resolution

        Protocols

07 Oct: Zongchen Chen, Georgia Institute of Technology (Georgia Tech)

14 Oct: Bruno Cavalar, University of Oxford

21 Oct: Xinyuan Zhang, Nanjing University

28 Oct: Patrick Totzke, University of Liverpool: Optimally Controlling a Random

        Population

If you would like to propose a speaker, or speak yourself, please contact me.

The seminar webpages:

http://web.inf.ed.ac.uk/lfcs/events/lfcs-seminars

Yours,

Ohad.

The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.