Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > READ-ONCE FORMULAE:
Reports tagged with read-once formulae:
TR09-010 | 29th January 2009
Nikos Leonardos, Michael Saks

Lower bounds on the randomized communication complexity of read-once functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae.

A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... 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