8 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…
SPARSE-PIVOT: Dynamic correlation clustering for node insertions
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsi…
Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
Given a graph with positive and negative edge labels, the correlation clustering problem aims to cluster the nodes so to minimize the total number of between-cluster positive and w…
Improved Approximation for the Directed Spanner Problem
Arnab Bhattacharyya, Konstantin Makarychev
We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of , for all k >= 3. This improv…