[Proof Complexity] Prague seminar on Monday - Marco Carmosino

[thapen]

Marco Carmosino will give a proof complexity talk in our online logic 
seminar on Monday 14th June, at 15:45 Prague time - see the announcement 
below. This will be the last talk for the semester.

To join use the link
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)

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

  Speaker: Marco Carmosino, Boston University
  Title: LEARN-Uniform Circuit Lower Bounds and Provability in Bounded 
Arithmetic

  Abstract

  We investigate randomized LEARN-uniformity, which captures the power of 
randomness and equivalence queries (EQ) in the construction of Boolean 
circuits for an explicit problem. This is an intermediate notion between 
P-uniformity and non-uniformity motivated by connections to learning, 
complexity, and logic. Building on a number of techniques, we establish 
the first unconditional lower bounds against LEARN-uniform circuits. For 
example:

  For each k >= 1, there is a language L in NP such that circuits for L 
of size O(n^k) cannot be learned in deterministic polynomial time with 
access to n^o(1) EQs.

  We employ such results to investigate the (un)provability of 
non-uniform circuit upper bounds (e.g., Is NP contained in SIZE[n^3]?) 
in theories of bounded arithmetic. Some questions of this form have been 
addressed in recent papers of Krajicek-Oliveira (2017), Muller-Bydzovsky 
(2020), and Bydzovsky-Krajicek-Oliveira (2020) via a mixture of 
techniques from proof theory, complexity theory, and model theory. In 
contrast, by extracting computational information from proofs via a 
direct translation to LEARN-uniformity, we establish robust 
unprovability theorems that unify, simplify, and extend nearly all 
previous results. In addition, our lower bounds against randomized 
LEARN-uniformity yield unprovability results for theories augmented with 
the dual weak pigeonhole principle, such as APC^1 (Jerabek, 2007), which 
is known to formalize a large fragment of modern complexity theory.

  Finally, we make precise potential limitations of theories of bounded 
arithmetic such as PV (Cook, 1975) and Jerabek's theory APC^1, by 
showing unconditionally that these theories cannot prove statements like 
"NP is not contained in BPP, and NP is contained in ioP/poly", i.e., 
that NP is uniformly "hard" but non-uniformly "easy" on infinitely many 
input lengths. In other words, if we live in such a complexity world, 
then this cannot be established feasibly.


  For more information see the seminar web page at
  https://calendar.math.cas.cz/logic-seminar-actual .

_______________________________________________
Logic-seminar mailing list
Logic-seminar at math.cas.cz
https://list.math.cas.cz/listinfo/logic-seminar