University of Birmingham > Talks@bham > Lab Lunch > Learning algorithms versus automatability of Frege systems

## Learning algorithms versus automatability of Frege systemsAdd to your list(s) Download to your calendar using vCal - Ján Pich
- Thursday 19 May 2022, 14:00-15:00
- LG23, SoCS and Zoom (see abstract for link).
If you have a question about this talk, please contact Anupam Das. We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system P, we prove that the following statements are equivalent, 1. Provable learning: P proves efficiently that p-size circuits are learnable by subexponential-size circuits over the uniform distribution with membership queries. 2. Provable automatability: P proves efficiently that P is automatable by non-uniform circuits on propositional formulas expressing p-size circuit lower bounds. Here, P is sufficiently strong and well-behaved if I.-III. holds: I. P p-simulates Jerabek’s system WF (which strengthens the Extended Frege system EF by a surjective weak pigeonhole principle); II. P satisfies some basic properties of standard proof systems which p-simulate WF; III . P proves efficiently for some Boolean function h that h is hard on average for circuits of subexponential size. For example, if III . holds for P = WF, then Items 1 and 2 are equivalent for P = WF. If there is a function h ∈ NE ∩ coNE which is hard on average for circuits of size 2^{n/4}, for each sufficiently big n, then there is an explicit propositional proof system P satisfying properties I.-III., i.e. the equivalence of Items 1 and 2 holds for P. This is joint work with Rahul Santhanam. === Zoom details === https://bham-ac-uk.zoom.us/j/81873335084?pwd=T1NaUFg2U1l6d0RLL2RlTzFBam1IUT09 Meeting ID: 818 7333 5084 Passcode: 217 This talk is part of the Lab Lunch series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsCond. Mat. seminar School of Metallurgy and Materials Colloquia Condensed Matter Physics Seminars## Other talksModelling uncertainty in image analysis. Quantum simulations using ultra cold ytterbium Perfect matchings in random sparsifications of Dirac hypergraphs Hodge Theory: Connecting Algebra and Analysis When less is more - reduced physics simulations of the solar wind Geometry of alternating projections in metric spaces with bounded curvature |