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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
- 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
- Unnamed Item
- Unnamed Item
This page was built for publication: Faster all-pairs shortest paths via circuit complexity
