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

Suppose we have a collection of sensors in a large region, each of which can detect events within a disk of radius 1. We wish to devise a schedule so that each sensor can sleep for much of the time, while making sure that the whole region is covered by the sensors that are awake. A natural way of doing this is to partition the sensors into k subsets, each subset of sensors covering the whole region. Then in time slot t we activate all the sensors in subset (t mod k). If this is possible we say the sensors are k-partitionable. An obvious necessary condition is that each point in the region is covered by at least k sensors (k-coverage), but this is not in general sufficient. We show that for random deployments of sensors k-coverage usually implies k-partitionability, and identify the most likely obstructions to k-partitionability when this fails. This leads to some natural unsolved problems involving k-partitionability of (deterministic) configurations of disks. This is joint work with B. Bollobas, A. Sarkar, and M. Walters.

For central simple algebras of even degree with orthogonal involutions, invariants modeled on the discriminant and Clifford algebra of quadratic forms were defined by Jacobson and Tits, and a relative cohomological invariant of degree 3 is defined by using the Rost invariant of Spin groups when the first two invariants vanish. Its properties and computation will be discussed in the particular case where the algebra has degree 8 and index 4, in relation with properties of 8-dimensional quadratic forms in $I^2$. (Joint work with Anne Qu\'eguiner-Mathieu).

One of the most powerful tools for improving success rates in introductory computing courses is the incorporation of context -- a theme that pervades the computing lectures, assignments, and examples which relates the content to a concrete application domain. Contextualized computing education has even allowed us to be successful with challenging audiences, such as the non-technical major. In this talk, we review why Georgia Tech has chosen to teach serious computer science to every student on campus, and then discuss research findings from several schools on the benefits and costs of contextualized computing education.

Discrete groups come in all shapes and sizes. I'll show you some. Then I'll explain what I think a quasi-isometry is.

Many groups have the property of having only finitely many conjugacy classes of finite subgroups. Examples include hyperbolic groups, CAT(0) groups, mapping class groups, and automorphism groups of free groups. Do subgroups of these groups inherit this property? The answer turns out to be no. I will describe how combinatorial Morse theory can be used to produce couterexamples. This is joint work with Noel Brady and Matt Clay.

Constraint Satisfaction Problems (CSP) are commonly found in practice and finding effective representation language and efficient constraint solving techniques are important research areas. A recent development is the integration of CSP (specifically SAT) solvers with relational database systems to enable CSPs to be modelled using SQL, and solved within the database system. A key challenge in this integration is to keep the SAT encoding of SQL constraints small. In this work, we describe a divide-and- conquer technique for reducing the encoding of cardinality constraints. We present a number of experiments to show the improvements on performance.

The problem of characterizing and detecting surprisingly recurrent sequence patterns such as substrings or motifs and related associations or rules is pursued ubiquitously in order to compress data, unveil structure, infer succinct descriptions, extract and classify features, etc. In Molecular Biology, some such patterns are variously implicated in facets of biological structure and function. Because of that, Pattern Discovery constitutes one of the most battered, flourishing and arguably useful applications of Computational Molecular Biology. The very notion of a pattern still embodies subtleties and ambiguities, as do related concepts such as class and structure. And the discovery, particularly on a massive scale, of surprising patterns and correlations thereof poses interesting methodological and algorithmic problems, some of which appear to be hardly surmountable. This talk proposes a brief account of algorithmic pattern discovery under constraints of saturation, displays some of its applications, and highlights issues, products and challenges emerged in recent and current work.

V.~Kac classified finite dimensional simple Lie superalgebras over the field of complex numbers in 1970s. They constitute several series and are divided into two types based on their even part: classical type and Cartan type. Lie superalgebras of Cartan type consists of four series $W(n)$, $S(n)$, $S^{~}(n)$, and $H(n)$. In this talk I will briefly introduce Cartan type Lie superalgebras and then I will show how explicitly one can compute cohomology and support varieties for $W(n)$ and $S(n)$. I will also mention what we have for $H(n)$ and present a new theorem on realizability of support varieties that holds both for classical and Cartan type Lie superalgebras. If I have time I am planning to present some open problems at the end of my talk. The results about $W(n)$ represents joint work with Jonathan Kujawa and Daniel Nakano.

Information-centric collaborative sites have emerged as viable sources for many information needs. In particular, the Community Question Answering (CQA) model has evolved as an effective alternative to web search: users post questions and answers, and rate and evaluate each other’s content. As a result, users contribute both content and rich interaction metadata in their roles as askers, answerers, and evaluators. To give a sense of the scale, just one popular site, Yahoo! Answers, has attracted an active participation of millions of users, and has amassed a searchable archive of hundreds of millions of answers to tens of millions of questions. The talk will build on our earlier work on modeling user interactions in web search, and will describe new problems related to mining this user-generated content, including estimating content quality, contributor authority, user intent, and asker satisfaction with the results.