Research
Research
Research
Research
1,641+ open-access research outputs.
The problem of determining whether a probabilistic program terminates almost surely (i.e.~with probability one) is undecidable, and actually $\Pi^0_2$-complete. For this reason, a growing literature h…
Despite the operational importance of hot fixes, large-scale evidence on how they reshape routine maintenance workflows, particularly in the era of autonomous coding agents, remains limited. We analys…
Let $G=(V,E)$ be a weighted undirected graph, with $n$ vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of \cite{TZ01}…
We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching $(e^{1/e}\approx 1.445)$-approximation via the rounding algorithm of Feng and…
Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art $3.1n - o(n)$ bound for affine dispersers (STOC 2…
A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LNW14] established an …
For a nonnegative integer $r$ and a positive integer $v$ satisfying \[ \frac{r(q-1)}{2}<v<\frac{(r+1)(q-1)}{2}, \] we define the combinatorial numbers \[ A_r(v)= \begin{cases} \display…
We prove that, for every fixed $\theta_0>0$, selecting a subset of prescribed cardinality that maximizes the Solow--Polasky diversity indicator is NP-hard for finite point sets in $\mathbb{R}^2$ with …
SAT solving has recently been proven effective in tackling open combinatorial problems. We contribute two additional results in the context of fair distribution of indivisible goods. Specifically,…
The Schur square of linear codes over a finite field has emerged as a fundamental operation in both classical and quantum coding theory. In this paper, we investigate the Schur square problem of Hyper…
For the discrete memoryless sources with a countably infinite alphabet, we prove that for any positive integer $k$, there exists a corresponding probability interval such that if the largest symbol pr…
Weber's conjecture (1886) governs three aspects of lattice-based cryptography: the solvability of the Principal Ideal Problem, the freeness of modules over rings of integers, and the tightness of wors…
We study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there exist absolute constan…
We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong $s$-bloc…
Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random $k$-coloring of a graph w…
Noisy $k$-XOR is a basic average-case inference problem in which one observes random noisy $k$-ary parity constraints and seeks to recover, or more weakly, detect, a hidden Boolean assignment. A centr…
Database research and the development of learned query optimisers rely heavily on realistic SQL workloads. Acquiring real-world queries is increasingly difficult, however, due to strict privacy regula…
Generalized finite automata (GFAs), probabilistic finite automata (PFAs), and one-way general quantum finite automata (1gQFA) recognize the same strict-cutpoint languages, but the state complexity of …
We study two conjectures posed in the analysis of Boolean functions $f : \{-1, 1\}^n \to \{-1, 1\}$, in both of which, the Majority function plays a central role: the "Majority is Least Stable" (Benja…
We study linear exact repair for $(n,k,\ell)$ MDS array codes over $\mathbb{F}_q$, with redundancy $r=n-k$, in the regime where $q$, $r$, and $\ell$ are fixed and the code length $n$ varies. A recent …
Free open-access publishing with Google Scholar indexing.
Submission Guide →