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 today:

  Tuesday, 14 Oct, 4.10pm

  Bruno Cavalar, 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:

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

Bruno Cavalar, University of Oxford

https://brunopc.github.io/

  Tue, 14 Oct, 4.10pm

  Venue: IF G.03

Title: Monotone circuit complexity of matching

Abstract

We show that the perfect matching function on $n$-vertex graphs

requires monotone circuits of size $2^{n^{\Omega(1)}}$. This

improves on the $n^{\Omega(\log n)}$ lower bound of Razborov (1985).

Our proof uses the standard approximation method together with a new

sunflower lemma for matchings.

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

Upcoming seminars:

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

21 Oct: Xinyuan Zhang, Nanjing University: Sampling and Counting via Coupling

        Independence

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.