Near-Linear Time Construction of Sparse Neighborhood Covers

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (only showing first 100 items - show all)

Generating sparse 2—spanners
Prioritized Metric Structures and Embedding
Almost Optimal Pseudorandom Generators for Spherical Caps
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
A Characterization of the Capacity of Online (causal) Binary Channels
A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
Analysis of a Classical Matrix Preconditioning Algorithm
L _p Row Sampling by Lewis Weights
The List Decoding Radius of Reed-Muller Codes over Small Fields
The communication complexity of interleaved group products
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Compact roundtrip routing with topology-independent node names
Reed-Muller Codes for Random Erasures and Errors
A new deterministic algorithm for fully dynamic all-pairs shortest paths
Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
FPTAS for #BIS with Degree Bounds on One Side
Faster algorithms for all-pairs small stretch distances in weighted graphs
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
Tight Bounds for Learning a Mixture of Two Gaussians
Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
Approximating the Nash Social Welfare with Indivisible Items
Proof of the Satisfiability Conjecture for Large k
Constant query time $(1 + \epsilon)$-approximate distance oracle for planar graphs
Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
Fast deterministic distributed algorithms for sparse spanners
The Power of Dynamic Distance Oracles
On the Complexity of Random Satisfiability Problems with Planted Solutions
Sum of Squares Lower Bounds from Pairwise Independence
A parallel bio-inspired shortest path algorithm
Small Stretch Pairwise Spanners and Approximate $D$-Preservers
An Interactive Information Odometer and Applications
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Lower Bounds on the Size of Semidefinite Programming Relaxations
Efficiently Learning Ising Models on Arbitrary Graphs
All-pairs nearly 2-approximate shortest paths in $O(n^2 \text{ polylog } n)$ time
Sparse Quantum Codes from Quantum Circuits
Beyond the Euler Characteristic
Preserving Statistical Validity in Adaptive Data Analysis
Random Permutations using Switching Networks
Randomized Composable Core-sets for Distributed Submodular Maximization
Computing with Tangles
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Secretary Problems with Non-Uniform Arrival Order
Small Value Parallel Repetition for General Games
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Inapproximability of Nash Equilibrium
Minimizing Flow-Time on Unrelated Machines
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
Sketching and Embedding are Equivalent for Norms
Ramsey partitions and proximity data structures
From Independence to Expansion and Back Again
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Test-and-Set in Optimal Space
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Adjacency Labeling Schemes and Induced-Universal Graphs
Non-malleable Reductions and Applications
Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
Learning Mixtures of Gaussians in High Dimensions
Approximate k -flat Nearest Neighbor Search
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Randomized Rounding for the Largest Simplex Problem
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Approximate Distance Oracles with Improved Bounds
The Directed Grid Theorem
Sublinear fully distributed partition with applications
Testing Cluster Structure of Graphs
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Hardness of Graph Pricing Through Generalized Max-Dicut
Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Succinct Randomized Encodings and their Applications
Shortest-path queries in static networks
On the Complexity of Nash Equilibria in Anonymous Games
Quantum spectrum testing
Garbled RAM From One-Way Functions
High Parallel Complexity Graphs and Memory-Hard Functions
Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Quantum Information Complexity
Edge-disjoint spanners of complete graphs and complete digraphs
Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
2-Server PIR with Sub-Polynomial Communication
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Forrelation
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Exponential Separation of Information and Communication for Boolean Functions
Rectangles Are Nonnegative Juntas
Toward a unified theory of sparse dimensionality reduction in Euclidean space
How Well Can Graphs Represent Wireless Interference?
Leveled Fully Homomorphic Signatures from Standard Lattices
Dynamic approximate all-pairs shortest paths: breaking the $O(mn)$ barrier and derandomization
Online Submodular Welfare Maximization
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
The Complexity of the Simplex Method
New pairwise spanners
Local, Private, Efficient Protocols for Succinct Histograms

This page was built for publication: Near-Linear Time Construction of Sparse Neighborhood Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210147)