In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2–factor 𝒬 via (quasi) spanning trees of faces in G/𝒬 and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette’s Conjecture is false, then hamiltonicity in 3–connected planar cubic bipartite graphs is an NP-complete problem.

A signed graph is a graph together with an assignment of signs to the edges. A closed walk in a signed graph is said to be positive (negative) if it has an even (odd) number of negative edges, counting repetition. Recognizing the signs of closed walks as one of the key structural properties of a signed graph, we define a homomorphism of a signed graph $(G,σ)$ to a signed graph $(H, π)$ to be a mapping of vertices and edges of $G$ to (respectively) vertices and edges of $H$ which preserves incidence, adjacency and the signs of closed walks. In this work we first give a characterization of the sets of closed walks in a graph $G$ that correspond to the set of negative walks in some signed graph on $G$. We also give an easy algorithm for the corresponding decision problem. After verifying the equivalence between this definition and earlier ones, we discuss the relation between homomorphisms of signed graphs and those of 2-edge-colored graphs. Next we provide some basic no-homomorphism lemmas. These lemmas lead to a general method of defining chromatic number which is discussed at length. Finally, we list a few problems that are the driving force behind the study of homomorphisms of signed graphs.

We describe a generating set for the variety of simple graphs that admit a $k$-ary near-unanimity (NU) polymorphism. The result follows from an analysis of NU polymorphisms of strongly bipartite digraphs, i.e., whose vertices are either a source or a sink. We show that the retraction problem for a strongly bipartite digraph ${\mathbb H}$ has finite duality if and only if ${\mathbb H}$ admits an NU polymorphism. This result allows the use of tree duals to generate the variety of digraphs admitting a $k$-NU polymorphism.

We describe a generating set for the variety of reflexive graphs that admit a compatible $k$-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of $j$-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

Monotone monadic strict NP (MMSNP) is a class of computational problems that is closely related to the class of constraint satisfaction problems for constraint languages over finite domains. It is known that one of those classes has a complexity dichotomy if and only if the other class has. Whereas the dichotomy conjecture has been verified for several subclasses of constraint satisfaction problems, little is known about the the computational complexity for subclasses of MMSNP. In this paper we completely classify the complexity of MMSNP for the case where the obstructions are monochromatic and where loops in the input are forbidden. That is, we determine the computational complexity of natural partition problems of the following type. For fixed sets of finite structures ${\cal S}_1, \dots, {\cal S}_k$, decide whether a given loopless structure can be vertex-partitioned into k parts such that for each $i \leq k$ none of the structures in ${\cal S}_i$ is homomorphic to the ith part.

For a fixed graph H, let $\textsc{Ret}(H)$ denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of $\textsc{Ret}(H)$ when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of $\textsc{Ret}(H)$ for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of deidentifying records is to remove identifying fields such as social security number, name, etc. However, recent research has shown that a large fraction of the U.S. population can be identified using nonkey attributes (called quasi-identifiers) such as date of birth, gender, and zip code. The k -anonymity model protects privacy via requiring that nonkey attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k −1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a prespecified number of data records. This technique is more general since we have a much larger choice for cluster centers than k -anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k . We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ϵ fraction of points to remain unclustered, that is, deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.

