Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs
110
0
0.0
(
0
)
Added by
Sergio Caracciolo
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4, whereas for k=3, there exists a polynomial-time algorithm based on Lovasz theory of polymatroid matching. Here we give a completely different, randomized polynomial-time algorithm in the case k=3. The main ingredients are a Pfaffian formula by Vaintrob and one of the authors (G.M.) for a polynomial that enumerates spanning hypertrees with some signs, and a lemma on the number of roots of polynomials over a finite field.
rate research
Read More
It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is $log$-complete in $Pi_2^p$. It had been shown quite recently that already the containment problem for multi-dimensional linear sets is $log$-complete in $Pi_2^p$ (where hardness even holds for a unary encoding of the numerical input parameters). In this paper, we show that already the containment problem for $1$-dimensional linear sets (with binary encoding of the numerical input parameters) is $log$-hard (and therefore also $log$-complete) in $Pi_2^p$. However, combining both restrictions (dimension $1$ and unary encoding), the problem becomes solvable in polynomial time.
Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f in mathbb{F}[x_1,ldots, x_n] $ (where $mathbb{F}$ = $mathbb{Q}$ or $mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $fequiv 0$ or not in time $ 2^d text{ poly}(n,s) $.
The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi in cite{FF} conjectured that the $r$-graph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-graphs with $m$ edges. In this paper, we give some partial results for this conjecture.
We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials having $n$ variables and defined over constant-degree expander graphs, have monotone arithmetic complexity $2^{Omega(n)}$. This yields the first strongly exponential lower bound on the monotone arithmetic circuit complexity for a polynomial in VP. Before this result, strongly exponential size monotone lower bounds were known only for explicit polynomials in VNP (Gashkov-Sergeev12, Raz-Yehudayoff11, Srinivasan20, Cavalar-Kumar-Rossman20, Hrubes-Yehudayoff21). Recently, Hrubes20 initiated a program to prove lower bounds against general arithmetic circuits by proving $epsilon$-sensitive lower bounds for monotone arithmetic circuits for a specific range of values for $epsilon in (0,1)$. We consider the spanning tree polynomial $ST_{n}$ defined over the complete graph on $n$ vertices and show that the polynomials $F_{n-1,n} - epsilon cdot ST_{n}$ and $F_{n-1,n} + epsilon cdot ST_{n}$ defined over $n^2$ variables, have monotone circuit complexity $2^{Omega(n)}$ if $epsilon geq 2^{-Omega(n)}$ and $F_{n-1,n} = prod_{i=2}^n (x_{i,1} +cdots + x_{i,n})$ is the complete set-multilinear polynomial. This provides the first $epsilon$-sensitive exponential lower bound for a family of polynomials inside VP. En-route, we consider a problem in 2-party, best partition communication complexity of deciding whether two sets of oriented edges distributed among Alice and Bob form a spanning tree or not. We prove that there exists a fixed distribution, under which the problem has low discrepancy with respect to every nearly-balanced partition. This result could be of interest beyond algebraic complexity.
There is a remarkable connection between the maximum clique number and the Lagrangian of a graph given by T. S. Motzkin and E.G. Straus in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we explore evidences that the Lagrangian of a 3-uniform hypergraph is related to the order of its maximum cliques when the number of edges of the hypergraph is in certain range. In particular, we present some results about a conjecture introduced by Y. Peng and C. Zhao (2012) and describe a combinatorial algorithm that can be used to check the validity of the conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
