Algebraic Approach to Approximation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10489333" target="_blank" >RIV/00216208:11320/24:10489333 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Algebraic Approach to Approximation

Popis výsledku v původním jazyce

Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently promise CSPs, we propose an algebraic framework for valued promise CSPs. To every valued promise CSP we associate an algebraic object, its so-called valued minion. Our main result shows that the existence of a homomorphism between the associated valued minions implies a polynomial-time reduction between the original CSPs. We also show that this general reduction theorem includes important inapproximability results, for instance, the inapproximability of almost solvable systems of linear equations beyond the random assignment threshold.

Název v anglickém jazyce

Algebraic Approach to Approximation

Popis výsledku anglicky

Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently promise CSPs, we propose an algebraic framework for valued promise CSPs. To every valued promise CSP we associate an algebraic object, its so-called valued minion. Our main result shows that the existence of a homomorphism between the associated valued minions implies a polynomial-time reduction between the original CSPs. We also show that this general reduction theorem includes important inapproximability results, for instance, the inapproximability of almost solvable systems of linear equations beyond the random assignment threshold.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings - Symposium on Logic in Computer Science

ISBN

—

ISSN

1043-6871

e-ISSN

2575-5528

Počet stran výsledku

14

Strana od-do

—

Název nakladatele

IEEE Computer Society Press

Místo vydání

Washington, D.C.

Místo konání akce

Tallinn

Datum konání akce

8. 7. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001275042100010