6 papers · 1 filter
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…
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…
Counting Simplices in Hypergraph Streams
Amit Chakrabarti, Themistoklis Haris
We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied pro…