#### Inscriere cercetatori

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: http://premii.ad-astra.ro/. Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la cristian.presura@gmail.com

#### Geometric Properties of Satisfying Assignments of random \$epsilon\$-1-in-k SAT

Autori: Gabriel Istrate

Editorial: International Journal of Computer Mathematics, 86(12), p.2029-2039, 2009.

Rezumat:

We study the geometric structure of the set of solutions of random \$epsilon\$-1-in-k SAT problem. For \$l geq 1\$, two satisfying assignments \$A\$ and \$B\$ are \$l\$-connected if there exists a sequence of satisfying assignments connecting them by changing at most \$l\$ bits at a time.

We first identify a subregion of the satisfiable phase where the set of solutions provably forms one cluster. Next we provide a range of parameters \$(c,epsilon)\$ such that w.h.p. two assignments of a random \$epsilon\$-1-in-\$k\$ SAT instance with \$n\$ variables and \$cn\$ clauses are \$O(log n)\$-connected, conditional on being satisfying assignments. Also, for random instances of 1-in-\$k\$ SAT in the satisfiable phase we show that there exists \$nu_{k}in (0,frac{1}{k-2}]\$ such that w.h.p. no two satisfying assignments at distance at least \$nu_{k}cdot n\$ form a „hole”. We believe that this is true for all \$nu_{k}>0\$, and in fact solutions of a random 1-in-\$k\$ SAT instance in the satisfiable phase form one cluster.

http://xxx.lanl.gov/abs/0811.3116

Cuvinte cheie: \$epsilon\$-1-in-k SAT, overlaps, random graphs, phase transition.