Theoretical Computer Science Group

Theory Seminar Schedule for Spring 2015

The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum computing and related areas are strongly encouraged to attend.

Date Speaker Title
January 20 (in IST 333 at 1:15pm) Grigory Yaroslavtsev (UPenn) Near Optimal LP Rounding for Correlation Clustering on Complete Graphs
January 23 Organizational meeting
January 30 Piotr Berman TBA
February 3 (in IST 333 at 1:20pm) Vanishree Rao (UCLA) Adaptive Multiparty Non-Interactive Key Exchange without Setup in the Standard Model
February 13 Nai-Hui Chia The Hardness of Inverting "One-Way Functions"
February 20 Nithin Varma An Optimal Nonadaptive Tester for Monotonicity on the Boolean Hypercube

Spring 2007     Fall 2007     Spring 2008     Summer 2008     Fall 2008     Spring 2009     Fall 2009     Spring 2010     Fall 2010     Spring 2011     Fall 2011     Spring 2012     Fall 2012     Spring 2013     Fall 2013     Fall 2014

Near Optimal LP Rounding for Correlation Clustering on Complete Graphs

Introduced about 10 years ago by Bansal, Blum and Chawla, correlation clustering has become one of the standard techniques in machine learning and data mining. This due to several advantages of correlation clustering as compared to other standard clustering methods (e.g. k-means):
-Correlation clustering only requires qualitative information about similarities between objects. This makes it applicable in scenarios such as crowdsourced duplicate finding when information about similarities between objects is generated by humans.
-Correlation clustering doesn’t require the number of clusters to be specified in advance, producing the number of clusters that best fits the data.

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps:
-For complete graphs our approximation is 2.06-ε for a fixed constant ε, which almost matches the previously known integrality gap of 2.
-For complete k-partite graphs our approximation is 3. We also show a matching integrality gap.
-For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2.

Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).

Joint work with Shuchi Chawla, Konstantin Makarychev and Tselil Schramm."

Adaptive Multiparty Non-Interactive Key Exchange without Setup in the Standard Model

Non-interactive key exchange (NIKE) is a fundamental notion in Cryptography. This notion was introduced by Diffie and Hellman in 1976. They proposed the celebrated 2-party NIKE protocol and left open as a fascinating question, whether NIKE could be realized in the multiparty setting. NIKE has since then been an active area of research with an ultimate goal of obtaining best possible security in the multiparty setting. Although this has evaded researchers for many decades, advancements have been made through relaxations in multiple directions such as restricting to 3-parties, static/semi-static model (where the adversary needs to commit to the set of parties he wishes to be challenged upon ahead of time), random-oracle model, allowing initial setup, etc.

In this talk, we shall see the first multiparty NIKE protocol that is adaptively secure and in the standard model. (Time permitting; we shall also see how to remove the setup.)

Our construction is based on indistinguishability obfuscation and obliviously-patchable puncturable pseudorandom functions, a new notion that we introduce.

We shall witness employing a novel technique of using indistinguishability obfuscation, which is interesting in its own right and which I believe would find wider applications in other settings. One such technique pertains overcoming, the somewhat inherent, drawback of non-adaptively of the puncturing technique introduced by Sahai and Waters [STOC'14]. Central to this technique is our new notion of obliviously-patchable puncturable pseudorandom functions.

The Hardness of Inverting "One-Way Functions"

One-way functions are functions that are easy to compute but hard to invert in the average case. Almost all crypto systems are based on the assumption that there exists a function which we can compute in polynomial time but which we cannot invert by classical (and quantum) computer in polynomial time. However, the existence of one-way functions is still a mystery.

In this talk, I am going to discuss the problem of whether there exists a polynomial-time computable function such that inverting that function is NP-Hard. Firstly, I will briefly introduce the definitions of one-way function, some complexity classes (NP, AM and IP) and the notion of average-case complexity. Then, I will present results by Akavia and Bogdanov et al., who try to answer the following question: Is it possible to reduce a worst-case NP-Hard problem to the task of inverting a polynomial-time computable function in the average case? Akavia et al show that the existence of a non-adaptive randomized reduction implies NP is in AM intersects coAM, which in turn implies the collapse of polynomial hierarchy. Bogdanov et al also show that if the function is size-verifiable, the existence of an adaptive randomized reduction implies NP is in AM intersects coAM. Their results could be regarded as negative evidences of the existence of one-way functions. Due to the constraint of the time, I will just focus on one of the results. Finally, I will discuss whether quantum computing makes any difference to this question.

An Optimal Nonadaptive Tester for Monotonicity on the Boolean Hypercube

A function f is said to be monotone if for all points x,y in the domain, x < y implies f(x) < f(y). Testing the monotonicity of functions is a fundamental problem in the field of property testing. Given oracle access to a function f, the problem is to determine whether the function is monotone or "far from being monotone".

One of the most studied questions in monotonicity testing is that of testing the property for Boolean functions defined on {0,1}^n. Coming up with an optimal testing algorithm for this problem is an important open question in the area. In a recent breakthrough, Khot et al came up with an optimal nonadaptive testing algorithm for the problem. In the talk, I will formalize the notion of monotonicity testing, list some of the important results and give a high level description of the result due to Khot et al.