Catálogo de publicaciones - libros

A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. [17] and Roland and Cerf [15] when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in log, where is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.

Pass observed that universal composable zero-knowledge (UCZK) protocols in the common reference string (CRS) model, where a common reference string is selected trustily by a trusted third party and is known to all players, lose deniability that is a natural property of any ZK protocol in the plain model [33]. An open problem (or, natural query) raised in the literature is: are there any other essential security properties, other than the well-known deniability property, that could be lost by universal composable zero-knowledge in the common reference string model, in comparison with UC security in the plain model? In this work, we answer this open question (or, natural query), by showing that UCZK protocols in the CRS model could lose concurrent general composability (CGC) and proof of knowledge (POK) properties that are very important and essential security implications of UCZK in the plain model. This is demonstrated by concrete attacks.

We clarify the potential limitation of the general feasibility for generalized universal composability (GUC) proposed in the recent work [8], and discuss a general principle for fully realizing universal composability. This in particular demonstrates the hardness of achieving generalized universal composability, and prevents potential misinterpretation in applications. We also propose some fixing approaches, which involve a source/session-authentic ID-based trapdoor commitment scheme via the hash-then-commit paradigm that could possibly be of independent interest.

In most of the used auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one is interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. Based on garbled circuits, i.e. encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements:

Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the bids in an auction based on the garbled circuit. Usually previous papers are focused on the problem of evaluating the bids of an auction. In this paper we address both problems. In addition to the generalization of the concept of garbled circuit we will present a -private protocol for the construction of a garbled circuit that reaches the lower bound of 2 + 1 parties and a more randomness efficient protocol for ( + 1) parties.

Finally we will present a strategy that allows new bidders to join a running auction or to change their bids dynamically. Our goal is that all bidders who do not change their bids are allowed to stay inactive in the process of bid changing.

This paper first explores the power of the dial locks (also called the combination locks), which are physical handy devices, in designing cryptographic protocols. Specifically, we design protocols for secure multiparty computations using the dial locks, and give some conditions for a Boolean function to be or not to be securely computable by a dial lock, i.e., to be or not to be “dial-computable.” In particular, we exhibit simple necessary and sufficient conditions for a symmetric function to be dial-computable.

We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if () is a time-constructible function and () grows faster than ( + 1), then there exists a language which can be accepted by a ()-time nondeterministic cellular automaton but not by any ()-time nondeterministic cellular automaton.

This paper investigates the satisfiability of Propositional Projection Temporal Logic (PPTL) with infinite models. A decision procedure for PPTL formulas is formalized. To this end, Normal Form (NF) and Normal Form Graph (NFG) for PPTL formulas are defined and an algorithm constructing NFG for PPTL formulas is presented. Further, examples are also given to illustrate how the decision algorithm works.

This paper presents a mixed 0 – 1 integer and linear programming (MILP) model for separation of data via a finite number of nonlinear and nonconvex discriminant functions. The MILP model concurrently optimizes the parameters of the user-provided individual discriminant functions and implements a decision boundary for an optimal separation of data under analysis.

The MILP model is extensively tested on six well-studied datasets in data mining research. The comparison of numerical results by the MILP-based classification of data with those produced by the multisurface method and the support vector machine in these experiments and the best from the literature illustrates the efficacy and the usefulness of the new MILP-based classification of data for supervised learning.

The Collatz problem, widely known as the 3 + 1 problem, asks whether or not a certain simple iterative process halts on all inputs. In this paper, we build on work of J. H. Conway to show that a natural generalization of the Collatz problem is complete.

Miller, Teng, Thurston, and Vavasis proved that every -nearest neighbor graph (-NNG) in Rd̂ has a balanced vertex separator of size (). Later, Spielman and Teng proved that the Fiedler value — the second smallest eigenvalue of the graph — of the Laplacian matrix of a -NNG in ℝ is at . In this paper, we extend these two results to nearest neighbor graphs in a metric space with doubling dimension and in nearly-Euclidean spaces. We prove that for every  > 0, each -NNG in a metric space with doubling dimension has a vertex separator of size , where and are respectively the maximum and minimum distances between any two points in , and is the point set that constitutes the metric space. We show how to use the singular value decomposition method to approximate a -NNG in a nearly-Euclidean space by an Euclidean -NNG. This approximation enables us to obtain an upper bound on the Fiedler value of the -NNG in a nearly-Euclidean space.