More Like this

1. On rich $$2$$-to-$$1$$ games

   Braverman, M; Khot, S; Minzer, D. (October 2019, Electronic colloquium on computational complexity)

   We propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture, we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture. 

   more » « less
2. Blaschke Products, Level Sets, and Crouzeix’s Conjecture

   https://doi.org/10.1007/s11854-023-0295-y  

   Bickel, Kelly; Gorkin, Pamela (April 2024, Journal d'Analyse Mathématique)

   We study several problems motivated by Crouzeix’s conjecture, which we consider in the special setting of model spaces and compressions of the shift with finite Blaschke products as symbols. We pose a version of the conjecture in this setting, called the level set Crouzeix (LSC) conjecture, and establish structural and uniqueness properties for (open) level sets of finite Blaschke products that allow us to prove the LSC conjecture in several cases. In particular, we use the geometry of the numerical range to prove the LSC conjecture for compressions of the shift corresponding to unicritical Blaschke products of degree 4. 

   more » « less
3. Counterexamples to the Low-Degree Conjecture

   Holmgren, Justin; Wein, Alexander S (April 2021, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021))

   Lee, James R (Ed.)

   A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to. 

   more » « less
4. Ring graphs and Goldberg's bound on chromatic index

   https://doi.org/10.1002/jgt.22494  

   Cao, Yan; Chen, Guantao; He, Shushan; Jing, Guangming (August 2019, Journal of Graph Theory)

   Abstract Let be a multigraph with maximum degree and chromatic index . If is bipartite then . Otherwise, by a theorem of Goldberg, , where denotes the odd girth of . Stiebitz, Scheide, Toft, and Favrholdt in their book conjectured that if then contains as a subgraph a ring graph with the same chromatic index. Vizing's characterization of graphs with chromatic index attaining the Shannon's bound showed the above conjecture holds for . Stiebitz et al verified the conjecture for graphs with and . McDonald proved the conjecture when is divisible by . In this paper, we show that the chromatic index condition alone is not sufficient to give the conclusion in the conjecture. On the positive side, we show that the conjecture holds for every with , and the maximum degree condition is best possible. This positive result leans on the positive resolution of the Goldberg‐Seymour conjecture. 

   more » « less
5. Immersions and Albertson’s Conjecture

   https://doi.org/10.4230/LIPIcs.SoCG.2025.50  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   A graph is said to contain K_k (a clique of size k) as a weak immersion if it has k vertices, pairwise connected by edge-disjoint paths. In 1989, Lescure and Meyniel made the following conjecture related to Hadwiger’s conjecture: Every graph of chromatic number k contains K_k as a weak immersion. We prove this conjecture for graphs with at most 1.4(k-1) vertices. As an application, we make some progress on Albertson’s conjecture on crossing numbers of graphs, according to which every graph G with chromatic number k satisfies cr(G) ≥ cr(K_k). In particular, we show that the conjecture is true for all graphs of chromatic number k, provided that they have at most 1.4(k-1) vertices and k is sufficiently large. 

   more » « less