9 papers
Testing k-submodularity
Themistoklis Haris, Diptaksho Palit
We initiate the study of property testing for -submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While $…
Efficient Algorithms for Influence Maximization in General Models and Observed Cascades
Fabian Spaeh, Themistoklis Haris, Alina Ene +1
We study influence maximization in general stochastic models, the observed cascades model, and the independent cascade (IC) model. For general stochastic models with only black-box…
Symmetry Reveals Layerwise Dynamics: How Transformers Perform In-Context Classification
Patrick Lutz, Themistoklis Haris, Arjun Chandra +2
Transformers can perform in-context classification from a few labeled examples, yet the inference-time algorithm remains opaque. We study multi-class linear classification in the h…
Noise Stability of Transformer Models
Themistoklis Haris, Zihan Zhang, Yuichi Yoshida
Understanding simplicity biases in deep learning offers a promising path toward developing reliable AI. A common metric for this, inspired by Boolean function analysis, is average…
Fast-MWEM: Private Data Release in Sublinear Time
Themistoklis Haris, Steve Choi, Mutiraj Laksanawisit
The Multiplicative Weights Exponential Mechanism (MWEM) is a fundamental iterative framework for private data analysis, with broad applications such as answering linear queries…
Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
Alexandr Andoni, Themistoklis Haris, Esty Kelman +1
We study the Approximate Nearest Neighbor (ANN) problem under a powerful adaptive adversary that controls both the dataset and a sequence of queries. Primarily, for the high-di…