Research
Research
Research
Research
31+ open-access research outputs.
We study compiled AI, a paradigm in which large language models generate executable code artifacts during a compilation phase, after which workflows execute deterministically without further model inv…
Civilization maintains an elaborate infrastructure devoted to the maintenance of synchronized time. Governments mandate daylight saving time. Standards bodies insert leap seconds into Coordinated Univ…
We present a family of fast pseudo-approximation algorithms for the minimum balanced vertex separator problem in a graph. Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, and a (constant) bala…
The Markov approximation is arguably the most ubiquitous tool in physics, underpinning quantum master equations, stochastic processes, and -- via Shannon's channel model and Lamport's logical clocks -…
This is the first of five papers comprising The Semantic Arrow of Time. The argument begins with a claim: computing's arrow of time is semantic, not thermodynamic. The direction in which meaning is pr…
The foundational impossibility results of distributed computing -- the Fischer-Lynch-Paterson theorem, the Two Generals Problem, the CAP theorem -- are widely understood as discoveries about the physi…
In April 2024, the White House directed NASA to establish Coordinated Lunar Time (LTC) by December 2026. The programme assumes that a unified time standard can be constructed by deploying atomic clock…
Since its introduction in the early 90s, the web has become the largest application platform available globally. HyperText Markup Language (HTML) has been an essential part of the web since the beginn…
Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys. There are mainly two classes of KLE techniques, cascade encryption and…
Emotion recognition using electroencephalography (EEG) signals has attracted increasing attention in recent years. However, existing methods often lack generalization in cross-corpus settings, where a…
For a set of points in $\mathbb{R}^d$, the Euclidean $k$-means problems consists of finding $k$ centers such that the sum of distances squared from each data point to its closest center is minimized. …
We present a $O(1)$-approximate fully dynamic algorithm for the $k$-median and $k$-means problems on metric spaces with amortized update time $\tilde O(k)$ and worst-case query time $\tilde O(k^2)$. W…
Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqrt{(\log n)/\varepsil…
The maximum weighted matching (MWM) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the rece…
In the stochastic weighted matching problem, the goal is to find a large-weight matching of a graph when we are uncertain about the existence of its edges. In particular, each edge $e$ has a known wei…
Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient solvers, both in theo…
Information extraction from semi-structured documents is crucial for frictionless business-to-business (B2B) communication. While machine learning problems related to Document Information Extraction (…
In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivalent to the basic line…
Multiplicative cut sparsifiers, introduced by Bencz\'ur and Karger [STOC'96], have proved extremely influential and found various applications. Precise characterisations were established for sparsifia…
The recent growth of the Internet of Things (IoT) devices has lead to the rise of various complex applications where these applications involve interactions among large numbers of heterogeneous device…
Free open-access publishing with Google Scholar indexing.
Submission Guide →