IIIT-Bangalore Theory Club

Hi All,

Yash Khanna is giving a talk on Robust Algorithms for recovering planted structures in Semi-random instances on *Friday* this week (Nov 13) at *5:15pm* on Zoom (https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09). He was kind enough to share the link of this talk with us and everyone interested in theoretical computer science should attend this talk. Find the details below.

Title: Robust Algorithms for recovering planted structures in Semi-random instances
Speaker: Yash Khanna
Affiliation: Indian Institute of Science, Bangalore
Date and Time: 13th November 2020, 5:15pm - 6:15pm
Zoom Link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09

Abstract:
In this work, we design algorithms for two fundamentally important and classical graph problems in the planted setting. Both of these problems are NP-hard and the bounds known from the algorithmic front are either not fully understood, or not much progress can be made because of tight lower bounds. Thus it is natural to consider semi-random models for
these problems. These models are inspired from the seminal paper of Feige and Killian [FK01] and have been studied in numerous follow-up works with the latest ones by Steinhardt, and McKenzie et al. [Ste17, MMT20]. The construction of our instance starts with an empty graph, then an arbitrary set of vertices (S) is chosen and either a dense graph or a clique (or an independent set) is planted on it, the subgraph on S x V-S is a random graph, while the subgraph on V-S might be a random, arbitrary, or some special graph (depending on the model). Our algorithms are based on rounding semi-definite programs and our primary focus is on recovering (completely or partially) the planted structure (S) with high probability (over the randomness of the input). We give algorithms that exploit the geometry of the corresponding vectors (from the SDP) and are easy to design/analyse.

The two problems which we study are:
1. Densest k-Subgraph/Clique
Given an undirected graph G, the Densest k-Subgraph problem (DkS) asks to compute a subset S of V of cardinality k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, in spite of many decades of research, is yet to be
settled. There is a significant gap between the best known worst-case approximation factor of this problem [BCC+10] and the hardness of approximation for it (assuming the Exponential Time Hypothesis) [Man17]. We ask what are some easier instances of this problem? We propose some
natural semi-random models of instances with a planted dense subgraph and study approximation algorithms for computing the densest subgraph in them. There are many such random and semi-random models which have been
studied in the literature [BCC+10, Ame15, HWX16, BA19 etc.].

2. Independent Set in Hypergraphs
The independent set problem in graphs poses the following question: given a graph, and a subset of vertices such that any two vertices of the set do not have an edge between them. The maximization version of this problem features as one of the Karp's original twenty-one
NP-complete problems ([Kar72], the clique problem instead of its complement, the independent set problem). The independent set problem is relatively well understood and by the famous result of Håstad [Hås99], the lower and upper bounds of this problem are tight. Hypergraphs are a natural extension of graphs, where each edge is formed across a tuple of distinct vertices. For a graph, each tuple has a size, two. To the best of our knowledge, semi-random models on hypergraphs have not been studied so far. Studying classical problems like these on hypergraphs is naturally of theoretical as well as practical interest. We study the algorithmic problems studied in McKenzie et al. [MMT20] and develop
algorithms for them in the case of hypergraphs.

Note: This is joint work with Anand Louis and Rameesh Paul. Both of these e-prints will be up on arXiv soon.

Speaker Bio:
Yash Khanna is a third (and final) year M.Tech (Research) student in the Theory Group of CSA, IISc Bangalore. His research interests include Algorithms and Complexity. He previously graduated from BITS Pilani.

Join our Cloud HD Video Meeting Zoom is the leader in modern enterprise video communications, with an easy, reliable cloud platform for video and audio conferencing, chat, and webinars across mobile, desktop, and room systems. Zoom Rooms is the original software-based conference room solution used around the world in board, confer...

Hello People!

