scientific article; zbMATH DE number 6866332
From MaRDI portal
Publication:4638096
DOI10.4230/LIPIcs.ITCS.2017.42zbMath1402.68106arXiv1611.08326MaRDI QIDQ4638096
Publication date: 3 May 2018
Full work available at URL: https://arxiv.org/abs/1611.08326
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Which problems have strongly exponential complexity?
- Can Almost Everybody be Almost Happy?
- An Axiomatic Approach to Community Detection
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
- Inapproximability Results for Approximate Nash Equilibria
- Two-query PCP with subconstant error
- The Complexity of Satisfiability of Small Depth Circuits
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Interactive proofs and the hardness of approximating cliques
- ETH Hardness for Densest-k-Subgraph with Perfect Completeness
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs
- Constant factor approximation for balanced cut in the PIE model
- How robust are reconstruction thresholds for community detection?
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
- Clustering Social Networks
- Finding Endogenously Formed Communities
- On the complexity of \(k\)-SAT
This page was built for publication:
