On protocols for monotone feasible interpolation

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F23%3A00574198" target="_blank" >RIV/67985840:_____/23:00574198 - isvavai.cz</a>

Alternative codes found

RIV/00216208:11320/23:10467112

Result on the web

<a href="https://doi.org/10.1145/3583754" target="_blank" >https://doi.org/10.1145/3583754</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3583754" target="_blank" >10.1145/3583754</a>

Result language

angličtina

Original language name

On protocols for monotone feasible interpolation

Original language description

Dag-like communication protocols, a generalization of the classical tree-like communication protocols, are useful objects in the realm of proof complexity (most importantly for monotone feasible interpolation) and circuit complexity. We consider three kinds of protocols in this article (d is the degree of a protocol): - IEQ-d-dags: feasible sets of these protocols are described by inequality which means that the feasible sets are combinatorial triangles, these protocols are also called triangle-dags in the literature, - EQ-d-dags: feasible sets are described by equality, and - c-IEQ-d-dags: feasible sets are described by a conjunction of c inequalities.Garg, Göös, Kamath, and Sokolov (Theory of Computing, 2020) mentioned all these protocols, and they noted that EQ-d-dags are a special case of c-IEQ-d-dags. The exact relationship between these types of protocols is unclear. As our main contribution, we prove the following statement: EQ-2-dags can efficiently simulate c-IEQ-d-dags when c and d are constants. This implies that EQ-2-dags are at least as strong as IEQ-d-dags and that EQ-2-dags have the same strength as c-IEQ-d-dags for c ≥ 2 (because 2-IEQ-2-dags can trivially simulate EQ-2-dags).Hrubeš and Pudlák (Information Processing Letters, 2018) proved that IEQ-d-dags over the monotone Karchmer-Wigderson relation are equivalent to monotone real circuits which implies that we have exponential lower bounds for these protocols. Lower bounds for EQ-2-dags would directly imply lower bounds for the proof system R(LIN).

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

ACM Transactions on Computation Theory

ISSN

1942-3454

e-ISSN

—

Volume of the periodical

15

Issue of the periodical within the volume

1-2

Country of publishing house

US - UNITED STATES

Number of pages

17

Pages from-to

2

UT code for WoS article

001020428600002

EID of the result in the Scopus database

2-s2.0-85164243386