Limits of local algorithms over sparse random graphs
From MaRDI portal
Publication:5892454
DOI10.1145/2554797.2554831zbMath1365.05277OpenAlexW2257861360MaRDI QIDQ5892454
Publication date: 19 May 2017
Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2554797.2554831
Random graphs (graph-theoretic aspects) (05C80) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (30)
Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ Total domination in regular graphs ⋮ Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ Factor of IID Percolation on Trees ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times ⋮ Invariant Gaussian processes and independent sets on regular graphs of large girth ⋮ Asymptotic bounds on total domination in regular graphs ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Finding one community in a sparse graph ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ On the almost eigenvectors of random regular graphs ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Spectral measures of factor of i.i.d. processes on vertex-transitive graphs ⋮ Factors of IID on Trees ⋮ Optimization of the Sherrington--Kirkpatrick Hamiltonian ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Finding a large submatrix of a Gaussian random matrix ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Entropy and expansion ⋮ Local approximation of the maximum cut in regular graphs ⋮ Optimization of mean-field spin glasses ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Surfing on minima of isostatic landscapes: avalanches and unjamming transition ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Walksat Stalls Well Below Satisfiability ⋮ Sofic homological invariants and the Weak Pinsker Property
Cites Work
- Unnamed Item
- A hierarchy of polynomial time lattice basis reduction algorithms
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- (Leveled) fully homomorphic encryption without bootstrapping
- Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
- Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Trapdoors for hard lattices and new cryptographic constructions
- Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
- Evaluating Branching Programs on Encrypted Data
- Bounds for Width Two Branching Programs
- Fully homomorphic encryption using ideal lattices
- Public-key cryptosystems from the worst-case shortest vector problem
- Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
- New lattice-based cryptographic constructions
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- On lattices, learning with errors, random linear codes, and cryptography
- On lattices, learning with errors, random linear codes, and cryptography
This page was built for publication: Limits of local algorithms over sparse random graphs
