August 9-11, 2010
Room 121, 1/F., Ho Sin Hang Engineering Building
The Chinese University of Hong Kong
In a sequence of recent papers, Sudan and coauthors have investigated the relation between testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Linear-invariance is arguably the most common such symmetry for natural properties of Boolean functions on the hypercube. Hence, it is an important goal to find necessary and sufficient conditions for testability of linear-invariant properties. This is explicitly posed as an open problem in a recent survey of Sudan. We obtain the following results:
1. We show that every linear-invariant property that can be characterized by forbidding induced solutions to a (possibly infinite) set of linear equations can be tested with one-sided error.
2. We show that every linear-invariant property that can be tested with one-sided error can be characterized by forbidding induced solutions to a (possibly infinite) set of systems of linear equations.
We conjecture that our result from item (1) can be extended to cover systems of linear equations. We further show that the validity of this conjecture would have the following implications:
1. It would imply that every linear-invariant property that is closed under restrictions to linear subspaces is testable with one-sided error. Such a result would unify several previous results on testing Boolean functions, such as the results on testing low-degree polynomials and results on testing Fourier dimensionality.
2. It would imply that a linear-invariant property P is testable with one-sided error *if and only if* P is closed under restrictions to linear subspaces, thus resolving Sudan's problem.
Alon and Krivelevich showed that if a graph is ε-far from bipartite, then a subgraph induced by a random subset of about 1/ε vertices is likely to contain an odd length cycle. We conjecture that this subgraph is likely to be far from bipartite. We prove the conjecture is true for regular graphs of any degree.
Assuming this conjecture, we give an algorithm that tests bipartiteness in time O(1/ε2-c), where c > 0 is some universal constant. Our algorithm is inherently adaptive, as it is known that non-adaptive algorithms for testing bipartiteness require at least 1/ε2 queries.
Our conjecture and algorithm build upon previous works on testing bipartiteness by Alon and Krivelevich, Goldreich and Ron, and Gonen and Ron.
Based on joint work with Li Fan.
The matroid parity problem is a generalization of two important problems in combinatorial optimization, the maximum matching problem and the matroid intersection problem. Although the matroid parity problem is NP-hard, the linear matroid parity problem can be solved in polynomial time. The linear matroid parity problem, on its own, has applications in many areas like the minimum pinning set problem in combinatorial rigidity, the maximum genus imbedding problem in topological graph theory, approximating minimum Steiner tree and approximating maximum planar subgraph.
In this talk I will present an algebraic algorithm for the linear matroid parity problem. This algorithm is faster then other known algorithms and is very simple to implement in practice. Then I will show when graph problems are solved through the linear matroid parity problem, some structures can be exploited to give even faster algorithms.
This is a joint work with Lap Chi Lau and Kai Man Leung.
In CRYPTO'88, Damgaard proposed a candidate of a cryptographic pseudorandom generator based on the Legendre sequence. His generator is defined as the Legendre sequence starting from a given random seed, i.e., L(x) = ((x | p), (x+1 | p), (x+2 | p), ...) for a prime p. The pseudorandomness of this generator remains open even under any reasonable computational assumption. In this talk, we show a hardcore property of the Legendre generator for any quantum one-way function. More precisely, we prove that
is a hardcore function for f'(x, r) = (f(x), r), where p is an arbitrary n-bit prime, f is an arbitrary quantum one-way function and l = O(log n). Our main technique is a robust quantum state decoding, which significantly extends the Kawachi-Yamakami decoding method. This is a joint work with Keita Xagawa (NTT).
A long-standing lacuna in the field of computational learning theory is the learnability of succinctly representable monotone Boolean functions, i.e., functions that preserve the given order of the input. We show that Boolean functions computed by polynomial-size monotone circuits are hard to learn assuming the existence of one-way functions. Having shown the hardness of learning general polynomial-size monotone circuits, we show that the class of Boolean functions computed by polynomial-size depth-3 monotone circuits are hard to learn using statistical queries. As a counterpoint, we give a statistical query learning algorithm that can learn random polynomial-size depth-2 monotone circuits (i.e., monotone DNF formulas).
This talk will survey several recent results in the field of Property Testing. A property tester is a highly-efficient algorithm for distinguishing whether a massive input has a property, or is "far" from having the property. In the case of Boolean functions, for instance, a property tester's goal is make few queries to a Boolean function f on n variables (where n is large), and distinguish whether f belongs to a class C or is far from every member of C. This can be viewed as a relaxation of a typical machine learning problem, since a learning algorithm must also return an approximation to f if it is in C. We give property testing algorithms for many different classes C, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of n, better than the best possible learning algorithm. The theoretical results combine techniques from both learning and testing.
We ask whether Identity Based Encryption (IBE), a popular public key system where arbitrary strings can be used as public keys, can be implemented based on the popular assumptions of Decisional Diffie Hellman (DDH) and the existence of trapdoor permutations (TDP). In [1,2] we answer both questions in the negative. The question about TDPs is answered in a two-year old paper [1]. The question about DDH is conceptually substantially more difficult and was completed very recently [2]. As it is common, such black-box separations are being performed in a constructive way; i.e. in a setting where given oracle access, one primitive (e.g. DDH) exists whereas the other (e.g. IBE) cannot be implemented. We remark that the setting (model) for the DDH separation is interesting in its own right. In particular, we prove the DDH separation in the Generic Groups Model, introduced by Shoup [3]. This model has been criticized as too strong for positive results. We show the first negative result in this model, which is also of more general interest.
[1] Dan Boneh, Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters, On the impossibility of basing Identity Based Encryption on trapdoor permutations, FOCS'08
[2] Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, Brent Waters, The Limits of DDH (unpublished, 2010)
[3] Victor Shoup, Lower Bounds for Discrete Logarithms and Related Problems, EUROCRYPT'97
Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers.
We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat-free Nash equilibrium that is more permissive but still eliminates the undesirable ``empty threats'' of non-sequential solution concepts.
To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria (Dodis-Halevi-Rabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a non-trivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.
Joint work with Noam Livne and Ronen Gradwohl.
We discuss a new proof of the 4-color theorem alog the lines of Appel & Haken (1976) and of Robertson, Sanders, Seymour and Thomas (1994). Insights and refreshments will be provided.
A fundamental problem in data management is to draw a sample of a large data set, for approximate query answering, selectivity estimation, and query planning. With large, streaming data sets, this problem becomes particularly difficult when the data is shared across multiple distributed sites. The challenge is to ensure that a sample is drawn uniformly across the union of the data while minimizing the communication needed to run the protocol and track parameters of the evolving data. At the same time, it is also necessary to make the protocol lightweight, by keeping the space and time costs low for each participant. In this paper, we present communication-efficient protocols for sampling (both with and without replacement) from k distributed streams. These apply to the case when we want a sample from the full streams, and to the sliding window cases of only the W most recent items, or arrivals within the last w time units. We show that our protocols are optimal, not just in terms of the communication used, but also that they use minimal or near minimal (up to logarithmic factors) time to process each new item, and space to operate.
In this talk, we will discuss a real sequence alignment problem in bioinformatics which requires to align millions of short patterns (of length 35 to 75) to a long DNA sequence (say, with length of 3 billion characters) with small errors. Basically, the problem is the well-known approximation matching problem. However, theoretically sound algorithms may not be practical enough and well-known indexing techniques such as suffix tree or suffix array require too much memory. To solve the problem, we introduce a modified Burrows-Wheeler transform (BWT) data structure (referred as the bi-directional BWT) to index the long sequence in order to speed up the searching while using less memory than suffix tree/array. We will talk about the details of bi-directional BWT and the comparison of the performance of our solution with other existing solutions using real datasets.
Recent technological advances in experimental biology and the ‘omics’ revolution have yielded large amounts of biological network data with new mechanistic insights. However, the complexity of living systems has presented major challenges to the underpinnings between these huge datasets and the many real world phenomena. In this presentation, perturbation-response approaches are employed to study modular biological networks on a cellular level. We explore the use of simple linear rules to explain complex living processes such as the innate immune signaling and bacterial spore germination mechanisms. The goal is to decipher a systems-level governing principle to analyzing and modeling complex biological systems.