Entity usage

This page lists pages that use the given entity (e.g. Q42). The list is sorted by descending page ID, so that newer pages are listed first.

Showing below up to 50 results in range #1 to #50.

How robust are reconstruction thresholds for community detection?: Label: en
Semidefinite programs on sparse random graphs and their application to community detection: Label: en
Base collapse of holographic algorithms: Label: en
Basis collapse for holographic algorithms over all domain sizes: Label: en
Bipartite perfect matching is in quasi-NC: Label: en
Beating CountSketch for heavy hitters in insertion streams: Label: en
On approximating functions of the singular values in a stream: Label: en
Streaming algorithms for embedding and computing edit distance in the low distance regime: Label: en
Tight bounds for single-pass streaming complexity of the set cover problem: Label: en
Graph isomorphism in quasipolynomial time [extended abstract]: Label: en
Explicit two-source extractors and resilient functions: Label: en
Reed-Muller codes achieve capacity on erasure channels: Label: en
Poly-logarithmic Frege depth lower bounds via an expander switching lemma: Label: en
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits: Label: en
On the size of homogeneous and of depth four formulas with low individual degree: Label: en
Near-optimal small-depth lower bounds for small distance connectivity: Label: en
Routing under balance: Label: en
Approximating connectivity domination in weighted bounded-genus graphs: Label: en
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting: Label: en
Improved approximation for node-disjoint paths in planar graphs: Label: en
Enumerating parametric global minimum cuts by random interleaving: Label: en
Ramanujan coverings of graphs: Label: en
Deterministic and probabilistic binary search in graphs: Label: en
Fault tolerant subgraph for single source reachability: generic and optimal: Label: en
Contention resolution with log-logstar channel accesses: Label: en
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths: Label: en
A lower bound for the distributed Lovász local lemma: Label: en
Distributed (∆+1)-coloring in sublogarithmic rounds: Label: en
A discrete and bounded envy-free cake cutting protocol for four agents: Label: en
Do prices coordinate markets?: Label: en
The sample complexity of auctions with side information: Label: en
New deterministic approximation algorithms for fully dynamic matching: Label: en
Deterministic decremental single source shortest paths: beyond the o(mn) bound: Label: en
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made: Label: en
Cell-probe lower bounds for dynamic problems via a new communication model: Label: en
The 4/3 additive spanner exponent is tight: Label: en
A tight space bound for consensus: Label: en
Online matching: haste makes waste!: Label: en
Beyond matroids: secretary problem and prophet inequality with general constraints: Label: en
Parallel exhaustive search without coordination: Label: en
Extractors for sumset sources: Label: en
Non-malleable extractors and codes, with their many tampered extensions: Label: en
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs: Label: en
Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time: Label: en
Weighted low rank approximations with provable guarantees: Label: en
Optimal principal component analysis in distributed and streaming models: Label: en
Efficiently decoding Reed-Muller codes from random errors: Label: en
Repairing Reed-solomon codes: Label: en
Maximizing determinants under partition constraints: Label: en
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors: Label: en