Source author record

Peter Manohar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Let $\mathcal{H}(k,n,p)$ be the distribution on $k$ -uniform hypergraphs where every subset of $[n]$ of size $k$ is included as an hyperedge with probability $p$ independently. In this work, we design and analyze a simple spectral algorithm that certifies a bound on the size of the largest clique, $ω(H)$ , in hypergraphs $H \sim \mathcal{H}(k,n,p)$ . For example, for any constant $p$ , with high probability over the choice of the hypergraph, our spectral algorithm certifies a bound of $\tilde{O}(\sqrt{n})$ on the clique number in polynomial time. This matches, up to $\textrm{polylog}(n)$ factors, the best known certificate for the clique number in random graphs, which is the special case of $k = 2$ . Prior to our work, the best known refutation algorithms [CGL04, AOW15] rely on a reduction to the problem of refuting random $k$ -XOR via Feige's XOR trick [Fei02], and yield a polynomially worse bound of $\tilde{O}(n^{3/4})$ on the clique number when $p = O(1)$ . Our algorithm bypasses the XOR trick and relies instead on a natural generalization of the Lovasz theta semidefinite programming relaxation for cliques in hypergraphs.

preprint2020arXiv

Lower Bounds for Caching with Delayed Hits

Caches are a fundamental component of latency-sensitive computer systems. Recent work of [ASWB20] has initiated the study of delayed hits: a phenomenon in caches that occurs when the latency between the cache and backing store is much larger than the time between new requests. We present two results for the delayed hits caching model. (1) Competitive ratio lower bound. We prove that the competitive ratio of the algorithm in [ASWB20], and more generally of any deterministic online algorithm for delayed hits, is at least Omega(kZ), where k is the cache size and Z is the delay parameter. (2) Antimonotonicity of the delayed hits latency. Antimonotonicity is a naturally desirable property of cache latency: having a cache hit instead of a cache miss should result in lower overall latency. We prove that the latency of the delayed hits model is not antimonotone by exhibiting a scenario where having a cache hit instead of a miss results in an increase in overall latency. We additionally present a modification of the delayed hits model that makes the latency antimonotone.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.