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

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

Hi,

Reminding that this week's LFCS seminar will hopefully start shortly:

  Thur, 02 Apr, 2.10pm (note unusual time and date)

  Xi Chen, Columbia University

  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:

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

Xi Chen, Columbia University

https://www.engineering.columbia.edu/faculty-staff/directory/xi-chen

  Thur, 02 Apr, 2.10pm

  (Note unusual time and day.)

  Venue: IF G.03

Title: Adaptivity Does Not Help: Nearly Tight Lower Bounds for Boolean Monotonicity Testing

Abstract

Monotonicity testing asks: given a Boolean function f: {0,1}^n -> {0,1},

how many queries are needed to distinguish whether f is monotone

or far from monotone? For nonadaptive algorithms, the query

complexity was pinned down at \sqrt{n}. Along the way, a series of

directed isoperimetric inequalities were established to analyze

testers such as the edge tester and the path tester.

But can adaptivity help beat the \sqrt{n} bound? In this talk we answer

in the negative, by proving an almost tight n^{0.5-c} lower bound for

adaptive monotonicity testing, for any constant c > 0. Our proof is

based on a multilevel extension of Talagrand's function.

Joint work with Mark Chen, Hao Cui, William Pires and Jonah Stockwell

(Columbia).

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

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.