34 citations · 136 across the 27 of their papers we have counts for
32 papers
Jailbreaking Open-Weight LLMs via Random Embedding Perturbations
Abhinav Sudhakar Dubey, Scott Sirri, Vaggos Chatziafratis +1
While open-weight models have enjoyed steady progress in capabilities and wide adoption across multiple domains, their safety remains an important concern. One key feature is the a…
Lend Me Your Eyes: Instruction-Aware Text Embeddings via Attention Relay
Yiyuan Luo, Vaggos Chatziafratis
Text embedding models trained with contrastive learning learn to follow task instructions from instruction-paired data, while instruction-tuned LLMs already know how to follow them…
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…
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo
Embedding-based representations in Euclidean space are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that fait…
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…
Tunable Latent Generative Priors for Compressed Sensing and Inverse Problems
Sean Gunn, Jorio Cocola, Oliver De Candido +2
Latent generative models have emerged as powerful priors for solving inverse problems. These models typically represent a class of natural signals at a single, fixed complexity, go…
The Complexity of Finding Local Optima in Contrastive Learning
Jingming Yan, Yiyuan Luo, Vaggos Chatziafratis +3
Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on , often given as a…
Welfare Approximation in Additively Separable Hedonic Games
Martin Bullinger, Vaggos Chatziafratis, Parnian Shahkar
Partitioning a set of items or agents while maximizing the value of the partition is a fundamental algorithmic task. We study this problem in the specific setting of maximizing…
Accelerating data-driven algorithm selection for combinatorial partitioning problems
Vaggos Chatziafratis, Ishani Karmarkar, Yingxi Li +1
Data-driven algorithm selection is a powerful approach for choosing effective heuristics for computational problems. It operates by evaluating a set of candidate algorithms on a co…
Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
Vaggos Chatziafratis, Piotr Indyk
Metric embeddings traditionally study how to map items to a target metric space such that distance lengths are not heavily distorted; but what if we only care to preserve the r…
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
Vaggos Chatziafratis, Konstantin Makarychev
We study the natural problem of Triplet Reconstruction (also Rooted Triplets Consistency or Triplet Clustering), originally motivated in computational biology and relational databa…
On Scrambling Phenomena for Randomly Initialized Recurrent Networks
Vaggos Chatziafratis, Ioannis Panageas, Clayton Sanford +1
Recurrent Neural Networks (RNNs) frequently exhibit complicated dynamics, and their sensitivity to the initialization process often renders them notoriously hard to train. Recent w…
Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas +3
Computing Nash equilibrium policies is a central problem in multi-agent reinforcement learning that has received extensive attention both in theory and in practice. However, provab…
Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds
Sepehr Assadi, Vaggos Chatziafratis, Jakub Łącki +2
The Hierarchical Clustering (HC) problem consists of building a hierarchy of clusters to represent a given dataset. Motivated by the modern large-scale applications, we study the p…
Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem
Clayton Sanford, Vaggos Chatziafratis
Given a target function , how large must a neural network be in order to approximate ? Recent works examine this basic question on neural network \textit{expressivity} from t…
Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
Vaggos Chatziafratis, Mohammad Mahdian, Sara Ahmadian
In this paper, we study a number of well-known combinatorial optimization problems that fit in the following paradigm: the input is a collection of (potentially inconsistent) local…
Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering
Danny Vainstein, Vaggos Chatziafratis, Gui Citovsky +3
Recently, Hierarchical Clustering (HC) has been considered through the lens of optimization. In particular, two maximization objectives have been defined. Moseley and Wang defined…
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
Vaggos Chatziafratis, Neha Gupta, Euiwoong Lee
We present hardness of approximation results for Correlation Clustering with local objectives and for Hierarchical Clustering with dissimilarity information. For the former, we stu…
From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering
Ines Chami, Albert Gu, Vaggos Chatziafratis +1
Similarity-based Hierarchical Clustering (HC) is a classical unsupervised machine learning algorithm that has traditionally been solved with heuristic algorithms like Average-Linka…
Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems
Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas
The expressivity of neural networks as a function of their depth, width and type of activation units has been an important question in deep learning theory. Recently, depth separat…
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto +4
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and t…
Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas +1
Understanding the representational power of Deep Neural Networks (DNNs) and how their structural properties (e.g., depth, width, type of activation unit) affect the functions they…
Adversarially Robust Low Dimensional Representations
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen +1
Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical…