14
votes
Accepted
Finding subgraphs with high treewidth and constant degree
See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers.
We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
11
votes
Random functions of low degree as a real polynomial
Here's an algorithm that beats the trivial attempts.
The following is a known fact (Exercise 1.12 in O'Donnell's book) : If $f:\{-1,1\}^n\to\{-1,1\}$ is a Boolean function which has degree $\le d$ as ...
1
vote
Finding subgraphs with high treewidth and constant degree
In the case of pathwidth, reposting here a comment made to me by email by Benjamin Rossman back in 2020 (see also the comments to the answer https://cstheory.stackexchange.com/a/38943):
Every graph G ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
bounded-degree × 13cc.complexity-theory × 6
graph-theory × 4
boolean-functions × 4
graph-colouring × 4
np-hardness × 2
co.combinatorics × 2
approximation-hardness × 2
randomness × 2
fourier-analysis × 2
graph-algorithms × 1
counting-complexity × 1
graph-isomorphism × 1
planar-graphs × 1
tree × 1
set-cover × 1
treewidth × 1
algebraic-complexity × 1
arithmetic-circuits × 1
hypergraphs × 1
graph-minor × 1
enumeration × 1