February 21, Graduate Center: Vladimir Shpilrain (City College), Solving Yao's millionaires' problem without one-way functions
Abstract: The ``two millionaires problem" introduced by Yao is: Alice has a private number a and Bob has a private number b, and the goal of the two parties is to solve the inequality a < b? without revealing the actual values of a or b, or more stringently, without revealing any information about a or b other than a < b or a > b. We offer efficient and practical physical as well as mathematical solutions of Yao's millionaires' problem without using any one-way functions.
February 28, Graduate Center: Mohammad Mahdian (Google), Online bipartite matching with random arrivals
Abstract: In the online bipartite matching problem, we have n boys and n girls, with girls arriving one by one. When a girl arrives, we learn the set of boys she likes, and must match her to one such boy who is still unmatched. This decision cannot be changed later, and must be made without the knowledge of what comes later. In a classical result, Karp, Vazirani, and Vazirani showed that a simple ranking algorithm achieves a competitive ratio of 1-1/e for this problem, i.e., it guarantees that no matter in what order the girls arrive, the algorithm produces a matching whose size is at least 1-1/e times the size of the optimal matching. Their result also implies that in the random arrivals model defined by Goel and Mehta, where the girls arrive in a random order, a simple greedy algorithm achieves a competitive ratio of 1-1/e. In this talk, we discuss the ranking algorithm in the random arrivals model, and show that it has a competitive ratio of at least 0.696, beating the 1-1/e ~= 0.632 barrier in the adversarial model. Our analysis has two main steps. First, we exploit properties of the ranking algorithm to derive a family of factor-revealing linear programs (LPs). Second, to obtain a good lower bound on the optimal values of all these LPs and hence on the competitive ratio of the algorithm, we derive a family of modified LPs such that the optimal value of any single one of these LPs is a lower bound on the competitive ratio of the algorithm. This enables us to leverage the power of computer LP solvers to solve for large instances of the new LPs to establish bounds that would otherwise be difficult to attain by human analysis.
This is based on joint work with Qiqi Yan.
April 25, Graduate Center: Giovanni Di Crescenzo (Applied Communication Sciences), Practical and Privacy-Preserving Policy Compliance for Outsource Data
Abstract: We consider a scenario for data outsourcing that supports performing database queries in the following three-party model: a client interested in making database queries, a data owner providing its database for client access, and a server (e.g., a cloud server) holding the (encrypted) outsourced data and helping both other parties. In this scenario, a natural problem is that of designing efficient and privacy-preserving protocols for checking compliance of a client’s queries to the data owner’s query compliance policy.We propose a cryptographic model for the study of such protocols, defined so that they can compose with an underlying database retrieval protocol (with no query compliance policy) in the same participant model. Our main result is a set of new protocols that satisfy a combination of natural correctness, privacy, and efficiency requirements. Technical contributions of independent interest include the use of equality-preserving encryption to produce highly practical symmetric-cryptography protocols (i.e., two orders of magnitude faster than “Yao-like” protocols), and the use of a query rewriting technique that maintains privacy of the compliance result.
Published at a Financial Cryptography 2014 workshop. Co-authored with J.Feigenbaum (Yale Univ.), D.Gupta (Yale Univ.), E.Panagos (Applied Communication Sciences), J.Perry (Rutgers Univ.) and R.Wright (Rutgers Univ.).
May 2, Graduate Center: Yuri Bahturin (Memorial University of Newfoundland), Growth of subalgebras and subideals in free Lie algebras
Abstract: The aim of the talk is to show how the technique of generating functions can be used for the study of subgroups of free groups and subalgebras of free Lie algebras. Most of the results are from joint work with Alexander Olshanskii.
May 9, Graduate Center: Jamshid Derakhshan (Oxford University), p-adic model theory uniformly in p, and applications to algebra and number theory
Abstract: In 1949, Julia Robinson proved that the field of rational numbers is undecidable. Later, in 1965, motivated by a conjecture of Artin on zeroes of p-adic forms, Ax and Kochen proved that the field of p-adic numbers is decidable. This enabled development of model theory for p-adic and related fields. These theories have turned out to have a surprising feature, namely, that most of the properties that hold do not depend on the prime p, and are in turn controlled by other universal theories. Later, Ax developed a model theory of finite fields for almost all p, and this theory beautifully relates to the theory of p-adics for almost all p. The uniform logical behavior was then showed by Pas-Denef-Loeser to govern many properties of p-adic integrals uniformly in p, which enabled a theory of motivic integration, and it is is believed that this is a feature of many of the naturally occurring concepts and structures in number theory.
Recently, in continuation of this line of developments, new results have been obtained on the following topics:
1. Counting conjugacy classes and representations (and other counting problems) in algebraic groups over local fields (this is joint work with Mark Berman, Uri Onn, and Pirita Paajanen) where one can translate asymptotic questions in group theory formulated in terms of a generating Poincare series to questions on p-adic and motivic integrals approachable by model theory,
2. A model theory has been developed for the adeles of a number field (this is joint work with Angus Macintyre). The ring of adeles of the rational numbers is a locally compact ring made of all the p-adic fields for all p and the real field and enables using results on the local fields to derive results for the global rational field. It is intimately related to questions on various kinds of zeta functions in arithmetic and geometry.
Going from the local (p-adic and real) fields back to the rationals has long been a fundamental local-global transition both for the logic and the algebra. The above results give new tools and results on this. I will give a survey of some of the results and challenging open problems.
To subscribe to the seminar mailing list, click here
Fall 2013 talks
Spring 2013 talks
Fall 2012 talks
Spring 2012 talks
Fall 2011 talks
Spring 2011 talks
Fall 2010 talks
Spring 2010 talks
Fall 2009 talks
Spring 2009 talks
Fall 2008 talks
Spring 2008 talks
Fall 2007 talks
Spring 2007 talks
Fall 2006 talks
Spring 2006 talks
Fall 2005 talks