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

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

Hi,

We'll have an LFCS seminar next week:

  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.