Search

Consider the following process of activation on a strongly connected directed graph G ( V , E ) with threshold function ? : V ? N . In round zero, a set of vertices, called the seeds, are active. Thereafter, a vertex v ? V is activated in a round if it has at least ? ( v ) active in-neighbors in the previous round. Once a vertex is activated, it remains active. Sets of seeds activating all vertices after a finite number of rounds are known in the literature as irreversible dynamic monopolies (a.k.a. perfect target sets) corresponding to ( G , ? ) . With ? ( v ) = ? ? deg - ( v ) ? for all v ? V , where deg - ( v ) denotes the indegree of v and ? ? ( 0 , 1 ] , this paper proves the existence of an irreversible dynamic monopoly of size no more than max ? { 4.92 ? | V | , 1 } .

Consider the following reversible cascade on a simple directed graph G=(V,E). In round zero, a set of vertices, called the seeds, are active. In round [email protected]?Z^+, a vertex [email protected]?V is activated (deactivated) if at least (resp., fewer than) @f(v) of its in-neighbors are active in round k-1, where @f:V->N. An irreversible cascade is defined similarly except that active vertices cannot be deactivated. Two specific candidates for the threshold function @f are @f"m"a"j"("v")^s^t^r^i^c^[email protected]?(deg^-(v)+1)/[email protected]? and @f"@r(v)[email protected][email protected]@?deg^-(v)@?, where deg^-(v) denotes the indegree of [email protected]?V and @[email protected]?(0,1]. An irreversible dynamic monopoly is a set of seeds that leads all vertices to activation after finitely many rounds of the irreversible cascade with @[email protected]"m"a"j^s^t^r^i^c^t. A set of vertices, S, is said to be convergent if no vertex will ever change its state, from active to inactive or vice versa, once the set of active vertices equals S. This paper shows that an irreversible dynamic monopoly of size at most @?|V|/[email protected]? can be found in polynomial (in |V|) time if G is strongly connected. Furthermore, we show that for any constant @e>0, all @[email protected]?(0,1], @[email protected]"@r, [email protected]?[([email protected])(ln(e/@r))/n,1] and with probability 1-n^-^@W^(^1^), every convergent set of the Erdos-Renyi random graph G(n,p) has size O(@[email protected]@?) or n-O(@[email protected]@?). Our result on convergent sets holds for both the reversible and irreversible cascades.

A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the resource one is interested in) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give an efficient revision algorithm in the model of learning with equivalence and membership queries for threshold functions, and some negative results showing, for instance, that threshold functions cannot be revised efficiently from either type of query alone. The algorithms work in a general revision model where both deletion and addition type revision operators are allowed.

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.