As the CoViD-19 pandemic prevails, many of us are lucky enough to get the opportunity to stay at home. Some people work on their passion projects, and others are "bored". A possible way to get rid of this boredom is by learning something new. NPTEL has an awesome, upcoming online course on Information Theory by Dr. Himanshu Tyagi from IISc. This course will be helpful for people with a variety of interests, like Statistics, Algorithms, Machine Learning, Cryptography (yes, even crypto), etc.

Himanshu Tyagi is a great teacher and the course is very well-designed. I hope some of you will take advantage of this opportunity (and privilege), and come out of this pandemic safe and more knowledgeable.

Link:

Information Theory - Course

Combinatorics Challenge -

Suppose we have a regular N sided polygon P.

Let S be the set of all n-sided polygons (N > n) inscribed in P (the n vertices are a subset of the vertices of P) such that none of the smaller polygons share an edge with P.

Can you come up with a formula for the cardinality of S, in terms of n,N ?

Hey guys! Looking for a challenge? Give this a shot.

You've got two dice. One of them is fair. The other one, though, is loaded. It shows 6 with probability 1/2.

You are really bored, so you roll the two dice a total of 100 times (combined) in the following manner -

First you roll the fair die.

Subsequently, if the previous roll was a 6, you roll the loaded die, else you roll the fair one.

What is the expected (average) number of 6's coming up in these 100 rolls?

Might be of interest for some:

ACM India ACM-W India seeks to take forward the task of the ACM community, but with a particular focus on the empowerment of women in computing in India.

Hi all
There is a TCS+ (https://tcsplus.wordpress.com/) talk (on Google hangout) by Artur Czumaj from the University of Warwick on Round Compression for Parallel Matching Algorithms.

Date: March 28th, 2018
Time: 11:30 pm (IST)

Find more details here: https://tcsplus.wordpress.com/2018/03/21/tcs-talk-wednesday-march-28th-artur-czumaj-university-of-warwick/

TCS+ talk: Wednesday, March 28th — Artur Czumaj, University of Warwick The next TCS+ talk will take place this coming Wednesday, March 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Artur Czumaj from the University of War…

The slides and references and applications regarding the talk by Rameshwar on LSH are updated on the website.

https://iiitbtheoryclub.github.io/talks/2018/03/16/locality-sensitive-hashing.html

Have fun!

Locality Sensitive Hashing (LSH) Talk on Locality-Sensitive Hashing by Rameshwar Pratap

Hi all
There is a live streaming of theory of deep learning workshop at Princeton going on. All the theory night owls can enjoy the live streaming. Others can view it later. Do not miss it.

PrincetonDeepMath

Please be updated on our site

https://iiitbtheoryclub.github.io/

We put out slides and whatever extra materials the speakers give us, on the site, for references. You can subscribe to our site via RSS.

Have fun and keep learning

IIIT Bangalore Theory Club Contact moderators at [email protected] [email protected]

Hi Everyone,

The Theory Club is ready with another talk on 14th March (around 5:00pm).

Sushravya GM has kindly volunteered to give a talk on something she has been reading about Classical and Quantum Information Theory and their applications to AI.

All the things are really interesting here, information theory, quantum information theory, and AI. It would be very interesting to see how these things marry together to give birth to new and interesting results and applications.
Just to add my knowledge about Quantum mechanics (Quoting from "Quantum Computing since Democritus" by Scott Aaronson)
"But if quantum mechanics isn’t physics in the usual sense – if
it’s not about matter, or energy, or waves, or particles – then what is it about?
It’s about information and probabilities and observables, and how they relate to each other. Quantum mechanics is what you would inevitably come up with if you started from probability theory and then said, let’s try to generalize it so that the numbers we used to call “probabilities” can be negative numbers. As such, the theory could have been invented by mathematicians in the nineteenth century without any input from experiment. It wasn’t, but it could have been. "
So this sort of gives us the motivation for the field of Quantum Information Theory. How is it to be used in AI? I guess we'll have to wait for the talk and see.

Please let us know if there is any clash with any events, or that if some other date is more preferred for most of the people.