Home

Talks

Publications

Conferences

Theory Seminars and Meetings

STAR Seminar and Other Talks

The Theory Group and those interested in Theory topics meet once a week for the STAR (Seminar on Theory, Algorithms and cRyptography Research) seminar. In the Winter-2008 quarter, we are meeting once a week on Wednesday, 10:00am, in EBU3b 4109 (see webpage). Apart from the STAR seminar, there are talks given by visiting researchers. Here is the schedule for these talks.

Speaker	Time and Location	Topic and Abstract
Todor Ristov, CSE, UCSD	Wed., Feb. 27, 2008, 10am-11pm, CSE 4109	Topic: Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products - by Jonathan Katz, Amit Sahai and Brent Waters Abstract: References: http://eprint.iacr.org/2007/404
Daniele Micciancio, CSE, UCSD	Wed., Feb. 20, 2008, 10am-11pm, CSE 4109	Topic: SWIFFT: a modest proposal for FFT hashing Abstract: We propose SWIFFT, a collection of compression functions that are highly parallelizable and admit very efficient implementations on modern microprocessors. The main technique underlying our functions is a novel use of the Fast Fourier Transform (FFT) to achieve ``diffusion,'' together with a linear combination to achieve compression and ``confusion.'' We provide a detailed security analysis of concrete instantiations, and give a high-performance software implementation that exploits the inherent parallelism of the FFT algorithm. The throughput of our implementation is competitive with that of SHA-256, with additional parallelism yet to be exploited. Our functions are set apart from prior proposals (having comparable efficiency) by a supporting asymptotic security proof: it can be formally proved that finding a collision in a randomly-chosen function from the family (with noticeable probability) is at least as hard as finding short vectors in cyclic/ideal lattices in the worst case. [Joint work with Lyubashevsky, Peikert and Rosen (FSE 2008)] References:
Petros Mol, CSE, UCSD	Wed., Feb. 13, 2008, 10am-11pm, CSE 4109	Topic: Recovering NTRU Secret Key From Inversion Oracles Abstract: We consider the NTRU encryption scheme as lately suggested for use, and study the connection between inverting the NTRU primitive (i.e., the one-way function over the message and the blinding information which underlies the NTRU scheme) and recovering the NTRU secret key (universal breaking). We model the inverting algorithms as black-box oracles and do not take any advantage of the internal ways by which the inversion works (namely, it does not have to be done by following the standard decryption algorithm). This allows for secret key recovery directly from the output on several inversion queries even in the absence of decryption failures. Our oracles might be queried on both valid and invalid challenges e, however they are not required to reply (correctly) when their input is invalid. We show that key recovery can be reduced to inverting the NTRU function. The efficiency of the reduction highly depends on the specific values of the parameters. As a side-result, we connect the collisions of the NTRU function with decryption failures which helps us gain a deeper insight into the NTRU primitive. (Joint work with Moti Yung, to be presented at PKC 2008) References:
Vadim Lyubashevsky, CSE, UCSD	Wed., Feb. 6, 2008, 10am-11pm, CSE 4109	Topic: Lattice-Based Identification Schemes Secure Under Active Attacks Abstract: There is an inherent difficulty in building 3-move identification schemes based on combinatorial problems without much algebraic structure. A consequence of this is that most standard identification protocols today are based on the hardness of number theory problems. Not having schemes based on alternate assumptions is a cause for concern since improved number theoretic algorithms or the realization of quantum computing would make the known schemes insecure. In this work, we examine the possibility of creating identification protocols based on the hardness of lattice problems. We construct a 3-move identification scheme whose security is based on the worst-case hardness of the shortest vector problem in all lattices, and also present a more efficient version based on the hardness of the same problem in all \emph{cyclic} lattices. References:
Kristin Lauter, Microsoft Research	Wed. Jan. 30, 2008, 10am, CSE 4109	Topic: Cryptographic hash functions from expander graphs Abstract: We propose constructing provable collision resistant hash functions from expander graphs. As examples, we investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer's Ramanujan graphs, (the set of supersingular elliptic curves over GF(p^2) with l-isogenies, l a prime different from p), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. We estimate the cost per bit to compute these hash functions, and we implement our hash function for several members of the LPS graph family and give actual timings. (Joint work with D. Charles and E. Goren.) References:
Jean Monnerat, CSE, UCSD	Wed. Jan. 23, 2008, 10am, CSE 4109	Topic: Separation Results on the ``One-More'' Computational Problems Abstract: In 2001, Bellare, Namprempre, Pointcheval and Semanko introduced the notion of ``one-more'' computational problems. Since their introduction, these problems have found numerous applications in cryptography. For instance, Bellare et al. showed how they lead to a proof of security for Chaum's RSA-based blind signature scheme in the random oracle model. In this paper, we provide separation results for the computational hierarchy of a large class of algebraic ``one-more'' computational problems (e.g. the one-more discrete logarithm problem, the one-more RSA problem and the one-more static Computational Diffie-Hellman problem in a bilinear setting). We also give some cryptographic implications of these results and, in particular, we prove that it is very unlikely, that one will ever be able to prove the unforgeability of Chaum's RSA-based blind signature scheme under the sole RSA assumption. (Joint work with Emmanuel Bresson, Jean Monnerat, Damien Vergnaud. To appear in CT-RSA 2008.) References:
Scott Yilek, CSE, UCSD	Wed., Jan. 16, 2008, 10am-11pm, CSE 4109	Topic: Chosen-Ciphertext Secure Proxy Re-Encryption --by Canetti and Hohenberger Abstract: In a proxy re-encryption (PRE) scheme, a proxy is given special information that allows it to translate a ciphertext under one key into a ciphertext of the same message under a different key. The proxy cannot, however, learn anything about the messages encrypted under either key. PRE schemes have many practical applications, including distributed storage, email, and DRM. Previously proposed re-encryption schemes achieved only semantic security; in contrast, applications often require security against chosen ciphertext attacks. We propose a definition of security against chosen ciphertext attacks for PRE schemes, and present a scheme that satisfies the definition. Our construction is efficient and based only on the Decisional Bilinear Diffie-Hellman assumption in the standard model. We also formally capture CCA security for PRE schemes via both a game-based definition and simulation-based definitions that guarantee universally composable security. We note that, simultaneously with our work, Green and Ateniese proposed a CCA-secure PRE, discussed herein. References: http://doi.acm.org/10.1145/1315245.1315269
Kirill Levchenko, CSE, UCSD	Wed., Dec. 5, 2007, 11am-12pm, CSE 4109	Topic: The Synergy between Systems and Theory: How Theory Can Benefit From Systems and Networking. Abstract: References:
Chris Peikert, SRI International	Wed., Nov. 21, 2007, 11am-12pm, CSE 4109	Topic: Lossy Trapdoor Functions and Their Applications Abstract: We propose a new general primitive called lossy trapdoor functions (lossy TDFs), and realize it under a variety of different number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of standard lattice problems. Using lossy TDFs, we develop a new approach for constructing many important cryptographic primitives, including standard trapdoor functions, CCA-secure cryptosystems, and more. All of the constructions are simple, efficient, and black-box. Taken all together, these results resolve some long-standing open problems in cryptography. They give the first known (injective) trapdoor functions that are not directly related to integer factorization, and provide the first known CCA-secure cryptosystem based solely on worst-case lattice assumptions. Joint work with Brent Waters of SRI International. References:
Scott Yilek, CSE, UCSD	Wed., Nov. 14, 2007, 11am-12pm, CSE 4109	Topic: The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization Abstract: The round-complexity of black-box zero-knowledge has for years been a topic of much interest. Results in this area generally focus on either proving lower bounds in various settings (e.g., Canetti, Kilian, Petrank, and Rosen prove concurrent zero-knowledge (cZK) requires Omega(log n / loglog n) rounds of interaction), or giving upper bounds (e.g., Prabhakaran, Rosen, and Sahai give a cZK protocol with omega(log n) rounds). We show that though proving upper bounds seems to be quite different from demonstrating lower bounds, underlying both tasks there is in fact a single, simple combinatorial game between two players which we call the rewinder and the scheduler. We give two theorems relating the success of rewinders in the game to both upper and lower bounds for black-box zero-knowledge in various settings (single-session, concurrent composition, etc). Our game and theorems unify the previous results in the area while greatly simplifying the task of proving upper and lower bounds, and should be useful in showing future results. (Joint work with Daniele Micciancio, to be presented at TCC 2008) References:
Vadim Lyubashevsky, CSE, UCSD	Wed., Nov. 7, 2007, 11am-12pm, CSE 4109	Topic: Asymptotically Efficient Lattice-Based Digital Signatures Abstract: We give a direct construction of digital signatures based on the complexity of approximating the shortest vector in ideal (e.g., cyclic) lattices. The construction is provably secure based on the worst-case hardness of approximating the shortest vector in such lattices within a polynomial factor, and it is also asymptotically efficient: the time complexity of the signing and verification algorithms, as well as key and signature size is almost linear (up to poly-logarithmic factors) in the dimension $n$ of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve lattice problems in the worst case, even when restricted to cyclic lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-off. (Joint work with Daniele Micciancio, to be presented at TCC 2008) References:
Alexander Vardy, UCSD	Wed., Oct. 31, 2007, 11am-12pm, CSE 4109	Topic: Multivariate Interpolation Decoding: Reaching the Ultimate Limit of List Error-Correction Abstract: One of the central questions in coding theory is this: What is the largest possible fraction of errors that a code of rate R can correct? We consider the case of adversarial errors, with error- correction defined in the list-decoding sense. Due to a series of ground-breaking papers in the past decade, we now have a complete answer to this question: the ultimate error-correction radius of 1 - R can be reached and, moreover, this can be done constructively with polynomial-time decoding. These exciting results will be presented in the chronological order of their development. We'll start with a brief introduction to Reed-Solomon codes and their decoding based on bivariate polynomial interpolation. This method, developed by Sudan and Guruswami-Sudan in the late 1990s, achieves a list-decoding radius of 1 - \sqrt{R}, improving upon the classical (1-R)/2 bound. We'll then devise a new decoding algorithm for Reed-Solomon codes based upon M-variate polynomial interpolation. The first nontrivial case M = 3 will be discussed in detail. We will show that, in contrast to the bivariate case, the recovery of the transmitted message requires at least two trivariate polynomials that satisfy the interpolation constraints. This will force us to part ways with Reed-Solomon codes, and introduce a new family of nonlinear algebraic codes that are list-decodable beyond the Guruswami-Sudan bound of 1 - \sqrt{R}. The key idea is to combine multivariate interpolation decoding with a kind of "inverted" algebraic-geometric construction. That is, instead of evaluating certain functions at rational points of a curve, we evaluate the rational points themselves, viewed as pairs of polynomials over a subfield, at certain elements of the subfield. This construction leads to polynomial-time error-correction up to the radius of 1 - O(R log(1/R)). Finally, we will review the recent preprint of Guruswami and Rudra, which shows how this construction can be combined with a clever folding technique in order to list-decode up to the radius of 1 - R - \epsilon, for any positive \epsilon. References:
Wenbo Zhao, UCSD	Wed., Oct. 17, 2007, 11am-12pm, CSE 4109	Topic: Analysis of Greedy Approximation with Nonsubmodular Potential Function Abstract: In recent work of Du, Graham, Pardalos, Wan, Wu and Zhao, we introduced a new method which can analyze a large class of greedy approximations with non-submodular potential functions, including some long-standing heuristics for Steiner trees, connected dominating sets, and power assignment in wireless networks. There exist many greedy approximations for various combinatorial optimization problems, such as set covering, Steiner tree, subset-interconnection designs, etc. There are also many methods to analyze these in the literature. However, all of the previously known methods are suitable only for those greedy approximations with submodular potential functions. This talk is based on joint work with D.-Z. Du, R. L. Graham, P. M. Pardalos, P.-J. Wan and W. Wu to be presented at SODA 2008. References:
Tom Ristenpart, CSE, UCSD	Wednesday, October 10, 2007, 11am-12pm, CSE 4109	Topic: How to build a hash function from any collision-resistant function Abstract: Recent collision-finding attacks against hash functions such as MD5 and SHA-1 motivate the use of provably collision-resistant (CR) functions in their place. Finding a collision in a provably CR function implies the ability to solve some hard problem (e.g., factoring). Unfor- tunately, existing provably CR functions make poor replacements for hash functions as they fail to deliver behaviors demanded by practi- cal use. In particular, they are easily distinguished from a random ora- cle. We initiate an investigation into building hash functions from prov- ably CR functions. As a method for achieving this, we present the Mix- Compress-Mix (MCM) construction; it envelopes any provably CR func- tion H (with suitable regularity properties) between two injective ‚Äúmix- ing‚Äù stages. The MCM construction simultaneously enjoys (1) provable collision-resistance in the standard model, and (2) indifferentiability from a monolithic random oracle when the mixing stages themselves are indif- ferentiable from a random oracle that observes injectivity. We instantiate our new design approach by specifying a blockcipher-based construction that appropriately realizes the mixing stages. Joint work with Thomas Shrimpton References:
Petros Mol, UCSD	Wed, October 3, 2007, 11am-12pm, CSE 4109	Topic: Lattices and Cryptography Abstract: Historically, the study of lattices has been closely related to areas such as theory and geometry of numbers. The invention of LLL algorithm in 1982 and some intractability results for computational problems related to lattices motivated the use of lattices in applications such as factorization of integer polynomials, integer programming and Public-Key Cryptography. Especially in PKC, lattice theory has played a crucial role in the definition of new cryptosystems, in the study of cryptographic primitives and in cryptanalysis. In this talk, we present some of the most representative applications of lattices in Cryptography with emphasis on cryptanalytic attacks on RSA Cryptosystem. We present how Coppersmith's technique for finding small solutions to polynomial equations can be used to attack certain instances of RSA Cryptosystem. Such attacks include low public exponent , factoring and low private exponent attacks. We conclude by presenting a nice deterministic reduction of factoring the RSA modulus to finding the private key. References:
,	Tuesdays at 2pm, AP&M 7421	Topic: Combinatorics Summer Reading Seminar Abstract: The initial theme is to read and discuss papers from STOC 07. References:
Sanjoy Dasgupta, CSE, UCSD	Thursday June 7, 2007, 11am, CSE 4109	Topic: Random projection trees and low-dimensional manifolds Abstract: The curse of dimensionality has traditionally been the bane of nonparametric statistics (histograms, kernel density estimation, nearest neighbor search, and so on), as reflected in running times and convergence rates that are exponentially bad in the dimension. This problem is all the more pressing as data sets get increasingly high dimensional. Recently the field has been rejuvenated in several ways, of which perhaps the most promising is the realization that a lot of real-world data which appears high-dimensional in fact has low "intrinsic" dimension in the sense of lying close to a low-dimensional manifold. In the past few years, there has been a huge interest in learning such manifolds from data, and then using the learned structure to transform the data into a lower-dimensional space where standard statistical methods generically work better. I'll exhibit a way to benefit from intrinsic low dimensionality without having to go to the trouble of explicitly learning its fine structure. Specifically, I'll present a simple variant of the ubiquitous k-d tree (a spatial data structure widely used in machine learning and statistics) that is provably adaptive to low dimensional structure. We call this a "random projection tree" (RP tree). Along the way, I'll discuss different notions of intrinsic dimension -- motivated by manifolds, by local statistics, and by analysis on metric spaces -- and relate them. I'll then prove that RP trees require resources that depend only on these dimensions rather than the dimension of the space in which the data happens to be situated. This is work with Yoav Freund. References: http://charlotte.ucsd.edu/~dasgupta/papers/rptree-tr.pdf
Daniele Micciancio, UCSD	Thursday May 24, 2007, 11am, EBU3b 4109	Topic: Tight reductions among lattice approximation problems Abstract: The most important and widely studied approximation problems on point lattices are: - the shortest vector problem (SVP): given a lattice find the shortest nonzero vector in the lattice. - the closest vector problem (CVP): given also a target point, find the lattice point closest to the target. - the shortest independent vector problem (SIVP): given a lattice find n linearly independent lattice point that are as short as possible. The first two problems have many applications in theoretical computer science and combinatorial optimization. The last one plays a fundamental role in the construction of lattice based cryptographic function from worst-case complexity assumptions. How do these problems relate to each other? Are they equivalent under polynomial time reductions? Are some harder than others? In this talk I will survey the current state of knowledge about the relation among lattice approximation problems, present some new results, and describe the remaining open problems. Goldreich et al. have shown that SVP is not harder than CVP, in the sense that there is a reduction from SVP to CVP that preserves both the approximation factor, dimension and rank of the lattice. The main new result presented in this talk is a similar tight reduction from SIVP to CVP. The reduction yields faster algorithms to solves SIVP exactly, improving the running time of the best previously known solution from n!3^n to n!. References:*
Shai Halevi, IBM Watson	Thursday May 17, 2007, 11am, CSE 4109	Topic: Mitigating Dictionary Attacks on Password-Protected Local Storage Abstract: We address the issue of encrypting data in local storage using a key that is derived from the user's password. The typical solution in use today is to derive the key from the password using a cryptographic hash function. This solution provides relatively weak protection, since an attacker that gets hold of the encrypted data can mount an off-line dictionary attack on the user's password, thereby recovering the key and decrypting the stored data. We propose an approach for limiting off-line dictionary attacks in this setting without relying on secret storage or secure hardware. In our proposal, the process of deriving a key from the password requires the user to solve a puzzle that is presumed to be solvable only by humans (e.g, a CAPTCHA). We describe a simple protocol using this approach: many different puzzles are stored on the disk, the user's password is used to specify which of them need to be solved, and the encryption key is derived from the password and the solutions of the specified puzzles. Completely specifying and analyzing this simple protocol, however, raises a host of modeling and technical issues, such as new properties of human-solvable puzzles and some seemingly hard combinatorial problems. Here we analyze this protocol in some interesting special cases. (Joint work with Ran Canetti and Michael Steiner) References:
Charanjit Jutla, IBM Watson	Monday, May 14, 2007, 2:30pm, room CSE 4217	Topic: SHA and Average Case NP-Hardness Abstract: We show a problem with uniform distribution to be hard for flat-NP, where flat-NP is defined to be distributional NP problems (dist-NP) with distributions smooth w.r.t. uniform. We show that this problem models the inversion problem of cryptographic hash function SHA-1, but with uniform distribution on the output. On the other hand, we show that basing oneway-ness even on hardness of flat-NP seems unlikely. To this end, we define new complexity classes Avg-NP (not to be confused with dist-NP), and Avg-AM. Extending a result of Akavia et al., we show that for size-verifiable functions f, there is no oblivious reduction from flat-NP hard languages to average case inverting f, unless flat-NP is in Avg-coAM. A similar result holds for dist-NP. We mention that flat-NP includes the discrete log problem over finite fields. References:
Sebastian Cioaba, UCSD, Math	Thursday May 10, 2007, 11am-12am, Room EBU3b (CSE) 4109	Topic: Separating systems, perfect hash functions and hypergraph cut covers Abstract: A separating system is a family of disjoint subsets of a set with n elements that "separates" all the pairs of elements from [n]. A family of perfect hash functions provides a means for storing k-element subsets of a set with n elements. In this talk, we will discuss these objects and their connections to graph and hypergraph covering problems. This is joint work with Andre Kundgen (Cal State San Marcos). References:
Kamalika Chaudhuri, UC Berkeley	Tuesday May 8, 2007 at 1pm, CSE 4140	Topic: Clustering using Correlation and Independence Abstract: Clustering, a method of finding structure in unlabelled data by grouping the data points into few groups based on a similarity measure, has many applications in AI, Physics and Biology. A simple theoretical model that captures clustering is the problem of learning mixtures of distributions. In this setting, one is given sample points generated from a mixture of T distributions of a certain type, and the goal is to recover these distributions and classify the points correctly.^M In this talk, motivated by an application in biology, we focus on learning mixtures of product distributions. The crux of the problem is learning the centers of the distributions. Singular Value Decomposition (SVD) is extensively used to find the T-dimensional subspace that contains the T centers. While SVD is the basis of provably effective algorithms, it is known to be ineffective in situations where the noise has high variance.^M We present a simple method which simultaneously exploits the correlation between the signal features and independence between the noise features to effectively separate the centers of the distributions. Our method has performance comparable to SVD based algorithms for learning mixtures of product distributions, and successfully clusters mixtures of axis-aligned Gaussians in certain cases where SVD provably fails. References:
Gyula Katona, Renyi Institute (Budapest)	Thursday May 3, 2007, 11am-12am, Room EBU3b (CSE) 4109	Topic: Forbidden inclusion patterns in families of subsets Abstract: (PDF) References:
Andy Drucker, CSE, UCSD	Thursday April 26, 2007, 11am, in EBU3b 4109	Topic: The Complexity of Natural Counting Methods in Combinatorics Abstract: - There are n! distinct n x n 0/1 permutation matrices. - Half of all binary strings of a given length have an odd number of ones. What do the proofs of these familiar counting facts reveal about the structural complexity of the associated sets? In this presentation on work in progress, I will describe how circuit and automata classes can be given to model the power of natural counting methods based on combinatorial operations such as disjoint union and cartesian product. I will also describe how to prove exponential lower bounds for one such class, showing, for example, that constructively counting the permutation matrices requires an inherently richer vocabulary than does counting the odd-weight strings. References:
Vadim Lyubashevsky, CSE, UCSD	Thursday April 19, 2007, 11am, Room EBU3b 4109	Topic: Cryptographic Hardness for Learning Intersections of Halfspaces Abstract: We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time algorithm for PAC learning intersections of $n^{epsilon}$ halfspaces (for a constant $epsilon>0$) in $n$ dimensions would yield a polynomial-time solution to $tilde O(n^{1.5})$-unique shortest vector problem. We also prove that PAC learning intersections of $n^{epsilon}$ low-weight halfspaces would yield a polynomial-time quantum solution to $tilde O(n^{1.5})$-shortest vector problem and $tilde O(n^{1.5})$-shortest independent vector problem. By making stronger assumptions about the hardness of these lattice problems, we show that there is no polynomial-time algorithm for learning intersections of $log^c n$ halfspaces in $n$ dimensions, for $c>0$ sufficiently large. Our approach also yields the first representation-independent hardness results for learning polynomial-size depth-$2$ neural networks and polynomial-size depth-$3$ arithmetic circuits. (based on a FOCS 2006 paper by Adam Klivans and Alex Sherstov) References: http://eccc.hpi-web.de/eccc-reports/2006/TR06-057/index.html
Atri Rudra, University of Washington	Monday April 16, 2007, 11:00am, EBU 3B CSE 1202	Topic: Error-correction with Information-theoretically Optimal Data Rate Abstract: Suppose you want to communicate k packets over a noisy communication channel. This is a common scenario when transmitting data over any real world channel such as the Internet or the telephone line. In order to tolerate errors, you transmit a redundant collection of n=ck packets. When can you communicate reliably despite the adverse effects of the noisy channel? That is, when can the receiver recover the original message even in the presence of corrupted packets? Clearly, the receiver must receive at least k correct packets to have any hope of recovering the original message. In this talk, I will describe an efficient encoding (and decoding) scheme that achieves this information theoretical limit: for any eps>0, the receiver can recover the original message as long as (1+eps)k packets are not corrupted. The location of the correct packets and the errors can be chosen adversarially by the channel. This scheme achieves the optimal trade-off (called "capacity") between redundancy and error-resilience for a malicious noise model in which the channel can corrupt the transmitted symbols arbitrarily subject to a bound on the total number of errors. These results are obtained in an error-recovery model called list decoding. In this talk I will introduce and motivate list decoding and then give an overview of our encoding scheme. I will also briefly discuss my other work in game theory, sublinear algorithms, approximation algorithms and coding theory. In particular, I will talk about my results in profit maximizing auctions, lower bounds for data stream algorithms and rank aggregation. References:
Sergey Yekhanin, MIT	Thursday April 12, 4pm, 2007, AP&M Room #6402	Topic: New Locally Decodable Codes and Private Information Retrieval Schemes Abstract: A q-query Locally Decodable Code (LDC) is an error-correcting code that encodes an n-bit message x as a codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only q bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The goal of LDC related research is to minimize the length of such codes. A q-server private information retrieval (PIR) scheme is a cryptographic protocol that allows a user to retrieve the i-th bit of an n-bit string x replicated between q servers while each server individually learns no information about i. The goal of PIR related research is to minimize the communication complexity of such schemes. We present a novel algebraic approach to LDCs and PIRs and obtain vast improvements upon the earlier work. Specifically, given any Mersenne prime p=2^t - 1, we design three query LDCs of length Exp(n^{1/t}), for every n. Based on the largest known Mersenne prime, this translates to a length of less than Exp(n^{10^{-7}}), compared to Exp(n^{1/2}) in the previous constructions. We also design 3-server PIR schemes with communication complexity of O(n^{10^{-7}}) to access an n-bit database, compared to the previous best scheme with complexity O(n^{1/5.25}). It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of subexponential length and three server private information retrieval schemes with subpolynomial communication complexity. References: http://theory.lcs.mit.edu/~yekhanin/Papers/nice_PIR.pdf
Martin Grohe, Humboldt-Universitaat zu Berlin	Thursday April 12, 11am-12pm, 2007, Room EBU3b (CSE) 4109	Topic: An Isomorphism Between Exponential and Parameterized Complexity Theory Abstract: Exponential complexity theory is concerned with the exact complexity of hard algorithmic problems, and in particular with the question of whether such problems are solvable in subexponential time. For example, a central question in this area is whether 3-SAT is solvable in time 2^o(n), where n denotes the number of variables. Parameterized complexity theory is also concerned with exact algorithms for hard algorithmic problems; here the question is whether the exponential running time that may be required to solve a problem can be confined to be exponential in some parameter of the problem instances, such as the degree of a graph, that can be expected to be small for the "relevant" instances. We show that exponential and parameterized complexity theory are isomorphic in a precise sense: The so-called "miniaturization mapping", introduced by Fellows and others, is one-to-one and onto (in the relevant range of problems), and it preserves the partial order induced by the standard reductions on both sides. Moreover, we show that the mapping acts quite naturally on important problems and complexity classes. (This is joint work with Yijia Chen.) References: http://www2.informatik.hu-berlin.de/~grohe/pub/chegro07+.pdf
Julia Chuzhoy, IAS	Friday, April 6th 2007 at 11:00am, CSE1202	Topic: Cuts and Flows in Directed Graphs Abstract: Cuts and flows are among the most basic graph theoretic notions. Applications that require solving graph cut or flow problems arise in almost every area of computer science. The study of the connection between flows and cuts dates back to the late fifties when Ford and Fulkerson proved that in the single-commodity environment, minimum cut equals maximum flow in any graph. A natural generalization of this result would be establishing the relationship between flows and cuts in the presence of multiple commodities. This relationship is usually expressed via the notion of flow-cut gap: the maximum ratio, achievable for any graph, between the maximum multi-commodity flow and the corresponding cut value, called minimum multicut. Flow-cut gaps have been extensively studied for more than five decades now, and they are widely used in the design and the analysis of algorithms. One of the major breakthroughs in this area is a complete understanding of the flow-cut gap in undirected graphs, which was proved to be logarithmic. In spite of this success, the flow-cut gaps have remained poorly understood in directed graphs. In particular, it has remained an open question whether the flow-cut gap in directed graphs is also logarithmic. In this talk we will answer this question in the negative by showing that, in sharp contrast to the undirected case, the flow-cut gap in directed graphs is polynomial. References:
Konstantin Pervyshev, CSE, UCSD	3 PM Wed. March 21, 2007, CSE 4109	Topic: Proofs of Work & Memory-Bound Functions Abstract: In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions. In this talk, we will provide a construction of proofs-of-work based on a memory-bound function and prove an asymptotically tight amortized lower bound on the number of memory accesses required to compute an acceptable proof of effort. (based on a CRYPTO 2003 paper by C. Dwork, A. Goldberg and M. Naor) References: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/mem_abs.html
Milena Mihail, Georgia Tech	Wed March 21, 2007 at 11am, CSE (EBU3B) 1202	Topic: Network Performance and Spectral Metrics Abstract: What parameters of massive networks, such as the Internet, the Web, and peer-to-peer networks, are critical to protocol performance? Can we measure and control these parameters and hence improve network performance? Can we predict how performance will scale with the size of these networks? In this talk I will argue that a critical parameter is the expansion, or conductance of the graph underlying the network topology. This is also closely related to the spectral gap of a suitable normalization of the adjacency matrix of this graph. I will present both experimental studies of these parameters using real network data, and theoretical studies using models such as power-law graphs. I will further present efficient distributed algorithms that maintain network topologies with good expansion, conductance and spectral gap. References:
Olgica Milenkovic, University of Colorado, Boulder	Wed, March 14, 2007, 3 PM, 4109 EBU3b	Topic: Average case analysis of Gosper's algorithm for indefinite summation of hypergeometric terms. Abstract: When addressing questions arising in combinatorial theory, one frequently encounters the problem of evaluating sums of functions of binomial terms. Sometimes, these, and certain more general sums of hypergeometric terms, including binomial coefficients, factorials, power and rational functions, have surprisingly simple "closed-form" expressions. Interestingly, there exist completely automatic procedures for determining if such expressions can be found and of what form they are. The key component of all such procedures is Gosper's algorithm. In this talk, we present an asymptotic analysis of the average-case complexity of Gosper's algorithm, based on a novel class of probabilistic transforms for urn-model occupancies, Tauberian theorems and generalized random walk statistics. The results developed in the course of this analysis are of independent interest in other areas of theoretical computer science, probability and coding theory. This is a joint work with Kevin Compton from the University of Michigan, Ann Arbor. References: http://ece-www.colorado.edu/~milenkov/gosper2.ps
Vijay Vazirani,	Monday, March 12, 2007, 11:00 AM in CSE 1202	Topic: Markets and the Primal-Dual Schema Abstract: The Internet has seen the emergence of several novel, computationally intensive markets, including Google's AdWords market, eBay's auctions market, and Yahoo! and Amazon's online markets which depend heavily on recommender systems. This is just the beginning of a much larger revolution in which algorithmic considerations are bound to have an impact (indeed, Internet companies are gearing up to this fact through massive research investments). The study of markets, within general equilibrium theory, occupied a central place in mathematical economics for over a century. In this talk, I will describe recent results on efficiently computing equilibria for traditional as well as new market models. This body of work provides a nice starting point for building an algorithmic theory of markets which can address today's needs. Interestingly enough, in these early works, the classical algorithm design technique of primal-dual schema plays a central role. References:
David Kempe, USC	Wed. Mar. 6, 2007, 3-4pm, EBU3b 4109	Topic: On the Bias of Traceroute Sampling, or: Power-law Degree Distributions in Regular Graphs. Abstract: Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph structure is a surprisingly difficult task, as edges cannot be explicitly queried. Instead, empirical studies rely on traceroutes to build what are essentially single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a recent paper by Lakhina et al. found empirically that the resuting sample is intrinsically biased. For instance, the observed degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson. In this talk, we study the bias of traceroute sampling systematically, and, for a very general class of underlying degree distributions, calculate the likely observed distributions explicitly. To do this, we use a continuous-time realization of the process of exposing the BFS tree of a random graph with a given degree distribution, calculate the expected degree distribution of the tree, and show that it is sharply concentrated. As example applications of our machinery, we show how traceroute sampling finds power-law degree distributions in both d-regular and Poisson-distributed random graphs. Thus, our work puts the observations of Lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions. (Joint work with Dimitris Achlioptas, Aaron Clauset, and Cristopher Moore.) References: http://www-rcf.usc.edu/~dkempe/publications/bfs.pdf
Mohan Paturi, CSE, UCSD	Wed. Feb. 14 and 21, 2007, 3-4pm, EBU3b 4109	Topic: Expander Graphs Abstract: I will provide part I of a two part talk which culminates in zig-zag product construction of expander graphs. Today, we will cover preliminary ideas and prove a theorem that connect expansion with eigenvalues. References:
Russell Impagliazzo, CSE, UCSD	Wed. Feb. 7, 2007, 3-4pm, EBU3b 4109	Topic: A Chernoff style direct product theorem Abstract: Consider a challenge-response protocol, where a legitimate user should have probability at least $\alpha$ of responding correctly, whereas an attacker has probability at most $\beta < \alpha$ of responding correctly. One example is a CAPTCHA challenge, where a human should have a significantly higher chance of answering a single challenge (e.g., uncovering a distorted letter) than an attacker. Another example would be a zero-knowledge argument system without perfect completeness. A natural approach to boost the gap between legitimate users and attackers would be to issue many challenges, and accept if the response is correct for more than a threshold fraction, where the threshold is chosen between $\alpha$ and $\beta$. We give the first proof that parallel repetition with thresholds improves the security of such protocols. We do this with a very general result about an attackers ability to solve a large fraction of many independent instances of a hard problem, showing a Chernoff-like convergence of the fraction solved correctly to the probability of failure for a single instance. This is a joint work with Ragesh Jaiswal(UCSD) and Valentine Kabanets (SFU). References:
Andrew Drucker, CSE, UCSD	Wed. Jan 31, 2007, 3-4pm, EBU3b 4109	Topic: Property Testing Abstract: Property testing is a recently developed algorithmic paradigm inspired by the need for fast (even constant-time!) approximate solutions to problems with very large data sets. I will introduce the field, give representative examples of testing algorithms and their analysis, and describe lower bounds for the model. References:
Manindra Agrawal, IIT Kanpur	Mon. Jan. 22, 2007, 11-12, 1202 EBU3b	Topic: Determinant Versus Permanent Abstract: I will talk about the problem of expressing permanent of matrices as determinant of (possibly larger) matrices. This problem has close connections with complexity of arithmetic computations: complexities of computing permanent and determinant roughly correspond to arithmetic versions of the classes NP and DP respectively. I will survey known results about their relative complexity and describe two recently developed approaches that might lead to a proof of the conjecture that permanent can only be expressed as determinant of superpolynomial-sized matrices. References: www.cse.iitk.ac.in/users/manindra/survey/Determinant.pdf
Bakhadyr Khoussainov , University of Auckland	Wed. 6 Jan, 2007, 3pm, Ebu3b 4109	Topic: Automatic Structures Abstract: We introduce the concept of automatic structure. Informally, these are structures that can be defined in terms of automata. By automata we mean any of the following machines: finite automata, tree automata, Buchi automata, and Rabin automata. Nerode and the speaker initiated the systematic study of automatic structures in 94. An important property of automatic structures is that these structures are closed under the first order interpretations and have effective semantics. In particular, the first order theory of any automatic structure is decidable. The theory of automatic structures has become an active research area in the last decade with new and exciting results. In this talk we survey recent results in the area and outline some of the interesting proofs. The talk will provide many examples. Some of the results of the talk are published in LICS 01-04 and STACS04 conference proceedings. Results are joint with Nerode, Rubin, Stephan, and Nies. References:
Evdokia Nikolova, MIT	Wed. 12 Dec, 3pm, Ebu3b 4109	Topic: Stochastic Shortest Paths via Quasi-Convex Maximization Abstract: We consider the problem of finding shortest paths in a graph with independent randomly distributed edge lengths. Our goal is to maximize the probability that the path length does not exceed a given threshold value (deadline). We give a surprising exact $n^{\Theta(\log n)}$ algorithm for the case of normally distributed edge lengths, which is based on quasi-convex maximization. We then prove average and smoothed polynomial bounds for this algorithm, which also translate to average and smoothed bounds for the parametric shortest path problem, and extend to a more general non-convex optimization setting. We also consider a number other edge length distributions, giving a range of exact and approximation schemes. joint work with Matthew Brand, Jonathan Kelner, Michael Mitzenmacher References:
Andrew McGregor,	Wed. 6 Dec, 3pm, Ebu3b 4109	Topic: Estimating the Entropy of a Data Stream Abstract: In this talk we will present a list of m values from a universe [n]. The list may only be read from left to right and you only have polylog (n,m) bits of memory. What can you compute about the underlying distribution of the values in the stream? In particular, can you approximate the entropy of this distribution? The above constraints characterize the data stream model, a model that abstracts some of the challenges faced when processing network traffic, database records, and data from external memory devices. Over the last ten years numerous theoretical results have been proven for this model including the Goedel prize winning work of Alon, Matias, and Szegedy on estimating frequency moments. In addition to presenting a long list of values, this talk will feature the results of joint work with Amit Chakrabarti (Dartmouth College) and Graham Cormode (AT&T Labs). This includes a near-optimal algorithm and lower-bound for estimating Shannon entropy and consideration of higher-order entropy and the entropy of a random walk. Bonus! Time permitting we'll also discuss some new results on approximating information theoretic distances such as Kullback-Leibler and Jensen- Shannon in the data stream model. This is joint work with Sudipto Guha (University of Pennyslvania) and Piotr Indyk (MIT). References: http://talk.ucsd.edu/andrewm/papers/07-soda1.pdf
Du Peng,	29 Nov, Wed. at 3 PM, in CSE 4109	Topic: Bipartite graph matching for points on a circle Abstract: Finding a minimum-cost matching in balanced bipartite graph whose nodes are on a circle is an interesting problem, which has been intensively studied by many researchers. One basic assumption is the defined cost function has to obey quadrangle inequality. We hereby present linear algorithms for two variations of this matching problem, each of which is dealing with a different cost function. In the first problem, the cost function is given by the shortest arc length between any two nodes of different color. Observation that there exists a greedy solution where every node matches to its neighbor after certain classification leads a linear algorithm to this simple case. For the second, the cost function is provided by Euclidean distance between two nodes. The cumulative property of the first cost function doesn’t hold any more which makes the greedy solution incorrect. We introduce another linear algorithm developed by Samuel R. Buss and Peter N. Yianilos for this case by the insight into the properties of the constrained optimal solution. Finally, both algorithms are generalized for other types of cost functions and for the nodes that lie on shapes other than circles. References:
Russell Impagliazzo, CSE, UCSD	Wed. 15 November 2006, 3pm, CSE 4109	Topic: A unified approach to tail inequalities Abstract: A tail inequality is a bound on the probability that a random variable is far from its expectation. Some tail inequalities that are widely used include Chebyshev bounds, Chernoff bounds, and the Martingale bound (Azuma's inequality). This talk will show that these bounds are related, by giving a notion of tail-bound preserving reduction between families of random variables. The emphasis will be on simplifying and unifying the proofs of versions of the inequalities, often at the expense of getting weaker bounds. References:
Danny Harnik, Technion, Israel	Friday, Nov 10, 2006, 3 PM, Ebu3b CSE 4109	Topic: On the Power of the Randomized Iterate Abstract: We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad, Impagliazzo, Levin and Luby (known as HILL), is that pseudorandom generators can be constructed from any one-way function. The second, due to Yao in 1982, states that the existence of weak one-way functions implies the existence of full fledged one-way functions. The above reductions, however, are not as security preserving as one may desire. The main reason for the security deterioration is the input blow up in both of these constructions. This work revisits a technique that we call the Randomized Iterate, introduced by Goldreich, Krawczyk and Luby. The technique was used to give a construction of pseudorandom generators from regular one-way functions. We simplify and strengthen this technique in order to obtain a similar reduction where the seed length of the resulting generators is as short as O(n log n) rather than \Omega(n^3) in the original proposed generator. We give a reduction with similar parameters for security amplification of regular one-way functions. We also show that the randomized iterate may even be useful in the context of an arbitrary one-way function. In particular, we use the randomized iterate to replace the basic building block of the HILL construction. This modification improves the efficiency by an O(n^3) factor and reduces the seed length by a factor of n (which also implies improvement in the security of the construction). Joint work with Iftach Haitner and Omer Reingold. References:http://www.cs.technion.ac.il/~harnik/Randomized_Iterate.pdf
Konstantin Pervyshev, CSE, UCSD	1st Nov, 2006, 3pm, CSE EBU3b 4109	Topic: Time Hierarchies for Heuristic Algorithms Abstract: Although a time hierarchy for deterministic algorithms was one of the first results in complexity theory, it is still unclear whether a time hierarchy exists for probabilistic algorithms. Recently, Fortnow and Santhanam (FOCS'04) proposed to consider average-case setting and proved the existence of a time hierarchy for heuristic algorithms in BPP, one of probabilistic classes. We develop an alternative approach and give a simpler proof of this result. Further, we show that time hierarchies exist for heuristic algorithms in some other classes, such as NP, AM and MA. References: http://eccc.hpi-web.de/eccc-reports/2006/TR06-131/index.html
Max Alekseyev, CSE, UCSD	Wed. 25 October 2006, 3pm, CSE 4109	Topic: Multi-Break Rearrangements and Fragile Regions in Human Genome Abstract: Multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. While multi-break rearrangements were studied in depth for k=2 breaks, the k-break rearrangement distance problem for an arbitrary k remains unsolved. We prove a duality theorem for multi-break rearrangement distance and give a polynomial algorithm for computing this distance. Using these results, we analyze the recent controversy about the Fragile Breakage Model of chromosome evolution. References:
Reid Andersen, MATH, UCSD	18 Oct, 2006, 3pm, CSE EBU3b 4109	Topic: Local Partitioning using PageRank Abstract: A local graph partitioning algorithm finds a cut near a specified starting vertex, and runs in time proportional to the small side of the cut, rather than the size of the input graph. In this talk, we present a local partitioning algorithm which finds a cut by computing a PageRank vector with a specified starting distribution. By combining small cuts found by this algorithm, we obtain a cut with conductance Phi and approximately optimal balance in time O(m log^4 m / Phi^2), where m is the number of edges in the graph. This is joint work with Fan Chung and Kevin Lang. References: http://www.math.ucsd.edu/~fan/wp/localpartition.pdf
Benny Sudakov, Princeton University	Wed. October 11, 2006, 3 PM, in 4109 CSE (EBU3b)	Topic: Additive Approximation for Edge-Deletion Problems Abstract: A graph property is monotone if it is closed under removal of vertices and edges. In this talk we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by $E_P(G)$. Our first result states that for any monotone graph property P, any $\epsilon >0$ and n-vertex input graph $G$ one can approximate $E_P(G)$ up to an additive error of $\epsilon n2$ Our second main result shows that such approximation is essentially best possible and for most properties, it is NP-hard to approximate $E_P(G)$ up to an additive error of $n^{2-\delta}$, for any fixed positive $\delta$. The proof requires several new combinatorial ideas and involves tools from Extremal Graph Theory together with spectral techniques. Interestingly, prior to this work it was not even known that computing $E_P(G)$ precisely for dense monotone properties is $NP$-hard. We thus answer (in a strong form) a question of Yannakakis raised in 1981. Joint work with N. Alon and A. Shapira. References: http://www.math.princeton.edu/~bsudakov/edit-distance.pdf
Nina Balcan, CMU	Thursday Oct 5, 2pm-3pm, EBU3b 4140	Topic: Mechanism Design, Machine Learning and Pricing Problems Abstract: In this work, we make an explicit connection between machine learning and mechanism design. In doing so, we obtain a unified approach for considering a variety of profit maximizing mechanism design problems, including many that have been previously considered in the literature. In particular, we use techniques from sample complexity in machine learning theory to reduce problems of incentive compatible mechanism design to standard algorithmic questions. We apply these results to a wide variety of revenue-maximizing pricing problems, including the problem of auctioning a digital good, the attribute auction problem, and the problem of item pricing in unlimited supply combinatorial auctions. It is worth noting that from a learning perspective, these settings present several unique challenges: the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large. This is joint work with Avrim Blum, Jason Hartline, and Yishay Mansour. References:
Saurabh Panjwani, CSE, UCSD	4th October, 2006, 3pm, EBU3b 4109	Topic: Soundness of Symbolic Encryption in the presence of Adaptive Corruptions Abstract: Proving the security of cryptographic protocols in the presence of attackers who can corrupt protocol participants during the execution of the protocol, in an "adaptive" manner, can be quite a challenging task. It is known that, in general, non-adaptive security of a protocol (security against non-adaptively corrupting adversaries) does not imply security against adaptive corruptions (that is, there exist protocols that are provably secure against non-adaptive corruptions but which can be completely broken by adaptive adversaries). The situation is particularly grim for protocols that use encryption as the fundamental primitive; even the strongest notions of encryption security are not known to imply adaptive security of protocols constructed using such encryption schemes. In fact, it is commonly believed that in order to be able to prove an encryption protocol adaptively secure, one is required to use non-standard encryption schemes(that is, encryption schemes that satisfy security criteria stronger than the standard ones like semantic security against chosen plaintext attacks). In this work, we show that under some reasonable restrictions on the protocol syntax, it is possible to argue about the adaptive security of encryption protocols, in a manner that does NOT require using non-standard definitions of encryption security. We present a general computational soundness theorem, which establishes that in any symmetric-key based encryption protocol, if the underlying encryption scheme is semantically secure, and if encryption "cycles" are absent, then security against adaptive corruptions is achievable via a reduction factor of O((2n)^{2l}), with n and l being the "size" and the "depth" of the key graph generated during any protocol execution. Since, in most protocols of practical interest, the depth of key graphs (measured as the longest sequence of ciphertexts of the form Encrypt_{k_1}(k_2), Encrypt_{k_2}(k_3), Encrypt_{k_3}(k_4), ... ever generated), is much smaller than their size, this gives us a powerful tool to prove adaptive security of such protocols, and with very reasonable assurances on the strength of the protocol against adaptive attacks. If time permits, we will also present an application of the soundness theorem. Specifically, we will show how the soundness theorem can be used to prove a variant of the Logical Key Hierarchy (LKH) protocol adaptively secure. LKH is a rather simple protocol that has attracted considerable interest in the cryptography community but whose adaptive security has hitherto remained unresolved. References: Draft
Sashka Davis, CSE, UCSD	Wednesday 27th Sept., 3pm, EBU3b 4109	Topic: Online Algorithms to Minimize Resource Reallocations and Network Communication Abstract: In this paper, we consider two new online optimization problems (each with several variants), present similar online algorithms for both, and show that one reduces to the other. Both problems involve a control trying to minimize the number of changes that need to be made in maintaining a state that satisfies each of many users' requirements. Our algorithms have the property that the control only needs to be informed of a change in users needs when the current state no longer satisfies the user. This is particularly important when the application is one of trying to minimize communication between the users and the control. References: www-cse.ucsd.edu/~sdavis/sensor.pdf
Russell Impagliazzo, CSE, UCSD	May 31, 2006, 12:30, EBU3b 4109	Topic: On the Complexity of Succinct Zero-Sum Games Abstract: References: L. Fortnow, R. Impagliazzo, V. Kabanets, C. Umans "On the Complexity of Succinct Zero-Sum Games". IEEE Conference on Computational Complexity 2005: 323-332 [http://dx.doi.org/10.1109/CCC.2005.18]
Yoav Freund, CSE, UCSD	Wed May 24, 2006, 12:30pm, EBU3b 4109	Topic: Drifting games in continuous time Abstract: The computational task that lies in the core of many machine learning problems is the minimization of a cost function called the training error. This problem is frequently solved by local search algorithms such as gradient descent. On the other hand, the cost function can usually be expressed as a sum over many terms, each corresponding to the loss of the model on a single training example. We show that the iteratively minimizing a cost function of this form by local search is closely related to the following game: Imagine you are a shepherd in charge of a large herd of sheep and your goal is to concentrate the sheep in a particular small area by nightfall. Your influence on the sheep movements is represented by vectors which define the direction in which you want each sheep to move. The lengths of the vectors correspond to the fraction of your "energy" that you spend on moving the particular sheep, and these lengths sum to one. The sheep then have to respond by moving in a way that has a slight correlation with the influence direction on average. We characterize the min/max solution to this game and show that by taking the appropriate small-step/continuous-time limit, this solution can be characterized by a stochastic differential equation. By solving this differential equation we re-derive some known boosting and on-line learning algorithms as well as design some new ones with desirable properties. This is Joint work with Manfred Opper. References:
Vijay Vazirani, Georgia Tech	May 17, at 11 AM, EBU 3B 1202	Topic: New Market Models and Algorithms Abstract: The notion of a ``market'' has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by companies such as Google, Yahoo!, Amazon, MSN and Ebay. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, though essentially non-algorithmic, theory within Mathematical Economics, needs to be revived and rejuvenated with new models, ideas, and an inherently algorithmic approach. In this talk, I will give a feel for the exciting work going on on this front and present new results on resource allocation markets. Interestingly enough, this work has also contributed handsomely to the theory of algorithms itself. In particular, the highly successful primal-dual schema from exact and approximation algorithms, which was so far used for combinatorially solving special classes of linear programs, has been extended to solving nonlinear convex programs. (The talk is self-contained and is meant for a general audience.) References: http://www-static.cc.gatech.edu/fac/Vijay.Vazirani/EG.pdf http://eccc.hpi-web.de/eccc-reports/2006/TR06-029/index.html
Antonio Nicolosi, NYU	Wednesday May 17th, 1pm, EBU3b 4019	Topic: Non-Interactive Zero-Knowledge from Homomorphic Encryption Abstract: We propose a method for compiling a class of Sigma-protocols (3-move public-coin protocols) into non-interactive zero-knowledge arguments. The method is based on homomorphic encryption^M and _does not_ use random oracles. It only requires that a private/public key pair is set up for the verifier. The method applies to all known discrete-log-based Sigma-protocols.^M ^M As applications, we obtain non-interactive threshold RSA without random oracles, and non-interactive zero-knowledge for NP more^M efficiently than by previous methods.^M ^M Joint work with Ivan Damgaard (Aarhus Univ.) and Nelly Fazio (NYU).^M References:
Russell Impagliazzo, CSE, UCSD	Wednesday 10 May , 12:30, EBU3b 4109	Topic: Can Every Randomized Algorithm Be Derandomized? Abstract: Among the most important modern algorithmic techniques is the use of random decisions. Starting in the 1970's, many of the most significant results were randomized algorithms solving basic compuatational problems that had (to that time) resisted efficient deterministic computation [Ber72, SS79, Rab80, Sch80, Zip79, AKLLR]. In contrast, many of the most exciting recent work has been on derandomizing these same algorithms, coming up with efficient deterministic versions, e.g., [AKS02,Rein05]. This raises the question, can such results be obtained for all randomized algorithms? Will the remaining classical randomized algorithms be derandomized by similar techniques? Clear but complicated answers to these questions have emerged from complexity-theoretic studies of randomized complexity classes (e.g., RP and BPP) and pseudo-random generators. These questions are inextricably linked to another basic problem in complexity: which functions require large circuits to compute? In this talk, we'll survey some results from the theory of derandomization. I'll stress connections to other questions, especially circuit complexity, explicit extractors, hardness amplification, and error-correcting codes. Much of the talk is based on joint work with Valentine Kabanets and Avi Wigderson, but it will also include results by many other researchers. References:
	wednesdays, 12:00 - 1:30, EBU3b 4109	Topic: Game Theory in Computer Science Abstract: STAR for Spring-2006 References:
Russell Impagliazzo, CSE, UCSD	8 Dec, 1:00 pm, EBU3B 4217	Topic: Computational Complexity Since 1980 Abstract: This talk will address trends in the computational complexity theory since 1980. The defining problems and issues for the field were established in the 1960's and 1970's. While many of these problems remain open, what is notable in the subsequent work is the intertwining of these fundamental questions, both through direct implications relating them and through a common toolbox of techniques that can be used to address a variety of seemingly disparate issues in complexity. We'll show how this unified set of techniques has been used to address and relate a variety of the basic questions in complexity, such as: 1. Hardness of approximation: To what extent can $NP$-hardness results be circumvented? More precisely, which optimization problems can be efficiently solved approximately? 2. Average-case complexity: Does $NP$-hardness mean that intractible instances of a problem actually arise? Or can we devise heuristics that solve typical instances? Which problems can be solved on "most" instances? 3. Foundations of cryptography: Can computational complexity be used as a foundation for cryptography? What kind of computational hardness is needed for such a cryptography? 4. The Power of randomness: What is the power of randomized algorithms? Should randomized algorithms replace deterministic ones to capture the intuitive notion of efficient computation? 5. Circuit complexity: Which problems require many basic operations to compute in non-uniform models such as Boolean or arithmetic circuits? How does the circuit complexity of problems relate to their complexity in uniform models? 6. Constructive combinatorics: Many mathematically interesting objects, such as from extremal graph theory, are proved to exist non-constructively, e.g., through the probabilistic method. When can these proofs be made constructive, exhibiting explicit and easily computable graphs or other structures with the desired properties? References:
Saurabh Panjwani, CSE, UCSD	29th Nov, 1:30 pm, EBU3B 4217	Topic: Append-Only Signatures Abstract: We present a new cryptographic primitive - Append-only Signatures (AOS) - with the property that any party given an AOS signature Sig[M] on message M can compute Sig[M \|\| M'] for any message M' (where M \|\| M' denotes the concatenation of M and M') while no malicious party can forge a signature on M unless and until a prefix of M has already been signed. Such signatures can be used for implementing credential systems in which one party delegates some information to another while also giving the latter the capability to ``append'' to the existing information, but to do nothing else. We present several concrete schemes for AOS in the standard model (no random oracles), and prove their security under general complexity-theoretic assumptions. In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through poly-time reductions. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive. References: This is the joint work of Eike Kiltz, Anton Mityagin, Saurabh Panjwani and Barath Raghavan and it appeared in ICALP 2005
Alan Nash, CSE, UCSD	16 Nov, 1:00pm, EBU3B 4109	Topic: Testing Logical Implication in the Finite and Applications to Information Integration Abstract: References:
Santosh Vempala, MIT	10 Oct, 11:00-12:00, EBU3B 1202	Topic: Spectral Algorithms and Representations Abstract: The spectrum of a matrix (or a graph) captures many interesting properties in surprising ways. Spectral methods (based on eigenvalues and eigenvectors) are already used for unsupervised learning, image segmentation, to improve precision and recall in databases and broadly for information retrieval. The common component of these methods is a projection to the space of a few singular vectors of the data. In this talk, we describe this idea and focus on the vital role it plays in efficient algorithms for (a) clustering object-feature (document-term) matrices and (b) the classical problem of learning a mixture of Gaussians. We also highlight a property that makes these methods particularly attractive for large data sets: any matrix (of any size) contains a "constant-size" submatrix from which an approximate spectral representation can be efficiently computed. References:
Yevgeniy Dodis, NYU	27th Sept, 4-5:30pm, EBU3B 4217	Topic: On Extractors, Error-Correction and Hiding All Partial Information Abstract: Randomness extractors allow one to obtain nearly perfect randomness from highly imperfect sources randomness, which are only known to contain "scattered" entropy. Not surprisingly, such extractors have found numerous applications in many areas of computer science including cryptography. Aside from extracting randomness, a less known usage of extractors comes from the fact that they hide all deterministic functions of their (high-entropy) input: in other words, extractors provide certain level of privacy for the imperfect source that they use. In the latter kind of applications, one typically needs extra properties of extractors, such as invertibility, collision-resistance or error-correction. In this abstract we survey some of such usages of extractors, concentrating on several recent results by the speaker. The primitives we will survey include several flavors of randomness extractors, entropically secure encryption and perfect one-way hash functions. The main technical tools will include several variants of the leftover hash lemma, error correcting codes, and the connection between randomness extraction and hiding all partial information. References: http://theory.lcs.mit.edu/~yevgen/ps/ent-survey.ps
Eike Kiltz , CSE, UCSD	2 June, 11-12:20, AP&M 5218	Topic: Threshold Circuit Lower Bounds on Cryptographic Functions Abstract: In this work, we are interested in non-trivial upper bounds on the spectral norm of binary matrices M from {-1,1}^NxN. It is known that the distributed Boolean function represented by M is hard to compute in various restricted models of computation if the spectral norm is bounded from above by N^(1-e), where e>0 denotes a fixed constant. For instance, the size of a two-layer threshold circuit (with polynomially bounded weights for the gates in the hidden layer, but unbounded weights for the output gate) grows exponentially fast with n=log N. We prove sufficient conditions on M that imply small spectral norms (and thus high computational complexity in restricted models). Our general results cover specific cases, where the matrix M represents a bit (the least significant bit or other fixed bits) of fundamental functions. Functions like the discrete multiplication and division, as well as cryptographic functions such as the Diffie-Hellman function and the decoding functions of the Pointcheval and the ElGamal cryptosystems can be addressed by our technique. In order to obtain our results, we make a detour on exponential sums and on spectral norms of matrices with complex entries. References:
Ragesh Jaiswal, CSE, UCSD	19 May, 11-12:20 pm, AP&M 5218	Topic: Analysis of Hierarchical Markov Chains Abstract: Markov chains provide useful algorithmic paradigm for approaching generation problems in general. Analysing the rate of convergence of appropriate markov chain becomes the core issue when working with these stochastic techniques. Various methods like coupling, canonical paths, decomposition have been suggested to analyse the convergence rate of various classes of markov chains. We are primarily interested in reversible, hierarchical markov chains which comes up naturally for problems like Independent Set, Graph Matchings etc. In this work we suggest a characterization which is useful in bounding the convergence rate of a markov chain with a biased stationary distribution, in terms of the convergence rate of the corresponding markov chain with unbiased (uniform) stationary distribution. References:
Josh Buresh-Oppenheim, CSE, UCSD	12 May, 11-12:20pm, AP&M 5218	Topic: Towards Models for Backtracking and Dynamic Programming Abstract: Since most algorithms that people use can intuitively be classified into large paradigms of algorithms such as greedy, dynamic programming, LP rounding, local search, etc., it is natural to ask what problems can be computed by these paradigms. This question can be seen as an alternative to asking what problems can be computed by all, say, poly-time algorithms in that the restriction on the algorithms is more conceptual rather than complexity-theoretic. Of course, to ask a question about an algorithmic paradigm, you first have to formally define the paradigm. We offer one very natural model, BT, which captures many algorithms generally considered to be dynamic programming or backtracking. This model is an extension of the Priority Algorithm model of Borodin, Nielsen and Rackoff, which captures greedy algorithms. We demonstrate many upper and lower bounds in this model for problems such as interval scheduling, knapsack and SAT. We then define a stronger model, DP, and show that it captures some aspects of dynamic programming that BT does not. References:
Misha Alekhnovich, IAS Princeton	6 May, 1-2pm, AP&M 4301	Topic: The Hardness of the Closest Vector Problem for Pre-processed Lattices Abstract: We show that, unless NP has quasipolynomial algorithms the Closest Vector Problem with Pre-processing, for $\ell_p$ norm for any $p \geq 1,$ is hard to approximate within a factor of $(\log n)^{1/p-\epsilon}.$ This improves the previous best factor $3^{1/p}$ due to Regev. Our results also imply that for any $\epsilon>0,$ under the same complexity assumption, the Nearest Codeword Problem with Pre-processing is hard to approximate within a factor of $(\log n)^{1-\epsilon}.$ References:
Dr. Alexei Ashikhmin , Bell Laboratories, Lucent Technologies	10 May, 1-2pm, Fung Auditorium of the Powell-Focht Bioengineering Hall at UCSD	Topic: Quantum Codes: Constructions and Parameters Abstract: It is well known that a number of computational problems can be solved on a quantum computer exponentially faster than on a classical computer. One of the main problems in building a quantum computer is its unavoidable coupling with an environment. This coupling results in decoherence of quantum states. The only way of mitigating the decohernece is quantum error-correction. In this talk, I will give a general introduction to quantum error correcting codes. In particular, I will start with a definition of a quantum code, its minimum distance, and its distance distribution. After that, I will survey the state of our knowledge about quantum codes, including best-known results concerning explicit constructions of asymptotically-good quantum codes, upper and lower bounds on the minimum distance of quantum codes, and the probability of undetected error. References:
Daniele Micianccio, CSE, UCSD	5 May, 11-12:20, AP&M 5218	Topic: Pseudo Free Groups Abstract: References:
Chris Calabro, CSE UCSD	28 Apr, 11-12:20, AP&M 5218	Topic: "The PCP theorem by gap amplification" (ECCC TR05-046) Abstract: Let C={c_1,...,c_n} be a set of constraints over a set of variables. The {em satisfiability-gap} of C is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the variables. We prove a new combinatorial amplification lemma that doubles the satisfiability-gap of a constraint-system, with only a linear blowup in the size of the system. Iterative application of this lemma yields a self-contained (combinatorial) proof for the PCP theorem. The amplification lemma relies on a new notion of "graph powering" that can be applied to systems of constraints. This powering amplifies the satisfiability-gap of a constraint system provided that the underlying graph structure is an expander. We also apply the amplification lemma to construct PCPs and locally-testable codes whose length is {em quasi-linear}, and whose correctness can be probabilistically verified by making a {em constant} number of queries. Namely, we prove SAT in PCP_{0.5,1}[log(n * polylog n) , O(1)]. This answers an open question of Ben-Sasson et al. (STOC '04). References: http://www.eccc.uni-trier.de/eccc-reports/2005/TR05-046/index.html
Yi-Kai Liu, CSE, UCSD	21 Apr, 11-12, AP&M 5218	Topic: Holographic algorithms" from FOCS 2004 Abstract: We introduce a new notion of efficient reduction among computational problems. Classical reductions involve gadgets that map local solutions of one problem to local solutions of another in one-to-one, or possibly many-to-one or one-to-many, fashion. Our proposed reductions allow for gadgets with many-to-many correspondences. Their objective is to preserve the sum of the local solutions. Such reductions provide a method of translating a combinatorial problem to a family of finite systems of polynomial equations with integer coefficients such that the number of solutions of the combinatorial problem can be counted in polynomial time if some system in the family has a solution over the complex numbers. We can derive polynomial time algorithms in this way for ten problems for which only exponential time algorithms were known before. General questions about complexity classes are also formulated. If the method is applied to a #P-complete problem then we obtain families of polynomial systems such that the solvability of any one member would imply P^(#P) = NC2. References: http://ieeexplore.ieee.org/search/freesrchabstract.jsp? arnumber=1366250&isnumber=29918& punumber=9430&k2dockey=1366250@ieeecnfs&query=%28%28 holographic+algorithms%29%3Cin%3Emetadata%29&pos=0
Vadim Lyubashevski, CSE, UCSD	14 Apr, 11-12, AP&M 5218	Topic: Solving the Parity Problem with Few Examples and Decoding Random Linear Codes in Sub-Exponential Time Abstract: A few years ago, Blum, Kalai and Wasserman demonstrated the first sub-exponential algorithm for learning the parity function in the presence of noise. They solved the length-n parity problem in time 2^O(n/logn) but it required the availability of 2^O(n/logn) labeled examples. As an open problem, they asked whether there exists a 2^o(n) algorithm for the length-n parity problem that uses only poly(n) labeled examples. In this talk, a positive answer will be provided. It'll be shown that there is an algorithm that solves the length-n parity problem in time 2^O(n/loglogn) using n^(1+epsilon) labeled examples. This result immediately gives us a sub-exponential algorithm for decoding n x n^(1+epsilon) random linear codes in the presence of random noise. The same technique can also be used to come up with a sub-exponential algorithm for dense instances of the random subset sum problem. References:
Shuchi Chawla, CMU	11 Apr, 11-12, AP&M 4301	Topic: Algorithms for Path-Planning Abstract: Consider a robot with a map of its environment, that needs to visit a number of sites to deliver packages, collect samples, etc. However, owing to a limited supply of battery power, or some unforeseen obstacle, the robot may not be able to visit all the sites. In such a situation, a natural question is to ask for a tour that visits as many sites as possible by some pre-determined deadline. This is the classic Orienteering problem. More generally, path-planning problems involve a set of locations to be visited, with constraints on the path taken to visit them, such as deadlines on visiting particular locations, or a minimum number of locations that must be visited. These problems arise in many fields including operations research, scheduling, and robotics, and are mostly NP-hard. In this talk, Ms. Chawla will present the first approximations to several path-planning problems including Orienteering. Ms. Chawla will then discuss an application of path-planning to robot navigation and describe the complications that arise due to uncertainty in the robot's environment. References:
Sashka Davis, CSE, UCSD	7 Apr, 11 - 12, AP&M 5218	Topic: "Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders" (O. Reingold, S. Vadhan, A. Wigderson, Annals of Mathematics, Vol. 155, No.1, pp. 157-187, 2002.) Abstract: References: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/ SALIL/EXPANDERS/ANNALS/paper.ps
Salil Vadhan, Harvard University	1 Apr, 2 - 3pm, AP&M 4301	Topic: An Unconditional Study of Computational Zero Knowledge Abstract: We prove a number of general theorems about ZK, the class of problems possessing computational zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. In particular, we show that: - Honest-verifier ZK equals general ZK, - Public-coin ZK equals private-coin ZK, - ZK is closed under union, and - ZK with imperfect completeness equals ZK with perfect completeness. Our approach is to combine the conditional techniques previously used in the study of ZK with the unconditional techniques that we and others developed in the study of SZK, the class of problems possessing statistical zero-knowledge proofs. To enable this combination, we prove that every problem in ZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed. References:
Jia Mao, CSE, UCSD	16 Mar, 1-2 pm, AP&M 4218	Topic: Undirected ST-Connectivity in Log-Space, by Omer Reingold. Abstract: In this recent breakthrough paper, Reingold showed that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is solvable by a deterministic log-space algorithm, thus implying that SL = L as well as several other significant consequences. References: http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps
Alan Nash, UCSD Math and CSE	9 Mar, 1-2pm	Topic: PTIME Queries Revisited: joint work with Jeff Remmel and Victor Vianu Abstract: The existence of a language expressing precisely the PTIME queries on arbitrary structures remains the central open problem in the theory of database query languages. As it turns out, two variants of this question have been formulated. Surprisingly, despite the importance of the problem, the relationship between these variants has not been systematically explored. A first contribution of the present paper is to revisit the basic definitions and clarify the connection between these two variants. We then investigate two relaxations to the original problem that appear as tempting alternatives in the absence of a language for the PTIME queries. The first consists in trying to express the PTIME queries using a richer language that can also express queries beyond PTIME, but for which there exists a query processor evaluating all PTIME queries in PTIME. The second approach, studied by many researchers, is to focus on PTIME properties on restricted sets of graphs. Our results are mostly negative, and point out limitations to both approaches. Finally, we turn to a natural class of languages that we call finitely generated, whose syntax is obtained by applying a fixed set of constructors to a given set of building blocks. We identify a broad class of such languages that cannot express all the PTIME queries. References:
William Matthews, UCSD	2 march, 1-2 pm, AP&M 4218	Topic: A Deterministic (2-2/(k+1))^n Algorithm for k-SAT Based on Local Search, by Dantsin, Goerdt, Hirsh, Kannan, Kleinberg, Papadimitriou, Raghavan, and Schoning. Abstract: Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Sch�ning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.).We describe a deterministic local search algorithm for k-SAT running in time (2-2/(k+ 1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms. References: http://portal.acm.org/citation.cfm?id=637765 http://portal.acm.org/citation.cfm?id=796524
Russell Impagliazzo, UCSD	23 Feb, 1:00 - 2:00, AP&M 4218	Topic: Error-correcting codes and hardness amplification (Contd) Abstract: References:
Russell Impagliazzo, UCSD	16 Feb, 1 -2 PM, 4218 AP&M	Topic: Error-correcting codes and hardness amplification Abstract: In hardness amplification, we are given a worst-case hard problem or a problem hard for some small fraction of instances. We wish to construct a reliably hard problem, hard for almost all instances. Hardness amplification is important for cryptography and pseudo-randomness, in that one needs reliably hard problems for both types of application. In hindsight, many of the techniques used for hardness amplification resemble those in error-correction. In fact, it is relatively straight-forward to translate hardness amplification results into error-correction results. The result illuminates techniques in both areas. This talk will sketch the parallels between hardness amplification and error-correction. It will also discuss a new type of weak error-correction that arises from this viewpoint, a boosting code. References: Note: references are from bad memory. Yao, Theory and application of trap-door one-way functions. Goldreich, Levin: A hard-core bit for any one-way function. Babai, Fortnow, Nisan , Wigderson: P=BPP unless EXP has publishable proofs Impagliazzo, Wigderson: P=BPP unless EXP has subexponential circuits. Sudan, Trevisan, Vadhan: Derandomization through locally list-decoding Trevisan's extractor paper. Trevisan's new paper.
James R. Lee, UC Berkeley	11 Feb, 11:00 - 12:00, AP&M 4301	Topic: Metric Geometry and Computer Science Abstract: References:
Alexander Vardy, ECE, UC San Diego	12:30 - 2:00, AP&M 4218	Topic: Old Problems and New Results in Coding Theory Abstract: Coding theory was born in 1948 with the work of Claude Shannon, who proved that for every information rate $R$ up to channel capacity, there exists a code of rate $R$ that guarantees a vanishing probability of decoding error. Shannon, however, did not tell us how to find such codes nor how to decode them. It was recognized early on that codes with good Hamming distance can correct many errors, while codes endowed with algebraic structure admit efficient algebraic decoding algorithms. This has led to over 50 years of research in algebraic and combinatorial coding theory. We will survey several key problems and new results in this area. In particular, we'll elaborate upon a new asymptotic improvement of the Gilbert-Varshamov bound and upon recent methods for decoding Reed-Solomon codes using bivariate polynomial interpolation. About 10 years ago, the field of coding theory was transformed by the discovery of codes defined on certain graphs, with no algebraic structure, that perform extremely close to the Shannon capacity under probabilistic message-passing decoding. We will briefly review this exciting development, and point out the challenges that lie ahead in the area of "probabilistic" coding theory. References: