6 papers
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…
Estimating Hitting Times Locally At Scale
Themistoklis Haris, Fabian Spaeh, Spyros Dragazis +1
Hitting times provide a fundamental measure of distance in random processes, quantifying the expected number of steps for a random walk starting at node to reach node . They…
Compression Barriers for Autoregressive Transformers
Themistoklis Haris, Krzysztof Onak
A key limitation of autoregressive Transformers is the large memory needed at inference-time to cache all previous key-value (KV) embeddings. Prior works address this by compressin…
NN Attention Demystified: A Theoretical Exploration for Scalable Transformers
Themistoklis Haris
Despite their power, Transformers face challenges with long sequences due to the quadratic complexity of self-attention. To address this limitation, methods like -Nearest-Neighb…