Graphs

swMATH12277MaRDI QIDQ24208FDOQ24208

Author name not available (Why is that?)

Described by source

• Shortest-path queries in static networks

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

• A polynomial-time bicriteria approximation scheme for planar bisection
• \(\ell_p\) row sampling by Lewis weights
• A characterization of the capacity of online (causal) binary channels
• Time lower bounds for nonadaptive turnstile streaming algorithms
• Analysis of a classical matrix preconditioning algorithm
• An efficient oracle for counting shortest paths in planar graphs
• An efficient oracle for counting shortest paths in planar graphs
• A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
• The List Decoding Radius of Reed-Muller Codes over Small Fields
• The communication complexity of interleaved group products
• Density independent algorithms for sparsifying \(k\)-step random walks
• On the Lovász theta function for independent sets in sparse graphs
• Matching triangles and basing hardness on an extremely popular conjecture
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Graph spanners: a tutorial review
• Sparse quantum codes from quantum circuits
• Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• Preserving statistical validity in adaptive data analysis (extended abstract)
• Random permutations using switching networks
• Randomized composable core-sets for distributed submodular maximization
• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• The Power of Dynamic Distance Oracles
• Almost Optimal Pseudorandom Generators for Spherical Caps
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Small value parallel repetition for general games
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Nearly-linear time positive LP solver with faster convergence rate
• Inapproximability of Nash equilibrium
• Sketching and embedding are equivalent for norms
• Minimizing flow-time on unrelated machines
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• From independence to expansion and back again
• An axiomatic approach to time-dependent shortest path oracles
• Test-and-set in optimal space
• Robust distance queries on massive networks
• Dimensionality reduction for \(k\)-means clustering and low rank approximation
• Adjacency labeling schemes and induced-universal graphs
• Non-malleable reductions and applications
• 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
• Approximate distance oracles with improved bounds
• The directed grid theorem
• Testing cluster structure of graphs
• Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity
• Succinct randomized encodings and their applications
• Reed-Muller codes for random erasures and errors
• On the complexity of Nash equilibria in anonymous games
• Indistinguishability obfuscation for Turing machines with unbounded memory
• Succinct garbling and indistinguishability obfuscation for RAM programs
• Garbled RAM from one-way functions
• Quantum information complexity
• Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
• Computing with Tangles
• Secretary Problems with Non-Uniform Arrival Order
• Forrelation: a problem that optimally separates quantum from classical computing
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Central Positions in Social Networks
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• FPTAS for \#BIS with degree bounds on one side
• Deterministic global minimum cut of a simple graph in near-linear time
• Leveled fully homomorphic signatures from standard lattices
• How well can graphs represent wireless interference?
• The complexity of the simplex method
• Super-resolution, extremal functions and the condition number of Vandermonde matrices
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Hardness of Graph Pricing Through Generalized Max-Dicut
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
• Local, private, efficient protocols for succinct histograms
• A lower bound for the quickest path problem
• High Parallel Complexity Graphs and Memory-Hard Functions
• Greedy algorithms for Steiner forest
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
• Faster canonical forms for primitive coherent configurations (extended abstract)
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• Excluded grid theorem: improved and simplified
• Computing source-to-target shortest paths for complex networks in RDBMS
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Tight bounds for learning a mixture of two Gaussians (extended abstract)
• Exponential Separation of Information and Communication for Boolean Functions
• Rectangles Are Nonnegative Juntas
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Approximating the Nash social welfare with indivisible items
• Search-space size in contraction hierarchies
• Proof of the satisfiability conjecture for large \(k\)
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Clustered Integer 3SUM via Additive Combinatorics
• On computing the diameter of real-world undirected graphs
• Bi-criteria path problem with minimum length and maximum survival probability
• Inapproximability of combinatorial problems via small LPs and SDPs
• An interactive information odometer and applications
• Lower bounds on the size of semidefinite programming relaxations

This page was built for software: Graphs