Add to ORKGWe investigate the average-case complexity of the k-CLIQUE problem on randomgraphs with an appropriate density of edges. Our results are lower bounds of nk=4 fortwo well-studied classes of circuits: bounded-depth circuits and monotone circuits. Besidesbeing the first lower bounds for k-CLIQUE in the average-case (and moreoveressentially tight), these results lead to a new “size hierarchy theorem” for AC0 and settlea longstanding open question in finite model theory.ERATOセミナ2010 : No.38. 2011年3月7
AbstractWe define CliqueN(n) to be the problem Clique restricted to the set of graphs G = (V, E) suc...
Given a simple graph G and an integer k, the goal of the k-Clique problem is to decide if G contains...
AbstractWe prove an exponential lower bound for the majority function on constant depth monotone cir...
The computational problem of testing whether a graph contains a complete subgraph of size k is among...
We prove that for k ≪4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi g...
We prove that for k ≫; 4√n regular resolution requires length nω(k) to establish that an ErdÅ's-Rény...
This paper gives the first correlation bounds under product distributions (including the uni-form di...
The class P is in fact a proper sub-class of NP. We explore topological properties of the Hamming sp...
Finding a maximum clique in a graph is one of the most basic computational problems on graphs. The v...
This paper proposes three new analytical lower bounds on the clique number of a graph and compares t...
AbstractWe prove a lower bound, exponential in the eighth root of the input length, on the size of m...
We prove that, unless any problem in NP can be solved in proba-bilistic polynomial time, for any >...
We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MK...
We study average-case complexity of branch-and-bound for maximum independent set in random graphs un...
We study average-case complexity of branch-and-bound for max independent set in random graphs under ...
AbstractWe define CliqueN(n) to be the problem Clique restricted to the set of graphs G = (V, E) suc...
Given a simple graph G and an integer k, the goal of the k-Clique problem is to decide if G contains...
AbstractWe prove an exponential lower bound for the majority function on constant depth monotone cir...
The computational problem of testing whether a graph contains a complete subgraph of size k is among...
We prove that for k ≪4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi g...
We prove that for k ≫; 4√n regular resolution requires length nω(k) to establish that an ErdÅ's-Rény...
This paper gives the first correlation bounds under product distributions (including the uni-form di...
The class P is in fact a proper sub-class of NP. We explore topological properties of the Hamming sp...
Finding a maximum clique in a graph is one of the most basic computational problems on graphs. The v...
This paper proposes three new analytical lower bounds on the clique number of a graph and compares t...
AbstractWe prove a lower bound, exponential in the eighth root of the input length, on the size of m...
We prove that, unless any problem in NP can be solved in proba-bilistic polynomial time, for any >...
We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MK...
We study average-case complexity of branch-and-bound for maximum independent set in random graphs un...
We study average-case complexity of branch-and-bound for max independent set in random graphs under ...
AbstractWe define CliqueN(n) to be the problem Clique restricted to the set of graphs G = (V, E) suc...
Given a simple graph G and an integer k, the goal of the k-Clique problem is to decide if G contains...
AbstractWe prove an exponential lower bound for the majority function on constant depth monotone cir...