共查询到20条相似文献,搜索用时 46 毫秒
1.
Satyanarayana V. Lokam 《Theory of Computing Systems》2003,36(1):71-88
Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n 1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) 3 / ( log log n) 5 ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ 2 cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1]. 相似文献
2.
We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, 1987) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite
planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite
planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a
highly parallel
SPL\mathsf{SPL}
algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier
known bounds of non-uniform
SPL\mathsf{SPL}
by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, 1999) and
NC\mathsf{NC}
2 by Miller and Naor (SIAM J. Comput. 24:1002–1017, 1995), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp.
351–357, 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite
planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for
deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary. 相似文献
3.
4.
Ana Gàl 《Computational Complexity》2001,10(4):277-296
We give a characterization of span program size by a
combinatorial-algebraic measure. The measure we consider is a generalization
of a measure on covers which has been used to prove lower
bounds on formula size and has also been studied with respect to communication
complexity.?In the monotone case our new methods yield lower bounds for
the monotone span program complexity of explicit Boolean functions in
n variables over arbitrary fields, improving the previous lower bounds
on monotone span program size. Our characterization of span program
size implies that any matrix with superpolynomial separation between
its rank and cover number can be used to obtain superpolynomial lower
bounds on monotone span program size. We also identify a property
of bipartite graphs that is suficient for constructing Boolean functions
with large monotone span program complexity.
Received: September 30, 2000. 相似文献
5.
Abstract. We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking,
given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-determined property from the case
when it is ``far' from having this property. Whereas they view graphs as represented by their adjacency matrix and measure
the distance between graphs as a fraction of all possible vertex pairs, we view graphs as represented by bounded-length incidence
lists and measure the distance between graphs as a fraction of the maximum possible number of edges. Thus, while the previous
model is most appropriate for the study of dense graphs, our model is most appropriate for the study of bounded-degree graphs.
In particular, we present randomized algorithms for testing whether an unknown bounded-degree graph is connected, k -connected (for k>1 ), cycle-free and Eulerian. Our algorithms work in time polynomial in 1/ɛ , always accept the graph when it has the tested property, and reject with high probability if the graph is ɛ -far from having the property. For example, the 2-connectivity algorithm rejects (with high probability) any N -vertex d -degree graph for which more than ɛ dN edges need to be added in order to make the graph 2-edge-connected.
In addition we prove lower bounds of Ω(\sqrt N ) on the query complexity of testing algorithms for the bipartite and expander properties. 相似文献
6.
7.
Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC1 . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for
this problem requires depth. This would separate AC1 from NC1. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using
communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem
which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d
2(k log k)1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function
on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof
will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds.
Received: July 30, 1999. 相似文献
8.
Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at
some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous
startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the
agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given
initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous
is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller
of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with
simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains
cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost
of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous
cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous
algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show
a lower bound Ω (n2) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous
algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance
between agents is bounded. 相似文献
9.
L. S. Heath 《Theory of Computing Systems》1997,30(1):51-65
An undirected graph is viewed as a simplicial complex. The notion of a graph embedding of a guest graph in a host graph is
generalized to the realm of simplicial maps. Dilation is redefined in this more general setting. Lower bounds on dilation
for various guest and host graphs are considered. Of particular interest are graphs that have been proposed as communication
networks for parallel architectures. Bhattet al. provide a lower bound on dilation for embedding a planar guest graph in a butterfly host graph. Here, this lower bound is
extended in two directions. First, a lower bound that applies to arbitrary guest graphs is derived, using tools from algebraic
topology. Second, this lower bound is shown to apply to arbitrary host graphs through a new graph-theoretic measure, called
bidecomposability. Bounds on the bidecomposability of the butterfly graph and of thek-dimensional torus are determined. As corollaries to the main lower-bound theorem, lower bounds are derived for embedding
arbitrary planar graphs, genusg graphs, andk-dimensional meshes in a butterfly host graph.
This research was supported by National Science Foundation Grant CCR-9009953. A preliminary version of some of this research
appears in “Lower Bounds for Graph Embeddings via Algebraic Topology (Extended Abstract),”Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993, pp. 311–317. 相似文献
10.
Ruo-Wei Hung 《Theory of Computing Systems》2012,50(4):721-738
A bipartite graph G=(U,W,E) with vertex set V=U∪W is convex if there exists an ordering of the vertices of W such that for each u∈U, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination
problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct,
we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the
same time bound. 相似文献
11.
We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of
(log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of
(log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic
connectivity problems.
Received January 1995; revised February 1997. 相似文献
12.
Beate Bollig 《Information Processing Letters》2008,109(1):41-43
Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are the most common dynamic data structure for Boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. Analyzing the limits of symbolic graph algorithms for the all-pairs-shortest paths problem which work on OBDD-represented graph instances the so-called graph of integer multiplication has been investigated by Sawitzki [D. Sawitzki, Lower bounds on the OBDD size of graphs of some popular functions, in: Proc. of SOFSEM, LNCS, vol. 3381, 2005, pp. 298-309]. Using simple arguments his lower bound of 2n/768−1 on the size of OBDDs representing the graph of integer multiplication is improved up to 2n/24. 相似文献
13.
Stasys Jukna 《Theory of Computing Systems》2010,46(2):301-310
We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1}
n
→{0,1}
m
as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f.
Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic
explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n
3) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n
2log n). 相似文献
14.
We study the complexity of learning arbitrary Boolean functions of n variables by membership queries, if at most r variables are relevant. Problems of this type have important applications in fault searching, e.g. logical circuit testing and generalized group testing. Previous literature concentrates on special classes of such Boolean functions and considers only adaptive strategies. First we give a straightforward adaptive algorithm using O(r2
r
log n) queries, but actually, most queries are asked nonadaptively. This leads to the problem of purely nonadaptive learning. We give a graph-theoretic characterization of nonadaptive learning families, called r-wise bipartite connected families. By the probabilistic method we show the existence of such families of size O(r2
r
log n + r
22
r
). This implies that nonadaptive attribute-efficient learning is not essentially more expensive than adaptive learning. We also sketch an explicit pseudopolynomial construction, though with a slightly worse bound. It uses the common derandomization technique of small-biased k-independent sample spaces. For the special case r = 2, we get roughly 2.275 log n adaptive queries, which is fairly close to the obvious lower bound of 2 log n. For the class of monotone functions, we prove that the optimal query number O(2
r
+ r log n) can be already achieved in O(r) stages. On the other hand, (2
r
log n) is a lower bound on nonadaptive queries. 相似文献
15.
The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and
a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem
in the distributed setting, where the input is given in a distributed manner, i.e., every node “knows” which of its own emanating
edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the
graph in such a way that for every node, given (its own state and label and) the labels of its neighbors only, the node can
detect whether these edges are indeed its MST edges. In this paper, we present such a verification scheme with a maximum label
size of O(log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of Ω(log n log W) (as long as W > (log n)1+ε for some fixed ε > 0). Both our bounds improve previously known bounds for the problem.
For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both
the distributed and the sequential settings.
A preliminary version of this work was presented in ACM PODC 2006.
A. Korman was supported in part at the Technion by an Aly Kaufman fellowship.
S. Kutten was supported in part by a grant from the Israeli Ministry for Science and Technology. 相似文献
16.
Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from
node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring
graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result
on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space,
i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous
problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees
deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct
identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is
achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while
exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires
logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm
to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph. 相似文献
17.
Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics.
We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}n → {0, 1} which depend on all n variables, and distinct primes p, q:
o If f has degree o(log n) modulo p, then it must have degree Ω(n1−o(1)) modulo q. Thus a Boolean function has degree o(log n) in at most one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. 相似文献
18.
19.
When executing processes on parallel computer systems a major bottle-neck
is interprocessor communication. One way to address this problem is to minimize the
communication between processes that are mapped to different processors. This
translates to the k-partitioning problem of the corresponding process graph,
where k is the number of processors. The classical spectral lower bound of
(|V|/2k)\sum
k
i=1λ
i
for the k-section width of a graph is well
known. We show new relations between the structure and the eigenvalues of a graph
and present a new method to get tighter lower bounds on the k-section width.
This method makes use of the level structure defined by the k-section. We
define a global expansion property and prove that for graphs with the same
k-section width the spectral lower bound increases with this global expansion.
We also present examples of graphs for which our new bounds are tight up to a
constant factor. 相似文献
20.
Given an undirected graph and 0 £ e £ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm
that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant
probability of success, a linear size e{\epsilon}-near clique if there exists an e3{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n
−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of
size Ω(n/(log log n)
α
) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting. 相似文献
|