Catálogo de publicaciones - libros

This paper studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of labeling the nodes of any -node graph is such a way that given the labels of two nodes and , one can decide whether and are -vertex connected in , i.e., whether there exist vertex disjoint paths connecting and . The paper establishes an upper bound of log on the number of bits used in a label. The best previous upper bound for the label size of such labeling scheme is 2log.

This paper studies the gap between quantum one-way communication complexity () and its classical counterpart (), under the setting, i.e., it is enough that the success probability is strictly greater than 1/2. It is proved that for (total or partial) Boolean function , () = ⌈()/2 ⌉, i.e., the former is always exactly one half as large as the latter. The result has an application to obtaining an exact bound for the existence of (,,)-QRAC which is the -qubit random access coding that can recover any one of original bits with success probability ≥ . We can prove that (,, > 1/2)-QRAC exists if and only if  ≤ 2− 1. Previously, only the non-existence of (2,, > 1/2)-QRAC was known.

We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on  +  bits have communication complexity linear in , even in the presence of unlimited entanglement.

We solve some fundamental problems in the number-on-forehead (NOF) -party communication model. We show that there exists a function which has at most logarithmic communication complexity for randomized protocols with a one-sided error probability of 1/3 but which has linear communication complexity for deterministic protocols. The result is true for  =  players, where is the number of bits on each players’ forehead. This separates the analogues of RP and P in the NOF communication model. We also show that there exists a function which has constant randomized complexity for public coin protocols but at least logarithmic complexity for private coin protocols. No larger gap between private and public coin protocols is possible. Our lower bounds are existential and we do not know of any explicit function which allows such separations. However, for the 3-player case we exhibit an explicit function which has (loglog) randomized complexity for private coins but only constant complexity for public coins.

It follows from our existential result that any function that is complete for the class of functions with polylogarithmic nondeterministic -party communication complexity does not have polylogarithmic deterministic complexity. We show that the set intersection function, which is complete in the number-in-hand model, is not complete in the NOF model under cylindrical reductions.

The between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this paper, we present a worst-case ()-time algorithm for this problem, improving the previous best (log)-time algorithm [7]. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of (log) [4] to (), matching our algorithm’s running time. Furthermore, we obtain matching upper and lower bounds of when the two trees have sizes and where  < .

Exploring a graph through search is one of the most basic building blocks of various applications. In a setting with a huge state space, such as in testing and verification, optimizing the search may be crucial. We consider the problem of visiting all states in a graph where edges are generated by actions and the (reachable) states are not known in advance. Some of the actions may commute, i.e., they result in the same state for every order in which they are taken (this is the case when the actions are performed independently by different processes). We show how to use commutativity to achieve full coverage of the states while traversing considerably fewer edges.

We define and study two versions of the bipartite matching problem in the framework of two-stage stochastic optimization with recourse. In one version the uncertainty is in the second stage costs of the edges, in the other version the uncertainty is in the set of vertices that needs to be matched. We prove lower bounds, and analyze efficient strategies for both cases. These problems model real-life stochastic integral planning problems such as commodity trading, reservation systems and scheduling under uncertainty.

We study a fundamental result of Impagliazzo () known as the hard-core set lemma. Consider any function :{0,1} →{0,1} which is “mildly-hard”, in the sense that any circuit of size must disagree with on at least fraction of inputs. Then the hard-core set lemma says that must have a hard-core set of density on which it is “extremely hard”, in the sense that any circuit of size

s’= must disagree with on at least (1 − )/2 fraction of inputs from .

There are three issues of the lemma which we would like to address: the loss of circuit size, the need of non-uniformity, and its inapplicability to a low-level complexity class. We introduce two models of hard-core set constructions, a strongly black-box one and a weakly black-box one, and show that those issues are unavoidable in such models.

First, we show that in any strongly black-box construction, one can only prove the hardness of a hard-core set for smaller circuits of size at most . Next, we show that any weakly black-box construction must be inherently non-uniform — to have a hard-core set for a class of functions, we need to start from the assumption that is hard against a non-uniform complexity class with bits of advice. Finally, we show that weakly black-box constructions in general cannot be realized in a low-level complexity class such as AC[] — the assumption that is hard for AC[] is not sufficient to guarantee the existence of a hard-core set.

Say that :{0,1} →{0,1} -approximates : {0,1} →{0,1} if the functions disagree on at most an fraction of points. This paper contains two results about approximation by DNF and other small-depth circuits:

(1) For every constant 0 < < 1/2 there is a DNF of size that -approximates the Majority function on bits, and this is optimal up to the constant in the exponent.

(2) There is a monotone function with total influence (AKA average sensitivity) such that any DNF or CNF that .01-approximates requires size 2 and such that unbounded fan-in AND-OR-NOT circuit that .01-approximates requires size (/ log). This disproves a conjecture of Benjamini, Kalai, and Schramm (appearing in [BKS99,Kal00,KS05]).

We define new complexity classes in the Blum-Shub-Smale theory of computation over the reals, in the spirit of the polynomial hierarchy, with the help of infinitesimal and generic quantifiers. Basic topological properties of semialgebraic sets like boundedness, closedness, compactness, as well as the continuity of semialgebraic functions are shown to be complete in these new classes. All attempts to classify the complexity of these problems in terms of the previously studied complexity classes have failed. We also obtain completeness results in the Turing model for the corresponding discrete problems. In this setting, it turns out that infinitesimal and generic quantifiers can be eliminated, so that the relevant complexity classes can be described in terms of usual quantifiers only.