Seminars archive

With the trend of cloud computing, data and computing are moved away from desktop and are instead provided as a service from the cloud. Data-as-a-service enables access to a wealth of data across distributed and heterogeneous data sources in the cloud. It remains a challenge, however, to ensure the privacy, interoperability, and scalability for such services.\\ \\ We designed and developed DObjects, a general-purpose P2P-based query and data operations infrastructure that can be deployed in the cloud and provides access to heterogeneous data sources. The system builds on top of a distributed mediator-wrapper architecture where individual system nodes serve as mediators and/or wrappers and interact with each other in a P2P fashion what guarantees good scalability. As an analogy, the system nodes can be considered as droplets, small elements that provide similar functionality in the cloud. Just as thousands or millions of droplets form a single drop in nature, in cloud computing, groups of droplets that provide similar functionality can form a micro-cloud. Micro-clouds are an integral part of the whole cloud computing system and can provide specific services to users.\\ \\ The dissertation also discusses the novel dynamic query execution engine within the data query infrastructure that dynamically adapts to network and node (or droplet) conditions. The query processing is capable of fully benefiting from all the distributed resources to minimize the query response time and maximize system throughput. In addition to leveraging the traditional distributed query optimization techniques, the (sub)queries are deployed and executed on droplets in a dynamic and iterative manner in order to guarantee the best reaction to network and resource dynamics.\\ \\ Finally, the dissertation presents an extension to the basic DObjects model that enables access to private data that is distributed and needs anonymization. The extension enables droplets to form virtual groups in order to addresses two important privacy issues for the sensitive data: privacy of data subjects and confidentiality of data providers. The dissertation discusses decentralized protocols that enable data sharing for horizontally partitioned databases given these constraints. These protocols can be run by the groups of droplets. Concretely, given a query spanning multiple databases, the query results do not contain individually identifiable information. In addition, institutions do not reveal their databases to each other apart from the query results.

TBA

We know, thanks to the work of A. Weil, that counting points of varieties over finite fields yields purely topological information about them. For example, an algebraic curve is topologically a certain number g of donuts glued together. The same number g, on the other hand, determines how the number of points it has over a finite field grows as the size of this field increases. This interaction between complex geometry, the continuous, and finite field geometry, the discrete, has been a very fruitful two-way street that allows the transfer of results from one context to the other. In this talk I will first describe how we may count the number of points over finite fields for certain character varieties,parameterizing representations of the fundamental group of a Riemann surface into GL-n. The calculation involves an array of techniques from combinatorics to the representation theory of finite groups of Lie type. I will then discuss the geometric implications of this computation and the conjectures it has led to. This is joint work with T. Hausel and E. Letellier

We know how search engines crawl websites: they harvest links from pages and iterate through each to develop an "image" of the world wide web as a whole. During the last decade of search engine growth, websites have attempted to "help" or even to more directly influence the crawlers and the subsequent website ranking. For example, conventional wisdom holds that search engines "prefer" sites that are wide rather than deep, and that having a site index will result in more thorough crawling by the Big Three crawlers: Google, Yahoo, and MSN. But how do crawlers actually behave on websites? Does site design really affect this behavior? We created a series of 10 websites to monitor search engine behavior when crawling with very large websites (wide and deep), as well as their behavior on websites where resources "disappear." We analyzed the logs of each of these sites for over a full year to see if the conventional wisdom holds true. GIF animations of Apache log data are used to illustrate the crawling patterns. We found that each search engine exhibited different behavior and crawl persistence, and that site design does appear to affect this behavior. We plot the progress of the crawlers through the sites, and their behaviors regarding the various file types. A side benefit of search engine activity on a site is the "cached page" which is accessible if the original is unavailable. How long will such pages persist in the cache if the web source page disappears? We examine this issue and the role that the cache and a website's design play in website preservation.

It has long been recognized that practical contexts for constraint satisfaction problems (CSP) often involve large relational databases (RDB). Early attempts to marry constraint solving systems and relational database systems include deductive and constraint databases that reuse important ideas from logic programming. These techniques required knowledge outside the scope of traditional database users. The recent proposal by Cadoli and Mancini, CONSQL, shows that a simple extension to SQL provides a viable basis for modeling CSP. This opens the possibility for transparently integrating CSP with databases using SQL the most widely known and popular database language. Such an extension brings the power of constraint problem solving to SQL knowledgeable users. Towards that end, the current research describes a case study in the engineering details of designing and implementing such a prototype.

Inspired by the "rough classification" ideas from additive combinatorics, Soundararajan and I have recently introduced the notion of pretentiousness into analytic number theory. Besides giving a more accessible description of the ideas behind the proofs of several well- known difficult results of analytic number theory, it has allowed us to strengthen several results, like the Polya-Vinogradov inequality, the prime number theorem, etc. In this talk we will introduce these ideas and gave some flavour of these developments.

Scientific communication can be modeled on the basis of citation networks in which the flow of ideas is expressed by citations that point from one scientific publication to another. A number of graph-theoretical methods can be brought to bear on such citation networks to determine the status of particular publications and infer general properties of the scientific communication process. However, as scientific activity increasingly moves online, it becomes possible to study scientific relationships and processes from online usage patterns. In this colloquium I will present two applications of the analysis of large-scale usage data logs now commonly collected by scholarly web portals, namely modeling and mapping of the structure of scientific activity, and determining the components of scientific impact.

A starting point of the theory of random matrices is Wigner's semi-circle law obtained in the 1950s, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random hermitian matrix with iid (upper diagonal) entries follows the semi-circle law. The non-hermitian case is the famous Circular Law Conjecture, which asserts that (after a proper normalization) the limiting distribution of the spectra of a random matrix with iid entries is uniform in the unit circle. Despite several important partial results (Ginibre-Mehta, Girko, Bai, Edelman, Gotze-Tykhomirov, Pan-Zhu etc) the conjecture remained open for more than 50 years. This summer, T. Tao and I confirmed the conjecture in full generality. I am going to give an overview of this proof, which relies on rather surprising connections between various fields: combinatorics, probability, number theory and theoretical computer science. In particular, tools from additive combinatorics and Hardy-Littlewood circle method from analytic number theory play crucial roles.

In the last 15 years or so connections between questions in real algebraic geometry and functional analysis were discovered and exploited. By working together, algebraists and analysts were able to make progress on important problems in both areas. In this talk we discuss connections between a topic from algebra -- the representation of positive polynomials -- and two problems from analysis -- the classical moment problem and the Bessis-Moussa-Villani conjecture from quantum physics. The talk will be accessible to anyone who knows what polynomials, matrices, and integration are.