It is shown that up to logarithmic factors, generalized sorting is no harder than ordinary sorting, and a randomized algorithm is given that uses $O(n \log^4 n)$ comparisons in expectation.
Sanjeev Khanna, Aaron L. Putterman, Jun-Kai Song· 0 citations
How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic dynamic streaming algorithms for graph connectivity. Towards answering this question, we study the deterministic one-way communication problem in whic...
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan· 0 citations
Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges. For example, even covers--which check if each vertex appears in an even number of hyperedges--have found much success recently in the study of locally decodable codes. Inspired by a recently-emerging line of work on...
Joshua Brakensiek, V. Guruswami, Aaron L. Putterman· 1 citation
We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly...
Joshua Brakensiek, Aaron L. Putterman, Amatya Sharma et al.· 0 citations
We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\varepsilon>0$ and centrally symmetric, convex sets $C_1, \ldots, C_m\subseteq\mathbb{R}^n$ there...
Arpon Basu, Joshua Brakensiek, Ye-Yuan Chen et al.· 0 citations
This work begins a systematic study of basic problems in directed \emph{acyclic} graphs (DAGs) and shows that reachability from a single vertex and even topological sorting are both computable in O(n \log^3 n) many cut queries.