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)

• Tight Bounds for Learning a Mixture of Two Gaussians
• Graph spanners: a tutorial review
• 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
• The Power of Dynamic Distance Oracles
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Sum of Squares Lower Bounds from Pairwise Independence
• An axiomatic approach to time-dependent shortest path oracles
• 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
• Distance oracles for time-dependent networks
• Sparse Quantum Codes from Quantum Circuits
• Beyond the Euler Characteristic
• Preserving Statistical Validity in Adaptive Data Analysis
• Random Permutations using Switching Networks
• Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
• 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
• 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
• Robust Distance Queries on Massive Networks
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Central Positions in Social Networks
• 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
• 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
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
• On the Complexity of Nash Equilibria in Anonymous Games
• Quantum spectrum testing
• A lower bound for the quickest path problem
• 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
• 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
• Computing source-to-target shortest paths for complex networks in RDBMS
• 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
• Online Submodular Welfare Maximization
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
• The Complexity of the Simplex Method
• Local, Private, Efficient Protocols for Succinct Histograms
• Search-Space Size in Contraction Hierarchies
• Greedy Algorithms for Steiner Forest
• Fast Matrix Multiplication
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Clustered Integer 3SUM via Additive Combinatorics
• Bypassing KLS
• Faster Canonical Forms for Primitive Coherent Configurations
• On the Lovász Theta function for Independent Sets in Sparse Graphs
• Consistency thresholds for the planted bisection model
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• On computing the diameter of real-world undirected graphs
• Bi-criteria path problem with minimum length and maximum survival probability
• Excluded Grid Theorem
• Sum-of-squares Lower Bounds for Planted Clique
• Prioritized Metric Structures and Embedding
• Almost Optimal Pseudorandom Generators for Spherical Caps
• An efficient oracle for counting shortest paths in planar graphs
• An efficient oracle for counting shortest paths in planar graphs
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
• Density Independent Algorithms for Sparsifying k-Step Random Walks
• A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
• A Characterization of the Capacity of Online (causal) Binary Channels
• A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds

This page was built for software: Graphs