5 papers · 1 filter
Optimal VC Dimension of Contrastive Learning with Margin
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
Contrastive learning is a successful paradigm for learning -dimensional geometric representations from a collection of ``anchor--positive--negative'' triplets ,…
Strong Refutation of Ordering, Phylogenetic, and Ordinary CSPs, and New Satisfiability and Refutation Thresholds for Triplet and Quartet Reconstruction
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
We study phase transitions and algorithms for refuting CSPs arising in hierarchical clustering (as well as ranking, and ordinary CSPs). Here, variables are assigned to leaves o…
Optimal Phylogenetic Reconstruction from Sampled Quartets
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
Quartet Reconstruction, the task of recovering a phylogenetic tree from smaller trees on four species called \textit{quartets}, is a well-studied problem in theoretical computer sc…
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
Max-Cut is a classical graph-partitioning problem where given a graph , the objective is to find a cut which maximizes the number of edges crossing the cut. In…
A Simple Average-case Analysis of Recursive Randomized Greedy MIS
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We revisit the complexity analysis of the recursive version of the randomized greedy algorithm for computing a maximal independent set (MIS), originally analyzed by Yoshida, Yamamo…