Levent Tunçel

Yu Hin Au, Levent Tunçel

We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász--Schrijver SDP operator $\text{LS}_+$ applied to the fractional stable set polytope. In particular, we show that for every positive integer $\ell$, the smallest possible graph with $\text{LS}_+$-rank $\ell$ contains $3\ell$ vertices. This result is sharp and settles a conjecture posed by Lipták and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer $\ell$ there exists a vertex-transitive graph on at most $4\ell+12$ vertices with $\text{LS}_+$-rank at least $\ell$.

Yu Hin Au, Levent Tunçel

We study the lift-and-project relaxations of the stable set polytope of graphs generated by $\text{LS}_+$, the SDP lift-and-project operator devised by Lovász and Schrijver. Our focus is on $\ell$-minimal graphs: graphs on $3\ell$ vertices with $\text{LS}_+$-rank $\ell$, i.e., the smallest graphs realizing rank $\ell$. This manuscript makes two complementary contributions. First, we introduce $\text{LS}_+$ certificate packages, a modular framework for certifying membership in $\text{LS}_+$-relaxations using only integer arithmetic and simple, concise calculations, thereby making numerical lower-bound proofs more transparent, reliable, and easier to verify. Second, we apply this framework to a computational search for extremal graphs. We prove that there are at least 49 non-isomorphic 3-minimal graphs and at least 4,107 non-isomorphic 4-minimal graphs, improving the previously known counts of 14 and 588, respectively. Beyond the increase in counts, the new examples sharpen the emerging structural picture: stretched cliques remain central but are not exhaustive, clique number is informative but not decisive, and some extremal graphs exhibit previously unseen graph minor and edge density behaviour. We also determine the smallest vertex-transitive graphs of $\text{LS}_+$-rank $\ell$ for every $\ell \leq 4$.

Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato et al.

We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then simultaneously certify the approximate optimality of a cut and a fractional cut cover. We present several implementations which reliably achieve the celebrated Goemans and Williamson approximation ratio of $α_{\mathrm{GW}} \approx 0.878$ for both optimization problems simultaneously, after $\lceil 128 \ln m \rceil$ samples, a number significantly smaller than the best theoretical bounds. This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after $\lceil 128 \ln m \rceil$ samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run.

Ashwin Nayak, Jamie Sikora, Levent Tunçel

We focus on a family of quantum coin-flipping protocols based on bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. We then use these simplifications to construct their point games as developed by Kitaev. We also study the classical version of these protocols and use linear optimization to formulate optimal cheating strategies. We then construct the point games for the classical protocols as well using the analysis for the quantum case. We discuss the philosophical connections between the classical and quantum protocols and their point games as viewed from optimization theory. In particular, we observe an analogy between a spectrum of physical theories (from classical to quantum) and a spectrum of convex optimization problems (from linear programming to semidefinite programming, through second-order cone programming). In this analogy, classical systems correspond to linear programming problems and the level of quantum features in the system is correlated to the level of sophistication of the semidefinite programming models on the optimization side. Concerning security analysis, we use the classical point games to prove that every classical protocol of this type allows exactly one of the parties to entirely determine the coin-flip. Using the relationships between the quantum and classical protocols, we show that only "classical" protocols can saturate Kitaev's lower bound for strong coin-flipping. Moreover, if the product of Alice and Bob's optimal cheating probabilities is 1/2, then one party can cheat with probability 1. This rules out quantum protocols of this type from attaining the optimal level of security.

Ashwin Nayak, Jamie Sikora, Levent Tunçel

Coin-flipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coin-flip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coin-flips with near optimal bias. The probability of any outcome in these protocols is provably at most $1/\sqrt{2} + δ$ for any given $δ> 0$. However, no explicit description of these protocols is known, and the number of rounds in the protocols tends to infinity as $δ$ goes to 0. In fact, the smallest bias achieved by known explicit protocols is $1/4$ (Ambainis, 2001). We take a computational optimization approach, based mostly on convex optimization, to the search for simple and explicit quantum strong coin-flipping protocols. We present a search algorithm to identify protocols with low bias within a natural class, protocols based on bit-commitment (Nayak and Shor, 2003) restricting to commitment states used by Mochon (2005). An analysis of the resulting protocols via semidefinite programs (SDPs) unveils a simple structure. For example, we show that the SDPs reduce to second-order cone programs. We devise novel cheating strategies in the protocol by restricting the semidefinite programs and use the strategies to prune the search. The techniques we develop enable a computational search for protocols given by a mesh over the parameter space. The protocols have up to six rounds of communication, with messages of varying dimension and include the best known explicit protocol (with bias 1/4). We conduct two kinds of search: one for protocols with bias below 0.2499, and one for protocols in the neighbourhood of protocols with bias 1/4. Neither of these searches yields better bias. Based on the mathematical ideas behind the search algorithm, we prove a lower bound on the bias of a class of four-round protocols.