Let H be a graph and $k \geq 3$. A near-unanimity function of arity k is a mapping g from the k-tuples over $V(H)$ to $V(H)$ such that $g(x_1, x_2, \dots, x_k)$ is adjacent to $g(x'_1, x'_2, \dots, x'_k)$ whenever $x_i x'_i \in E(H)$ for each $i = 1, 2, \dots, k$, and $g(x_1, x_2, \dots, x_k) = a$ whenever at least $k-1$ of the $x_i$'s equal a. Feder and Vardi proved that, if a graph H admits a near-unanimity function, then the homomorphism extension (or retraction) problem for H is polynomial time solvable. We focus on near-unanimity functions on reflexive graphs. The best understood are reflexive chordal graphs H: they always admit a near-unanimity function. We bound the arity of these functions in several ways related to the size of the largest clique and the leafage of H, and we show that these bounds are tight. In particular, it will follow that the arity is bounded by $n -\sqrt{n}+1$, where $n = |V(H)|$. We investigate substructures forbidden for reflexive graphs that admit a near-unanimity function. It will follow, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity. However, we exhibit nonchordal graphs which do admit near-unanimity functions. Finally, we characterize graphs which admit a conservative near-unanimity function. This characterization has been predicted by the results of Feder, Hell, and Huang. Specifically, those results imply that, if P $\neq$ NP, the graphs with conservative near-unanimity functions are precisely the so-called bi-arc graphs. We give a proof of this statement without assuming P $\neq$ NP.

Brooks proved that every connected graph other than a clique or odd cycle can be colored with $\Delta$ colors. Erdős, Rubin, and Taylor (and, independently, Vizing) generalized the theorem of Brooks to list colorings, describing all uncolorable connected graphs in which no vertex has a list smaller than its degree. Other authors have extended this to list T-colorings and their generalizations. We further extend it to model pair-list colorings. In addition to including all of the previous situations, pair-list colorings also generalize list homomorphisms (also known as list H-colorings). In the general context of pair-list colorings, we prove a Brooks-type theorem which extends many (but not all) of the existing results. Our result applies to both graphs and digraphs, with or without loops. We discuss several applications of the result, including a polynomial test for the existence of balanced list homomorphisms and retractions.

We study the problem of finding approximate Nash equilibria of two player games. We show that for any 0<ε<1, there is no 1 1 + ε - approximate equilibrium with strategies of support O(log n ε2).

Query optimization that involves expensive predicates has received considerable attention in the database community. Typically, the output to a database query is a set of tuples that satisfy certain conditions, and, with expensive predicates, these conditions may be computationally costly to verify. In the simplest case, when the query looks for the set of tuples that simultaneously satisfy k expensive predicates, the problem reduces to ordering the evaluation of the predicates so as to minimize the time to output the set of tuples comprising the answer to the query. We study different cases of the problem: the sequential case, in which a single processor is available to evaluate the predicates, and the distributed case, in which there are k processors available, each dedicated to a different attribute (column) of the database, and there is no communication cost between the processors.

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effort to randomize. We show that the flip Markov chain on regular graphs is rapidly mixing, thus justifying this widely used peer-to-peer networking practice. Our mixing argument uses the Markov chain comparison technique. In particular, we extend this technique to embedding arguments where the compared Markov chains are defined on different state spaces. We give several conditions which generalize our results beyond regular graphs

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as social security number, name etc. However, recent research has shown that a large fraction of the US population can be identified using non-key attributes (called quasi-identifiers) such as date of birth, gender, and zip code [15]. Sweeney [16] proposed the k-anonymity model for privacy where non-key attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k−1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a pre-specified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-Anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant-factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, i.e., deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.

Feder and Vardi have conjectured that all constraint satisfaction problems to a fixed structure (constraint language) are polynomial or NP-complete. This so-called dichotomy conjecture remains open, although it has been proved in a number of special cases. Most recently, Bulatov has verified the conjecture for conservative structures, i.e., structures which contain all possible unary relations. We explore three different implications of Bulatov's result. First, the above dichotomy can be extended to so-called inclusive structures, corresponding to conservative constraint satisfaction problems in which each variable comes with its own domain. (This has also been independently observed by Bulatov.) We prove a more general version, extending the dichotomy to so-called three-inclusive structures, i.e., structures which contain, with any unary relation R, all unary relations $R'$ for subsets $R' \subseteq R$ with at most three elements. For the constraint satisfaction problems in this generalization we must restrict the instances to so-called 1-full structures, in which each variable is involved in a unary constraint. This leads to our second focus, which is on restrictions to more general kinds of "full" input structures. For any set W of positive integers, we consider a restriction to W-full input structures, i.e., structures in which, for each $w \in W$, any w variables are involved in a w-ary constraint. We identify a class of structures (the so-called W-set-full structures) for which the restriction to W-full input structures does not change the complexity of the constraint satisfaction problem, and hence the family of these restricted problems also exhibits dichotomy. The general family of three-inclusive constraint satisfaction problems restricted to W-full input structures contains examples which we cannot seem to prove either polynomial or NP-complete. Nevertheless, we are able to use our result on the dichotomy for three-inclusive constraint satisfaction problems, to deduce the fact that all three-inclusive constraint satisfaction problems restricted to W-full input structures are NP-complete or "quasi-polynomial" (of order $n^{O(\log n)}$). Our third focus deals with bounding the number of occurrences of a variable, which we call the degree. We conjecture that the complexity classification of three-inclusive constraint satisfaction problems extends to the case where all degrees are bounded by three. Using previous results, we are able to verify this conjecture in a number of special cases. Conservative, inclusive, and three-inclusive constraint satisfaction problems can be viewed as problems in which each variable is restricted to a "list" of allowed values. This point of view of lists is frequently encountered in the study of graph colorings, graph homomorphisms, and graph partitions. Our results presented here, in all three areas, were strongly motivated by these results on graphs.

The problem of finding a fixed point of a nonexpansive mapping on a hypercube is that it has a polynomial time algorithm. In fact, it is known that one can find a 2-satisfiability characterization of the set of all fixed points in polynomial time. This implies that the problem of finding a vertex that is a common fixed point of several given nonexpansive mappings on a hypercube is that it has a polynomial time algorithm. We consider the problem of finding a vertex that is a common fixed point of several given nonexpansive mappings on a more general Cartesian product of graphs. For a single nonexpansive mapping, a known polynomial time algorithm finds a fixed point and a 2-satisfiability-like characterization of all fixed points. We introduce graphs with a farthest point property (also called apiculate graphs in [H. J. Bandelt and V. Chepoi, The Algebra of Metric Betweenness: Subdirect Representations, Retracts, and Axiomatics, manuscript]), and show that finding a common fixed point of several nonexpansive mappings on Cartesian products of such graphs involves using a polynomial time algorithm. We generalize this result to any family of graphs having a majority function. By contrast, the smallest graph (in the sense of having the fewest vertices, and the fewest edges of those having the fewest vertices) without the farthest point property is K 2,3 , and finding a vertex that is a fixed point of two given nonexpansive mappings (retractions) on a Cartesian product of graphs isomorphic to K 2,3 is NP-complete. More generally, we exhibit an infinite family of graphs without the farthest point property giving NP-completeness. We show that for any family of graphs not having a majority function, the existence of a common fixed point of two nonexpansive mappings on Cartesian products of such graphs is NP-complete. This proves a dichotomy for the problem based on the existence of a majority function; a similar dichotomy is obtained for the special case of nonexpansive mappings that are retractions. Finally we characterize the families of chordal graphs corresponding to both dichotomies.

Matroid intersection has a known polynomial time algorithm using an oracle. We generalize this result to delta-matroids that do not have equality as a restriction and give a polynomial time algorithm for delta-matroid intersection on delta-matroids without equality using an oracle. We note that when equality is present, delta-matroid intersection is as general as delta-matroid parity. We also obtain algorithms using an oracle for delta-matroid parity on delta-matroids without inequality, and for delta-matroid intersection where one delta-matroid does not contain either equality or inequality, and the second delta-matroid is arbitrary. Both these results also generalize matroid intersection. The results imply a dichotomy for bipartite Boolean constraint satisfaction problems using an oracle when one of the two sides does not contain equality, leaving open cases of delta-matroid parity when both sides have equality; the results also imply a full dichotomy for k-partite Boolean constraint satisfaction problems for $k\geq 3$. We then discuss polynomial cases of Boolean constraint satisfaction problems with two occurrences per variable through delta-matroid parity that cannot be obtained using the oracle approach.

Anderson et al. [{\it Amer. Math. Monthly}, 96 (1989), pp. 481--493] studied a combinatorial game on an infinite path that is started with n disks at a vertex and ends with the disks spread between $k=\lfloor n/2 \rfloor$ vertices to the left and to the right of the initial vertex. They showed that the number of steps the game takes to converge to the final configuration is $ck^2+o(k^2)$ for some constant c. We generalize this game to the case of an infinite rooted tree, where each vertex has degree $d+1$ and where the earlier game corresponds to the case $d=1$. We determine the final configuration when the game is started with n disks at the root and show that in this final configuration all disks are at depth at most $k=\Theta(\log_d n)$ for $d\geq 2$. We also show that the number of steps that the game takes to converge to the final configuration in this case is at most $O(k(1+ \log_d k))$, so that the convergence is faster than what it was for the case $d=1$. We generalize the game to the case where the vertices at depth i in the tree have $d_i\geq 2$ children, where the $d_i$ are not necessarily the same, and show that the convergence time in this case is at most $O(k^{1.5} + k \log_{d_{\min}} d_{\max})$, where $d_{\min}$ and $d_{\max}$ are the smallest and largest $d_i$, respectively.

Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications. The goal is to efficiently maintain clusters of small diameter as new points are inserted. We analyze several natural greedy algorithms and demonstrate that they perform poorly. We propose new deterministic and randomized incremental clustering algorithms which have a provably good performance, and which we believe should also perform well in practice. We complement our positive results with lower bounds on the performance of incremental algorithms. Finally, we consider the dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters.

Preservations theorems, which establish connection between syntactic and semantic properties of formulas, are a major topic of investigation in model theory. In the context of finite-model theory, most, but not all, preservation theorems are known to fail. It is not known, however, whether the Los-Tarski-Lyndon theorem, which asserts that a first-order sentence is preserved under homomorphisms if it is equivalent to an existential positive sentence, holds with respect to finite structures. Resolving this is an important open question in finite-model theory. In this paper we study the relationship between closure under homomorphism and positive syntax for several nonfirst-order existential logics that are of interest in computer science. We prove that the Los-Tarski-Lyndon theorem holds for these logics. The logics we consider are variable-confined existential infinitary logic, Datalog, and various fragments of second-order logic.

We consider a new model for computing with uncertainty. It is desired to compute a function f(X 1 ,. . .,X n ), where X 1 , . . ., X n are unknown but guaranteed to lie in specified intervals I 1 , . . ., I n . It is possible to query the precise value of any X j at a cost c j . The goal is to pin down the value of f to within a precision $\delta$ at a minimum possible cost. We focus on the selection function f which returns the value of the kth smallest argument. We present optimal offline and online algorithms for this problem.

List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0,1,* defines a list partition problem. Different choices of the matrix M lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices M. Along the way, we obtain a variety of specific results, including generalizations of Lovász's communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvátal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems.

An acyclic homomorphism of a digraph D into a digraph F is a mapping $\phi\colon V(D) \to V(F)$ such that for every arc $uv\in E(D)$, either $\phi(u)=\phi(v)$ or $\phi(u)\phi(v)$ is an arc of F, and for every vertex $v\in V(F)$, the subgraph of D induced on $\phi^{-1}(v)$ is acyclic. For each fixed digraph F we consider the following decision problem: Does a given input digraph D admit an acyclic homomorphism to F? We prove that this problem is NP-complete unless F is acyclic, in which case it is polynomial time solvable. From this we conclude that it is NP-complete to decide if the circular chromatic number of a given digraph is at most q, for any rational number $q > 1$. We discuss the complexity of the problems restricted to planar graphs. We also refine the proof to deduce that certain F-coloring problems are NP-complete.

We consider the problem of finding long paths and cycles in Hamiltonian graphs. The focus of our work is on sparse graphs, e.g., cubic graphs, that satisfy some property known to hold for Hamiltonian graphs, e.g., k-cyclability. We first consider the problem of finding long cycles in 3-connected cubic graphs whose edges have weights $w_i\geq 0$. We find cycles of weight at least ${(\sum w_i^a)}^{\frac{1}{a}}$ for $a=\log_2 3$. Based on this result, we develop an algorithm for finding a cycle of length at least $m^{(\log_3 2)/2}\approx m^{0.315}$ in 3-cyclable graphs with vertices of degree at most 3 and with m edges. As a corollary of this result, for arbitrary graphs with vertices of degree at most 3 that have a cycle of length l (or, more generally, a 3-cyclable minor with degrees at most 3 and with l edges), we find a cycle of length at least $l^{(\log_3 2)/2}$. We consider the graph property of 1-toughness that is common to Hamiltonian graphs and 3-connected cubic graphs, and we try to determine if 1-toughness implies the existence of long cycles. We show that 2-connectivity and 1-toughness, for constant degree graphs, may give cycles that are only of logarithmic length. However, we exhibit a class of 3-connected 1-tough graphs with degrees up to 6, where we can find cycles of length at least ${m}^{\log_3 2}/2$.

We show that, for every choice of an oriented cycle H, the problem of whether an input digraph G has a homomorphism to H is either polynomially solvable or NP-complete. Along the way, we obtain simpler proofs for two known polynomial cases, namely, oriented paths and unbalanced oriented cycles, and exhibit two new simple polynomial cases of balanced oriented cycles. The more difficult cases of the classification are handled by means of a new problem, the bipartite boolean satisfiability problem. In general, the k-partite boolean satisfiability problems are shown to be either polynomially solvable or NP-complete, thus generalizing Schaefer's classification of boolean satisfiability problems.

We consider a new model for computing with uncertainty. It is desired to compute a function f(X_1,...,X_n) where X_1,...,X_n are unknown, but guaranteed to lie in specified intervals I_1,...,I_n. It is possible to query the precise value of any X_j at a cost c_j. The goal is to pin down the value of f to within a precision p at a minimum possible cost. We focus on the selection function f which returns the value of the kth smallest argument. We present optimal offline and online algorithms for this problem.

Article Finding long paths and cycles in sparse Hamiltonian graphs Share on Authors: Tomas Feder View Profile , Rajeev Motwani Department of Computer Science, Stanford University, CA Department of Computer Science, Stanford University, CAView Profile , Carlos Subi View Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 524–529https://doi.org/10.1145/335305.335368Online:01 May 2000Publication History 9citation694DownloadsMetricsTotal Citations9Total Downloads694Last 12 Months16Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We introduce a parametrized family of graph problems that includes several well-known graph partition problems as special czses.We develop tools which allow us to classify the complexity of many problems in this family, and in particular lead us to a complete classification for small values of the parameters.Along the way, we obtain a variety of specific results including the following: a generalization of a communication bound on the number of clique-versus-independentset separators; polynomial-time algorithms to recognize generalized split graphs; and, a quasi-polynomial algorithm for the Skew Cutset Problem that essentially resolves an open problem posed by Chv&tal.The last two problems have interesting connections to the Strong Perfect Graph Conjecture of Berge.We also observe that the dichotomy (NPcomplete versus polynomial-time solvable) conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasipolynomial) for our graph partition problems.

This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.

Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space.We propose a model-c~led incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications.The goal is to efficiently maintain clusters of small diameter as new points are inserted.We analyze several natural greedy algorithms and demonstrate that they perform poorly.We propose new deterministic and randomized incremental clustering algorithms which have a provably good performance.We complement our positive results with lower bounds on the performance of incremental algorithms.Finally, we consider tbe dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters.

In this work we study the direct-sum problem with respect to communication complexity: Consider a relation f defined over $\{0,1\}^{n} \times \{0,1\}^{n}$. Can the communication complexity of simultaneously computing f on $\ell $ instances $(x_{1}, y_{1}), \dotsc , (x_{\ell}, y_{\ell})$ be smaller than the communication complexity of separately computing f on the $\ell $ instances? Let the amortized communication complexity of f be the communication complexity of simultaneously computing f on $\ell $ instances divided by $\ell $. We study the properties of the amortized communication complexity. We show that the amortized communication complexity of a relation can be smaller than its communication complexity. More precisely, we present a partial function whose (deterministic) communication complexity is $\Theta (\log n)$ and amortized (deterministic) communication complexity is $O(1)$. Similarly, for randomized protocols we present a function whose randomized communication complexity is $\Theta (\log n)$ and amortized randomized communication complexity is $O(1)$. We also give a general lower bound on the amortized communication complexity of any functionf in terms of its communication complexity $C(f)$: for every function f the amortized communication complexity of f is $\Omega (\sqrt{C(f)} - \log n)$.

A constraint-satisfaction problem is given by a pair I (the instance) and T (the template) of finite relational structures over the same vocabulary.The problem is satisfied if there is a homomorphism from 1 to T. It is well-known that the constraintsatisfaction problem is NP-complete.In practice, however, one often encounters the situation where the template T is fixed and it is only the instance I that varies.We define CSP to be the class of constraint-satisfaction problems with respect to fixed templates.It is easy to see that CSP is contained in NP and that CSP contains both problems in P and NP-complete problems.We pose the question whether every problem in CSP is either in P or is NP-complete, and attempt to classify which problems in CSP are in P and which are NP-complete.

A given Boolean function has its input distributed among many parties. The aim is to determine which parties to talk to and what information to exchange in order to evaluate the function while minimizing the total communication. This paper shows that it is possible to evaluate the Boolean function deterministically with only a polynomial increase in communication and number of parties accessed with respect to the information lower bound given by the nondeterministic communication complexity of the function.

The authors study the direct sum problem with respect to communication complexity: Consider a function f: D to (0, 1), where D contained in (0, 1)/sup n/*(0, 1)/sup n/. The amortized communication complexity of f, i.e. the communication complexity of simultaneously computing f on l instances, divided by l is studied. The authors present, both in the deterministic and the randomized model, functions with communication complexity Theta (log n) and amortized communication complexity O(1). They also give a general lower bound on the amortized communication complexity of any function f in terms of its communication complexity C(f).>

The most natural, compositional, way of modeling real-time systems uses a dense domain for time.The satistiability of timing constraints that are capable of expressing punctuality in this model, however, is known to be undecidable.We introduce a temporal language that can constrain the time difference between events only with finite, yet arbitrary, precision and show the resulting logic to be EXPSPACE-complete.This result allows us to develop an algorithm for the verification of timing properties of real-time systems with a dense semantics.

Article Clique partitions, graph compression and speeding-up algorithms Share on Authors: Tomás Feder Bellcore, Morristown, NJ Bellcore, Morristown, NJView Profile , Rajeev Motwani Stanford Univ., Stanford, CA Stanford Univ., Stanford, CAView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 123–133https://doi.org/10.1145/103418.103424Online:03 January 1991Publication History 52citation1,288DownloadsMetricsTotal Citations52Total Downloads1,288Last 12 Months15Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A given Boolean function has its input distributed among many parties. The aim is to determine which parties to talk to and what information to exchange with each of them in order to evaluate the function while minimizing the total communication. It is shown that it is possible to obtain the Boolean answer deterministically with only a polynomial increase in communication with respect to the information lower bound given by the nondeterministic communication complexity of the function.>

In a network stability problem, the aim is to find stable configurations for a given network of Boolean gates. For general networks, the problem is known to be computationally hard. Mayr and Subramanian [22,23] introduced an interesting class of networks by imposing fanout restrictions at each gate, and showed that network stability on this class of networks is still sufficiently rich to express as special cases the well-known stable marriage and stable roommate problems.

Lower bounds on the depth of Boolean networks that can compute reliably in the presence of randomly occurring failures are proved. A bound is also given on the reliability that error-tolerant networks can achieve: this bound implies a limit strictly smaller than 1/2 on the failure probability per gate that can be tolerated. The results improve upon recently published bounds of N. Pippenger (ibid., vol.IT-34, p.194-7, 1988) on the depth of error-tolerant formulas and extend the bounds to the case of reliable computation by networks.>

In a clustering problem, the aim is to partition a given set of n points in d-dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any L4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size.