and non-monotone circuits [38]. Separations between the power of monotone and

non-monotone span programs is interesting since monotone span programs can

be exponentially more powerful than monotone circuits [2].

Finally, our result implies the same lower bound for matching and bipartite

matching. This follows from the projection reduction from directed st-con to

bipartite matching. Babai, G´l, and Wigderson [2] constructed a non-monotone

a

span program, over large enough ¬elds, for matching whose size is n (where n is

the number of edges in the graph). Thus, the same separation between monotone

and non-monotone span programs holds for matching.

1.3 Organization

In Section 2 we de¬ne monotone span programs. In Section 3 we give our ¬rst

proof of the lower bound and in Section 4 we give our second proof of the lower

bound.

2 Preliminaries

2.1 Monotone Span Programs

We start with the de¬nition of monotone span programs. As discussed above,

monotone span programs are equivalent to linear secret sharing schemes; we use

monotone span programs to prove lower bounds on linear secret sharing schemes.

De¬nition 1 (Monotone Span Program [28]). A monotone span program

over a ¬eld F is a triplet M = M, ρ, v , where M is a matrix over F, v is a

nonzero row vector called the target vector (it has the same number of coordinates

as the number of columns in M ), and ρ is a labeling of the rows of M by variables

from {x1 , . . . , xn } (every row is labeled by one variables, and the same variable

can label many rows).

A monotone span program accepts or rejects an input by the following crite-

n

rion. For every input u ∈ {0, 1} de¬ne the sub-matrix Mu of M consisting of

those rows whose labels are satis¬ed by the assignment u. The monotone span

program M accepts u if and only if v ∈ span(Mu ), i.e., some linear combination

of the rows of Mu gives the target vector v. A monotone span program computes

176 A. Beimel and A. Paskin

a Boolean function f if it accepts exactly those inputs u where f (u) = 1. The

size of M is the number of rows in M .1

Monotone span programs compute only monotone functions, and every mono-

tone Boolean function can be computed by a monotone span program. The size of the

smallest monotone span program over F that computes f is denoted by mSPF (f ).

Example 1. Consider the undirected-st-con function, whose input is an undi-

rected graph with two designated nodes s and t and its output is 1 i¬ the graph

contains a path from s to t. Formally, we consider the following function: The

input is an undirected graph with m + 2 nodes; the variables of the function

are the n = m+2 possible edges. Karchmer and Wigderson [28] construct a

2

monotone span program of size n for this function, that is, each edge labels ex-

actly one row in the program (a linear secret sharing scheme equivalent to this

program was previously shown in [10]).

We next describe this span program. Assume the nodes of the input graph

are z0 , . . . , zm+1 , where z0 = s and zm+1 = t. The program has m + 2 columns

and n rows. For every edge (zi , zj ), where i < j, there is a row in the program;

in this row all entries in the row are zero, except for the ith entry which is 1

and the jth entry which is ’1. The target vector is the same as the row labeled

by (s, t), that is, (1, 0, . . . , 0, ’1). It can be proven that over every ¬eld F, this

program computes the undirected-st-con function.

2.2 The st-con Function

In the rest of the paper we will refer to the st-con function in directed graphs as

st-con. Formally, we consider the following function: The input is a directed graph

with m + 2 nodes. The graph contains two designated nodes s, t. The variables are

the n = m(m + 1) possible edges in the graph. The function outputs 1 i¬ there is

a directed path from node s to node t. Our main results are summarized below.

Theorem 1. For every ¬eld F

mSPF (st-con) = ©(n1.5 ).

Theorem 2. For every ¬nite ¬eld F and every linear secret sharing scheme over

F realizing st-con the total number of bits in the shares is

©(n1.5 log |F|).

3 First Proof

3.1 Proof Outline

We use the following theorem of G´l [23] to prove our lower bound.

a

1

The choice of the ¬xed nonzero vector v does not a¬ect the size of the span program.

It is always possible to replace v by another nonzero vector v via a change of basis

without changing the function computed and the size of the span program. Most

often v is chosen to be the 1 vector (with all entries equal 1).

On Linear Secret Sharing for Connectivity in Directed Graphs 177

