ﻻ يوجد ملخص باللغة العربية
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.
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$-com
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 determinis
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
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 co
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 t