BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Susanna F. de Rezende (Mathematical Institute of the Czech Academy
  of Sciences)
DTSTART:20201007T170000Z
DTEND:20201007T180000Z
DTSTAMP:20260423T021010Z
UID:TCSPlus/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/12/"
 >Lifting with Simple Gadgets and Applications to Circuit and Proof Complex
 ity</a>\nby Susanna F. de Rezende (Mathematical Institute of the Czech Aca
 demy of Sciences) as part of TCS+\n\n\nAbstract\nLifting theorems in compl
 exity theory are a method of transferring lower bounds in a weak computati
 onal model into lower bounds for a more powerful computational model\, via
  function composition. There has been an explosion of lifting theorems in 
 the last ten years\, essentially reducing communication lower bounds to qu
 ery complexity lower bounds. These theorems only hold for composition with
  very specific "gadgets" such as indexing and inner product.\n \nIn this t
 alk\, we will present a generalization of the theorem lifting Nullstellens
 atz degree to monotone span program size by Pitassi and Robere (2018) so t
 hat it works for any gadget with high enough rank\, in particular\, for us
 eful gadgets such as equality and greater-than. We will then explain how t
 o apply our generalized theorem to solve three open problems:\n\n- We pres
 ent the first result that demonstrates a separation in proof power for cut
 ting planes with unbounded versus polynomially bounded coefficients. Speci
 fically\, we exhibit CNF formulas that can be refuted in quadratic length 
 and constant line space in cutting planes with unbounded coefficients\, bu
 t for which there are no refutations in subexponential length and subpolyn
 omial line space if coefficients are restricted to be of polynomial magnit
 ude.\n\n- We give the strongest separation to-date between monotone Boolea
 n formulas and monotone Boolean circuits. Namely\, we show that the classi
 cal GEN problem\, which has polynomial-size monotone Boolean circuits\, re
 quires monotone Boolean formulas of size $2^{\\Omega(n / \\text{polylog}(n
 ))}$.\n\n- We give the first explicit separation between monotone Boolean 
 formulas and monotone real formulas. Namely\, we give an explicit family o
 f functions that can be computed with monotone real formulas of nearly lin
 ear size but require monotone Boolean formulas of exponential size. Previo
 usly only a non-explicit separation was known.\n\nThis talk is based on jo
 int work with Or Meir\, Jakob Nordström\, Toniann Pitassi\, Robert Robere
 \, and Marc Vinyals.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/12/
END:VEVENT
END:VCALENDAR