Theorem 3 ([23]). Let f : {0, 1}n ’ {0, 1} be a monotone function. Let U

denote the set of maxterms of f , and V denote the set minterms of f , and let

U ⊆ U, V ⊆ V . If there exists a monotone span program of size s computing

f over a ¬eld F, then there exist matrices F1 , . . . , Fn , each matrix has |U | rows

and |V | columns (each row of the matrix is labeled by a u ∈ U and each column

is labeled by a v ∈ V ) such that

n

i=1 Fi = 1 (that is, the sum of the matrices over F is the all-one matrix).

1.

2. The non-zero entries in Fi are only in rows labeled by a u ∈ U such that

ui = 0 and in columns labeled by a v ∈ V such that vi = 1.

n

i=1 rankF (Fi ) ¤ s.

3.

In this section, we prove the result for GF(2), but the proof easily generalizes

to other ¬nite ¬elds. The skeleton of the proof is as follows. We appropriately

choose subsets U , V of the maxterms and minterms of st-con. We show that for

any matrices F1 , . . . , Fn satisfying (1) and (2) in Theorem 3, there exist “many”

(©(n)) matrices Fe , such that a large fraction (©(1)) of the entries of Fe are

zero entries. Also, every Fe has some “singleton” 1 entries at ¬xed positions,

which are “well-spread” over the matrix. We then prove that every matrix Fe

with “many” zero entries has rank ©(n0.5 ), this proof uses the partial knowledge

on the distribution of singletons, and the large number of zeros. By Theorem 3,

this implies that the size of every monotone span program computing st-con over

GF(2) has at least ©(n0.5 · n) = ©(n1.5 ) rows.

3.2 Details

To apply Theorem 3 we need to understand the minterms and maxterms of

st-con. Every minterm of st-con is a simple directed paths from s to t. Every

maxterm can be speci¬ed by a partition S ∪ T of V with s ∈ S, t ∈ T where

the edges in S — T are excluded and all other edges are included in the maxterm

(that is, the maxterm contains all edges in S — S, T — T , and T — S).

De¬ning U , V : Let w = m/d, where d is some constant to be ¬xed later.2 We ar-

range the nodes of the graph in layers L0 , L1 , . . . , Ld+1 , where L0 = {s}, Ld+1 =

{t}, and all other layers contain w nodes. We consider the restriction st-con

of the st-con function to directed graphs that contain only edges directed from

layer Li to layer Li+1 . Note that the number of edges in the restricted function

st-con is a constant fraction of the number of edges in the function st-con, so

every lower bound for st-con implies the same lower bound for st-con (up to a

constant factor). We de¬ne the subsets U , V as follows. Let V be all the s-t

paths, that is, paths s, v1 , . . . , vd , t, where vi ∈ Li . Let U be the set of all s-t

cuts where 1/2 of the nodes in each layer Li , where 1 < i < d, are in S (and

the other half is in T ). Additionally, {s} ∪ L1 ‚ S and {t} ∪ Ld ‚ T . Note that

w d’2

|V | = wd and |U | = w/2 .

2

As we see later, d = 4 will do.

178 A. Beimel and A. Paskin

Assume there is a monotone span program over F computing st-con and let

F1 , . . . , Fn be the matrices guaranteed by Theorem 3.3 For an edge e = (x, y),

let Re denote the restriction of Fe to rows labeled by a cut u ∈ U such that

ue = 0 (that is, the maxterm does not contain the edge (x, y)) and to columns

labeled by a path v ∈ V such that ve = 1 (that is, the path contains the edge

w d’2

(x, y)). Note that Re has wd’2 = |V |/w2 columns and 0.25 w/2 = |U |/4

rows (as we consider cuts such that x ∈ S and y ∈ T ).4 By (2) in Theorem 3,

rankF (Re ) = rankF (Fe ). We say that Re covers (u, v) if ue = 0 and ve = 1.

Denote the set of edges e such that Re covers (u, v) by S(u, v).

We start with a few simple observations. Obseration 1 and Obseration 2 follow

directly from (1) and (2) in Theorem 3 and the de¬nition of the Re ™s.