Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MATROIDS:
Reports tagged with matroids:
TR04-070 | 22nd June 2004
Leonid Gurvits

#### Combinatorial and algorithmic aspects of hyperbolic polynomials

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$
be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.
The support of such polynomial $p(x_1,...,x_n)$
is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ... more >>> TR12-063 | 17th May 2012 Raghav Kulkarni, Miklos Santha #### Query complexity of matroids Let$\mathcal{M}$be a bridgeless matroid on ground set$\{1,\ldots, n\}$and$f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$be the indicator function of its independent sets. A folklore fact is that$f_\mathcal{M}$is evasive," i.e.,$D(f_\mathcal{M}) = n$where$D(f)$denotes the deterministic decision tree complexity of$f.\$ Here we prove ... more >>>

ISSN 1433-8092 | Imprint