BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Antonina Kolokolova (Memorial University of Newfoundland) DTSTART:20220210T190000Z DTEND:20220210T200000Z DTSTAMP:20260423T021152Z UID:OLS/86 DESCRIPTION:Title: Lea rning from bounded arithmetic\nby Antonina Kolokolova (Memorial Univer sity of Newfoundland) as part of Online logic seminar\n\n\nAbstract\nThe c entral question of complexity theory -- what can (and cannot) be feasibly computed -- has a corresponding logical meta-question: what can (and cann ot) be feasibly proven. While complexity theory studies the former\, boun ded arithmetic is one of the main approaches to the meta-question. There i s a tight relation between theories of bounded arithmetic and correspondin g complexity classes\, allowing one to study what can be proven in\, for e xample\, "polynomial-time reasoning" and what power is needed to resolve c omplexity questions\, with a number of both positive and negative provabil ity results.\n\nHere\, we focus on the complexity of another meta-problem: learning to solve problems such as Boolean satisfiability. There is a ran ge of ways to define "solving problems"\, with one extreme\, the uniform s etting\, being an existence of a fast algorithm (potentially randomized)\ , and another of a potentially non-computable family of small Boolean circ uits\, one for each problem size. The complexity of learning can be recas t as the complexity of finding a procedure to generate Boolean circuits so lving the problem of a given size\, if it (and such a family of circuits) exists.\n\nFirst\, inspired by the KPT witnessing theorem\, a special cas e of Herbrand's theorem in bounded arithmetic\, we develop an intermediate notion of uniformity that we call LEARN-uniformity. While non-uniform lo wer bounds are notoriously difficult\, we can prove several unconditional lower bounds for this weaker notion of uniformity. Then\, returning to th e world of bounded arithmetic and using that notion of uniformity as a too l\, we show unprovability of several complexity upper bounds for both dete rministic and randomized complexity classes\, in particular giving simpler proofs that the theory of polynomial-time reasoning PV does not prove tha t all of P is computable by circuits of a specific polynomial size\, and t he theory $V^1$\, a second-order counterpart to the classic Buss' theory $ S^1_2$\, does not prove the same statement with NP instead of P. \n\nFina lly\, we leverage these ideas to show that bounded arithmetic "has trouble differentiating" between uniform and non-uniform frameworks: more specif ically\, we show that theories for polynomial-time and randomized polynom ial-time reasoning cannot prove both a uniform lower bound and a non-unif orm upper bound for NP. In particular\, while it is possible that NP != P yet all of NP is computable by families of polynomial-size circuits\, th is cannot be proven feasibly.\n LOCATION:https://researchseminars.org/talk/OLS/86/ END:VEVENT END:VCALENDAR