Catálogo de publicaciones - libros

We provide a framework for online conflict-free coloring (CF-coloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any -degenerate hypergraph. Our algorithm uses ( log) colors with high probability and this bound is asymptotically optimal for any constant . Moreover, our algorithm uses ( log log) random bits with high probability. As a corollary, we obtain asymptotically optimal randomized algorithms for online CF-coloring some hypergraphs that arise in geometry. Our algorithm uses exponentially fewer random bits compared to previous results.

We introduce deterministic online CF-coloring algorithms for points on the line with respect to intervals and for points on the plane with respect to halfplanes (or unit discs) that use (log) colors and recolor () points in total.

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the componentwise combination of their vectors. The parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. Sublinear-communication private protocols have been primarily been studied only in the two-party case. We give efficient multiparty protocols for sampling a row of the data matrix and for computing arbitrary functions of a row, where the row index is additively shared among two or more parties. We also give protocols for approximating the componentwise sum, minimum, or maximum of the columns in which the communication and the number of public-key operations are at most polynomial in the size of the small approximation and polylogarithmic in the number of rows.

We consider several private database query problems. The starting point of this work is the problem: the server holds a database of integers, and the user an integer ; the user wishes to find out how many database records are smaller than , without revealing ; nothing else about the database should be disclosed. We show a non-interactive communication-efficient solution to this problem. We then use it to solve more complex private database queries: range queries, range queries in plane and higher-dimensional generalizations of element rank. We also show an improved solution to the problem [1], and a solution to [9] using weaker assumptions than those of [9]. All our solutions assume semi-honest adversarial behaviour.

We present algebraic conditions on constraint languages that ensure the hardness of the constraint satisfaction problem CSP () for complexity classes L, NL, P, NP and ModL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP() is not first-order definable then it is L-hard. Our proofs rely on tame congruence theory and on a fine-grain analysis of the complexity of reductions used in the algebraic study of CSPs. The results pave the way for a refinement of the dichotomy conjecture stating that each CSP() lies in P or is NP-complete and they match the recent classification of [1] for Boolean CSP. We also infer a partial classification theorem for the complexity of CSP() when the associated algebra of is the idempotent reduct of a preprimal algebra.

The -consistency algorithm for constraint-satisfaction problems proceeds, roughly, by finding all partial solutions on at most variables and iteratively deleting those that cannot be extended to a partial solution by one more variable. It is known that if the core of the structure encoding the scopes of the constraints has treewidth at most , then the -consistency algorithm is always correct. We prove the exact converse to this: if the core of the structure encoding the scopes of the constraints does not have treewidth at most , then the -consistency algorithm is not always correct. This characterizes the exact power of the -consistency algorithm in structural terms.

We study – within the framework of propositional proof complexity – the problem of certifying unsatisfiability of CNF formulas under the promise that any satisfiable formula has many satisfying assignments, where “many” stands for an explicitly specified function Λ in the number of variables . To this end, we develop propositional proof systems under different measures of promises (that is, different Λ) as extensions of resolution. This is done by augmenting resolution with axioms that, roughly, can eliminate sets of truth assignments defined by Boolean circuits. We then investigate the complexity of such systems, obtaining an exponential separation in the average-case between resolution under different size promises:

(i) Resolution has polynomial-size refutations for all unsatisfiable 3CNF formulas when the promise is .2, for any constant 0 < < 1.

(ii) There are no sub-exponential size resolution refutations for random 3CNF formulas, when the promise is 2 (and the number of clauses is ()), for any constant 0 < < 1.

Motivated by the challenging task of designing “secure” vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most elements from a large universe of size on write-once memories in a manner that does not reveal the insertion order of the elements. Whereas previously known constructions were either inefficient (required () memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements.

In addition, we consider one of the classical distributed computing problems: Conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

Adaptive security, while more realistic as an adversarial model, is typically much harder to achieve compared to static security in cryptographic protocol design. Universal composition (UC) provides a very attractive framework for the modular design of cryptographic protocols that captures both static and adaptive security formulations. In the UC framework, one can design protocols in hybrid worlds that allow access to idealized functionalities and then apply the universal composition theorem to obtain more concrete protocol instances. The zero-knowledge (ZK) ideal functionality is one of the most useful sub-protocols in modular cryptographic design. Given an adaptively secure protocol in the ideal ZK-hybrid-world do we always need an adaptively secure realization of the ZK functionality in order to preserve adaptive security under composition? In this work, perhaps surprisingly, we find that this is not so and in fact there are useful protocol instances that we can “trade static security for adaptive security.”

We investigate the above setting, by introducing a weakened ZK ideal functionality, called the ideal leaking-zero-knowledge functionality (LZK) that leaks some information about the witness to the adversary in a certain prescribed way. We show that while LZK is interchangeable to ZK against static adversaries, ZK is more stringent when adaptive adversaries are considered. We then proceed to characterize a class of protocols in the hybrid-ZK-world that can be “transported” to the LZK-hybrid-world without forfeiting their security against adaptive adversaries. Our results demonstrate that in such settings a static protocol realization of ZK is sufficient for ensuring adaptive security for the parent hybrid protocol something that enables simplified and substantially more efficient UC realizations of such protocols.

We provide a new characterization of certain zero-knowledge protocols as (NIC). To obtain this result we consider the notion of V-bit protocols, which are very common, and found many applications in zero-knowledge. Our characterization result states that a protocol has a V-bit zero-knowledge protocol if and only if it has a NIC. The NIC inherits its hiding property from the zero-knowledge property of the protocol, and vice versa.

Our characterization result yields a framework that strengthens and simplifies many zero-knowledge protocols in various settings. For example, applying this framework to the result of Micciancio et al. [18] (who showed that some problems, including and , have a concurrent zero-knowledge proof) we easily get that arbitrary, monotone boolean formulae over a large class of problems (which contains, e.g., the complement of any random self-reducible problem) have a concurrent zero-knowledge proof.