Catálogo de publicaciones - libros

Since the seminal work of Paturi and Simon [26,FOCS’84 & JCSS’86], the unbounded-error classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [14, ICALP’07] found that the unbounded-error communication complexity in the model can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to the and (SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities for partial/total Boolean function, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is also used to show that the gap between unbounded-error quantum and classical communication complexities is at most a factor of three.

We propose an algorithm using a spectral method, and analyze its average-case performance for MAX2SAT in the planted solution model. In [16], they proposed a distribution for MAX2SAT in the planted solution model, as well as a message-passing algorithm. They showed that it solves, , MAX2SAT on for rather dense formulas, i.e., the expected number of clauses is . In this paper, we propose an algorithm using a spectral method and a variant of message-passing algorithms, and show that it solves, , MAX2SAT on for sparser formulas, i.e., the expected number of clauses is (log).

Valiant introduced some 25 years ago an algebraic model of computation along with the complexity classes VP and VNP, which can be viewed as analogues of the classical classes P and NP. Prominent examples of difficult (that is, VNP-complete) problems in this model includes the permanent and hamiltonian polynomials. In this paper we investigate the expressive power of easy special cases of these polynomials. We show that the permanent and hamiltonian polynomials for matrices of bounded treewidth both are equivalent to arithmetic formulas. Also, arithmetic weakly skew circuits are shown to be equivalent to the sum of weights of perfect matchings of planar graphs.

The 12 problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient algorithm that makes at most 2 queries to a -complete set has an efficient simulation that makes at most 1 query to . We obtain solutions to this problem under hypotheses weaker than previously considered. We prove that:

Here, for a complexity class and integer  ≥ 1, we model to be the class of problems solvable by zero-error randomized algorithms that always run in polynomial time, make at most queries to , and succeed with probability only 1/2 + 1/poly(·). This same model of , also considered in [CC06], subsumes the class of problems solvable by randomized algorithms that always answer correctly in expected polynomial time and make at most queries to .

Hemaspaandra, Hemaspaandra, and Hempel [HHH98], for  > 2, and Buhrman and Fortnow [BF99], for  = 2, had obtained the same consequence as of ours in (1) using the stronger hypothesis . Fortnow, Pavan, and Sengupta [FPS] had obtained the same consequence as of ours in (2) using the stronger hypothesis .

Our results may also be viewed as steps towards obtaining solutions to the most general form of the 1-versus-2 queries problem: For any  ≥ 1, whether can be simulated in .

is one of the most challenging algorithmic problems in topological graph theory, with applications to graph drawing and VLSI layout. No polynomial time constant approximation algorithm is known for this NP-complete problem. We prove that a natural approach to planar drawing of toroidal graphs (used already by Pach and Tóth in [21]) gives a polynomial time constant approximation algorithm for the crossing number of toroidal graphs with bounded degree. In this proof we present a new “grid” theorem on toroidal graphs.

Given an -node plane graph , the of is concerned with drawing each node of using a horizontal line segment such that the line segments associated with any two adjacent nodes of are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of no wider than . Our result improves upon the previously known upper bound , providing a positive answer to a conjecture suggested in the literature about whether an upper bound on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound only by one unit.

This paper studies the problem of computing an upward topological book embedding of an upward planar digraph , i.e. a topological book embedding of where all edges are monotonically increasing in the upward direction. Besides having its own inherent interest in the theory of upward book embeddability, the question has applications to well studied research topics of computational geometry and of graph drawing. The main results of the paper are as follows.

We consider the problems of hypergraph and minor crossing minimization, and point out a relation between these two problems which has not been exploited before. We present some complexity results regarding the corresponding edge and node insertion problems. Based on these results, we give the first embedding-based heuristics to tackle both problems and present a short experimental study. Furthermore, we give the first exact ILP formulation for both problems.

A very simple and natural broadcasting algorithm is the so-called push algorithm which has several applications in the area of distributed computing. Initially, only one vertex of a graph  = (,) owns a piece of information which is spread iteratively to all other vertices: in each time step  = 1,2,... every vertex chooses some neighbor uniformly at random which then becomes informed and may itself inform other vertices in the succeeding time steps. The crucial question is how many time steps are required such that all vertices become informed (with high probability).

For various graph classes, involved methods have been developed in order to show an upper bound of , where is the number of vertices and denotes the diameter of . However, currently no asymptotically tight bound on the runtime of the push algorithm based on the mixing time exists. In this work we fill this gap by deriving an upper bound of , where denotes the mixing time of a certain random walk on . After that we give a simple but useful upper bound which is based on a certain average value of the edge expansion of . Unfortunately, both approaches do not give the right bound for Hypercubes. Therefore, we develop a general way to combine them and prove that the runtime of the push algorithm is (log) on every Hamming graph.

In this paper we propose a novel algorithm that, given a source robot and a target robot , reconfigures into . Both and are robots composed of atoms arranged in 2 ×2 ×2 meta-modules. The reconfiguration involves a total of () atom operations (expand, contract, attach, detach) and is performed in () parallel steps. This improves on previous reconfiguration algorithms [1,2,3], which require () parallel steps. Our algorithm is in place; that is, the reconfiguration takes place within the union of the bounding boxes of the source and target robots. We show that the algorithm can also be implemented in a synchronous, distributed fashion.