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

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

Hi,

This seminar will start shortly:

1) Tuesday, 27 May, 2.10pm (note unusual time)

   Swagato Sanyal, University of Sheffield

   The seminar will take place in-person only.

   Venue: IF MF2

   If you want to meet with the speaker, contact Heng Guo <hguo@inf.ed.ac.uk> .

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:

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

Swagato Sanyal, University of Sheffield

https://www.sheffield.ac.uk/cs/people/academic/swagato-sanyal

  Tue, 27 May, 2.10pm

  Venue: IF MF-2

  Note unusual time and room.

Title: On the composition question for randomized query complexity.

Abstract

A query algorithm (also known as a decision tree) that computes a

Boolean function f on n variables, queries various bits of an input to f,

possibly in an adaptive fashion and using randomness. It eventually

produces a bit as an output, which is supposed to equal the value of f on

that input with high probability. The complexity measure of such an

algorithm is the number of queries that it makes in the worst case. This

talk considers the query complexity of a class of Boolean function

called 'composed functions'. Composition of two Boolean functions f

and g is, informally speaking, the Boolean function (say h) obtained by

successive applications of g and f. The composition question,

instantiated for query complexity, asks whether there exists a query

algorithm that computes h that is significantly more efficient than

what the definition of h suggests: first compute g and then compute f.

The question has been the centre of a lot of research, and stands open to

this day. In this work we present some results in relation to this

question.

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

Upcoming seminars:

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

05 Jun (Thur): Rasmus Møgelberg, IT University of Copenhagen

17 Jun (11.10am, TBC): Andreas Abel, Gothenburg University / Chalmers

05 Aug: Michael Sperber, Active Group GmbH

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.