Faster all-pairs shortest paths via circuit complexity
From MaRDI portal
Publication:5259602
DOI10.1145/2591796.2591811zbMath1315.68282arXiv1312.6680OpenAlexW2064790310WikidataQ56078256 ScholiaQ56078256MaRDI QIDQ5259602
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.6680
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20)
Related Items (44)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A Sparsified Four-Russian Algorithm for RNA Folding ⋮ Minimax regret 1-sink location problem with accessibility in dynamic general networks ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Unnamed Item ⋮ Subquadratic algorithms for succinct stable matching ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Constant-Round Interactive Proof Systems for AC0[2 and NC1] ⋮ A new coding-based algorithm for finding closest pair of vectors ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Improved bounds for rectangular monotone min-plus product and applications ⋮ Average-case complexity of the min-sum matrix product problem ⋮ Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness of RNA folding problem with four symbols ⋮ Anti-concentration for polynomials of independent random variables ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ The idemetric property: when most distances are (almost) the same ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ Approximating the minimum cycle mean ⋮ Algebraic methods in the congested clique ⋮ A spectral approach to the shortest path problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Efficient single-pair all-shortest-path query processing for massive dynamic networks ⋮ Unnamed Item ⋮ Smallest k-enclosing rectangle revisited ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Percolation centrality via Rademacher Complexity ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
This page was built for publication: Faster all-pairs shortest paths via circuit complexity
