Welcome!

In this website I will be writing about things I find interesting. I hope you stick around!

About me

I am a PhD student at Boston University. I am advised by Krzysztof Onak. In the past, I was also fortunate to work with Alina Ene at BU, and Amit Chakrabarti as an undergrad at Dartmouth College. Before starting grad school, I spent two years as a software engineer at Microsoft working on virtualization and the Windows Kernel, with the Base Kernel Team.

I study Theoretical Computer Science (TCS) and its applications on Machine Learning and Deep Learning. I have recently been excited about the following topics:

• Adversarially Robust Streaming Algorithms
• Differentially Private Mechanisms
• Efficient Algorithms for Approximating Self-Attention in Sparse Transformer Models
• Spectral Graph Theory and Random Processes
• Submodular Function Maximization
• Fine-Grained Average-Case Complexity Theory

I often blog about things I find interesting.

Contact

• Email: tharis at bu dot edu.
• Google Scholar!
• LinkedIn
• DBLP

Publications and Ongoing work

2024

1. $k$-NN Demystified: A Theoretical Exploration for Scalable Transformers, Themistoklis Haris

   • Main idea: We provide a theoretical analysis of $k$-NN Attention in Transformer models by using an expectation-based reformulation, lazy Gumbel Sampling and $k$-NN data structures. We also give novel algorithms for approximating the attention gradients.

2. Adversarial Robustness for Search Problems: The case of Locality Sensitive Hashing (under review), Themistoklis Haris, Krzysztof Onak, Esty Kelman, Alex Andoni

   • Main idea: We give theoretical frameworks for solving search problems robustly, by using techniques from the literature of differential privacy and fairness. We focus on the problem of approximate nearest neighbor search, but our results can be extended to any search problem.

2022

1. Counting Simplices in Hypergraph Streams, Amit Chakrabarti, Themistoklis Haris (ESA 2022)
   • Main idea: A hypergraph simplex generalizes a triangle. It is a collection of $k$ vertices for which all $k$ possible $(k-1)$-subsets are present hyperedges. We tackle the problem of counting these structures in a uniform hypergraph stream in low-memory regimes. We also provide lower bounds for this problem using communication complexity techniques.

2020

1. [Teaching American Sign Language In Mixed Reality], Qijia Shao, Amy Sniffen, Julien Blanchet, Megan E Hillis, Xinyu Shi, Themistoklis Haris, Jason Liu, Jason Lamberton, Melissa Malzkuhn, Lorna C Quandt, James Mahoney, David JM Kraemer, Xia Zhou, Devin Balkcom (Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies)