Expected Complexity of Graph Partitioning Problems

No abstract is available for this paper.

• Publication year

  1995

• Venue

  Discrete Applied Mathematics

• Publication date

  1995-02-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0166-218X(94)00103-K
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Simulated annealing for graph bisection

  1993cited by this paper
• The Greedy Coloring Is a Bad Probabilistic Algorithm

  1991cited by this paper
• Graphs with Small Chromatic Numbers are Easy to Color

  1989cited by this paper
• The Solution of Some Random NP-Hard Problems in Polynomial Expected Time

  1989influential reference
• The chromatic number of random graphs

  1988cited by this paper
• Almost All k-Colorable Graphs are Easy to Color

  1988cited by this paper
• Eigenvalues and graph bisection: An average-case analysis

  1987cited by this paper
• Colouring random graphs

  1984cited by this paper
• Expected Behavior of Graph Coloring Algorithms

  1977cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• The statistical threshold for planted matchings and spanning trees

  2026cites this paper
• Information-Theoretic Limits on Exact Subgraph Alignment Problem

  2026cites this paper
• On Approximate Computation of Critical Points

  2026cites this paper
• Detecting weighted hidden cliques

  2025cites this paper
• Candidate range limitation for efficient rainbow clique detection

  2025cites this paper
• On Finding Randomly Planted Cliques in Arbitrary Graphs

  2025cites this paper
• Quantum Annealing for Minimum Bisection Problem: A Machine Learning-based Approach for Penalty Parameter Tuning

  2025cites this paper
• The Fundamental Limits of Recovering Planted Subgraphs

  2025cites this paper
• Computational Lower Bounds for No-Regret Learning in Normal-Form Games

  2025cites this paper
• Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy 𝑘-LIN over Expanders

  2025influential citation
• Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection

  2025cites this paper
• "All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery (Extended Abstract)

  2025cites this paper
• On optimal distinguishers for Planted Clique

  2025cites this paper
• Finding Planted Cycles in a Random Graph

  2025cites this paper
• Planted clique recovery in random geometric graphs

  2025influential citation
• Barriers to Welfare Maximization with No-Regret Learning

  2024cites this paper
• Information-Theoretic Thresholds for Planted Dense Cycles

  2024cites this paper
• Planted Clique Conjectures Are Equivalent

  2024cites this paper
• Low-degree phase transitions for detecting a planted clique in sublinear time

  2024cites this paper
• Smarter k-Partitioning of ZX-Diagrams for Improved Quantum Circuit Simulation

  2024cites this paper
• Semirandom Planted Clique and the Restricted Isometry Property

  2024cites this paper
• Quantum community detection via deterministic elimination

  2024cites this paper
• Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration

  2024cites this paper
• Low-degree Security of the Planted Random Subgraph Problem

  2024cites this paper
• A Short Review on Novel Approaches for Maximum Clique Problem: from Classical algorithms to Graph Neural Networks and Quantum algorithms

  2024cites this paper
• Finding planted cliques using gradient descent

  2023cites this paper
• Detecting a Planted Bipartite Graph

  2023cites this paper
• Planted Bipartite Graph Detection

  2023cites this paper
• Is Planted Coloring Easier than Planted Clique?

  2023cites this paper
• Hardness Self-Amplification: Simplified, Optimized, and Unified

  2023influential citation
• Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs

  2022cites this paper
• Spectral Algorithms Optimally Recover Planted Sub-structures

  2022cites this paper
• Almost‐Linear Planted Cliques Elude the Metropolis Process

  2022cites this paper
• Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

  2022cites this paper
• Algorithms Approaching the Threshold for Semi-random Planted Clique

  2022cites this paper
• Exact recovery algorithm for Planted Bipartite Graph in Semi-random Graphs

  2022cites this paper
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning

  2022cites this paper
• Robustness of average-case meta-complexity via pseudorandomness

  2022cites this paper
• A degree 4 sum-of-squares lower bound for the clique number of the Paley graph

  2022cites this paper
• A Planted Clique Perspective on Hypothesis Pruning

  2022cites this paper
• Washington University Open Scholarship Washington University Open Scholarship

  2022cites this paper
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations

  2022cites this paper
• Average-Case Communication Complexity of Statistical Problems

  2021cites this paper
• SOS lower bound for exact planted clique

  2021cites this paper
• Pseudorandom Self-Reductions for NP-Complete Problems

  2021cites this paper
• Convex Formulation for Planted Quasi-Clique Recovery

  2021cites this paper
• Logspace Reducibility From Secret Leakage Planted Clique

  2021cites this paper
• Robust Estimation for Random Graphs

  2021cites this paper
• Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

  2021cites this paper
• Finding Planted Cliques in Sublinear Time

  2020cites this paper
• Is the space complexity of planted clique recovery the same as that of detection?

  2020cites this paper
• Distributional Analysis

  2020cites this paper
• Statistical and Computational Rates in Graph Logistic Regression

  2020cites this paper
• Learning fine-grained search space pruning and heuristics for combinatorial optimization

  2020cites this paper
• How to Hide a Clique?

  2020cites this paper
• Exact recovery of Planted Cliques in Semi-random graphs

  2020influential citation
• Two-Sample Testing on Pairwise Comparison Data and the Role of Modeling Assumptions

  2020cites this paper
• CSP-Completeness And Its Applications

  2020cites this paper
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions

  2020cites this paper
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

  2020cites this paper
• On the hardness of designing public signals

  2019cites this paper
• Beyond the Worst-Case Analysis of Algorithms

  2019cites this paper
• Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators

  2019cites this paper
• Statistical inference on graphs: Selected Topics∗

  2019cites this paper
• Optimal estimation in high-dimensional and nonparametric models

  2019cites this paper
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

  2019cites this paper
• Some lower bounds in parameterized AC0

  2019cites this paper
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property

  2019cites this paper
• Finding a planted clique by adaptive probing

  2019cites this paper
• Asymptotic performance of the Grimmett-McDiarmid heuristic

  2019cites this paper
• Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

  2019cites this paper
• Random Graphs (2017)

  2019cites this paper
• Hardness of Approximation Between P and NP

  2019cites this paper
• Graph Theory-Based Approach to Accomplish Complete Coverage Path Planning Tasks for Reconfigurable Robots

  2019cites this paper
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons

  2019cites this paper
• Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems

  2019cites this paper
• Approximation and Hardness: Beyond P and NP

  2019cites this paper
• The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs

  2019cites this paper
• Quantum Spectral Algorithms for Planted Clique

  2019cites this paper
• Public-Key Cryptography in the Fine-Grained Setting

  2019cites this paper
• On the Power of Symmetric Linear Programs

  2019cites this paper
• Clique is hard on average for regular resolution

  2018cites this paper
• Statistical Inference and the Sum of Squares Method

  2018cites this paper
• Non-Convex Matrix Completion Against a Semi-Random Adversary

  2018cites this paper
• Optimal link prediction with matrix logistic regression

  2018cites this paper
• Correlation clustering methodologies and their fundamental results

  2018cites this paper
• Hardness Amplification in Two Prover Game and Communication Complexity

  2018influential citation
• Hard optimization problems have soft edges

  2018cites this paper
• An Iterative Spectral Approach to Recovering Planted Partitions

  2018cites this paper
• A New Algorithm for the Robust Semi-random Independent Set Problem

  2018cites this paper
• Sub-Gaussian Mean Estimation in Polynomial Time

  2018cites this paper
• Unsupervised Alignment of Embeddings with Wasserstein Procrustes

  2018cites this paper
• О задаче приближенного нахождения максимальной двудольной клики

  2018cites this paper
• Mean estimation with sub-Gaussian rates in polynomial time

  2018cites this paper
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm

  2018cites this paper
• Random Matrices and the Sum-of-Squares Hierarchy

  2017cites this paper
• Tensor SVD: Statistical and Computational Limits

  2017cites this paper
• CS 264 : Beyond Worst-Case Analysis Lectures # 9 and 10 : Spectral Algorithms for Planted Bisection ( a . k . a . Community Detection ) and Planted Clique ∗

  2017cites this paper
• Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis

  2017cites this paper
• The Complexity of Public-Key Cryptography

  2017cites this paper