Events 

Seminars 

Prof. I. G. Sarma Memorial Lecture Series 

Prof. Priti Shankar Memorial Seminar Series 

Multimedia Archive 



UPCOMING SEMINARS 

Series: Ph.D. Thesis Defense Title: Program Repair by Automated Generation of Hints  Speaker: Ms. Shalini Kaleeswaran
Ph.D student  Faculty Advisor: Prof. Aditya Kanade
 Date and Time: Wednesday, April 05, 2017, 12:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Programming has become an important skill in today's technologydriven
world. It is a complex activity because of which programmers make mistakes
in their software. Student programmers make mistakes in their programs due
to lack of programming experience and also due to lack of understanding of
the algorithmic concepts being used. An experienced programmer in the
industry, on the other hand, makes mistakes in the software he develops
because of the mere complexity of an industrygrade software. Debugging
one's programs, i.e., finding and fixing faults is one of the challenging
activities for a programmer. This necessitates the need to develop
automated techniques that are effective in assisting programmers repair
faults in their programs.
In this thesis, we present new computerassisted approaches to help
programmers repair their programs. Finding repair for a fault in the
program is essentially a search over the space of all possible repairs.
Traditional repair techniques output a complete repaired program that
eliminates the fault in the original program. This ambitious goal of
finding a complete repair is often unachievable because the search space
becomes too large to navigate efficiently. The key insight of our work is
that programmers only need guidelines that help them understand the faults
they made and suggestions on how to fix them, as opposed to a complete
repair. Therefore, this thesis proposes a novel perspective of solving the
program repair problem, where we generate textual hints that direct the
programmer on how to fix the fault. A hint specifies which part of the
program needs modification as well as how to modify it. For student
programmers, our hints help them reflect on the mistakes they made and
improve their understanding of the problem being solved in the program. For
experienced programmers, our hints help them easily identify the cause of
fault and guide them to arrive at a repair. Our approaches use novel
combinations of syntactic, symbolic and statistical reasoning techniques to
achieve this goal of semiautomated program repair.
Our first contribution is an algorithmic technique for automated synthesis
of repair hints. Our technique takes as input a faulty program and a set of
test cases and outputs a ranked list of repair hints that suggest how to
rectify a faulty statement in the program. In this technique, we leverage
symbolic execution and statistical correlation analysis to identify
expressions that are likely to occur in the repaired code. Then we use
syntactic pattern matching to combine these expressions algorithmically and
generate repair hints. Since we restrict ourselves to finding ``building
blocks'' of repair, our hints are very effective in guiding the programmer
to the final repair, even in scenarios where a complete repair cannot be
obtained. We implemented this technique to develop a tool called
``MintHint'', that performs automated synthesis of repair hints for C
programs. We evaluated the effectiveness of MintHint by performing a user
study and found that programmers who used MintHint were able to repair more
faults compared to those who didn't. In addition, they obtained the repair
5.8 times faster.
Our next contribution is a semisupervised feedback generation methodology
for student programming assignments. In this methodology, we take a set of
student submissions as input and generate personalized, verified feedback
for each submission that suggests modifications to fix faults in the
program, if any. Student submissions are first clustered by solution
strategy, which is followed by an automated feedback generation phase. We
use unsupervised clustering to reduce the burden on the instructor in
providing reference implementations for each possible solution strategy.
The instructor is called upon simply to identify a correct submission in
each cluster, which acts as the reference implementation for all
submissions in the cluster. In the next phase, we use a novel
counterexample guided feedback generation algorithm that compares a
student submission with a reference implementation to generate verified
feedback. We applied this methodology to programs implementing iterative
dynamic programming algorithms and developed a tool called ``DPAssist''
that works on C programs. We evaluated DPAssist on a dataset of 2226 student
submissions to 4 programming problems from the programming contest site
CodeChef and successfully generated verified feedback for 85% of them.
 Series: M.Sc. (Engg) Thesis Defense Title: Learning Tournament Solutions from Preferencebased MultiArmed Bandits  Speaker: Mr. Siddartha Ramamohan
M.Sc (Engg.) student at CSA department  Faculty Advisor: Prof. Chiranjib Bhattacharyya
 Date and Time: Thursday, March 30, 2017, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract We consider the dueling bandits problem, a sequential decision task where the goal is to learn
to pick ‘good’ arms out of an available pool by actively querying for and observing relative
preferences between selected pairs of arms. The noisy observed preferences are assumed to be
generated by a ﬁxed but unknown stochastic preference model. Motivated by applications in
information retrieval, ecommerce, crowdsourcing, etc, a number of bandit algorithms have
been proposed in recent years for this task. These have mostly addressed restricted settings
wherein the underlying preference model satisﬁes various structural assumptions; such as
being based on a random utility function or a featurespace embedding, or satisfying
transitivity or sparsity properties, or at least possessing a Condorcet winner – a
single ‘best’ arm that is preferred to all others. In seeking to move beyond such
restricted settings, there has been a recent shift towards alternative notions of ‘good’
arms (including Borda, Copeland and von Neumann winners).
In this work, we extend the dueling bandits problem by adopting, as the
desired target set of good (or ’winning’) arms, a number of tournament
solutions that have been proposed in social choice and voting theory
literature as embodying principled and natural criteria for identifying
good arms based on preference relations. We then propose a family of upper
conﬁdence bound (UCB) based dueling bandit algorithms that learn to play
winning arms from several popular tournament solutions: the top
cycle, uncovered set, Banks set and Copeland set.
We derive these algorithms by ﬁrst proposing a generic UCBbased
framework algorithm that can be instantiated for diﬀerent tournament
solutions by means of appropriately designed ‘selection procedures’. We
show suﬃciency conditions for the resulting dueling bandit algorithms to
satisfy distributiondependent, horizonfree bounds on natural regret
measures deﬁned w.r.t. the target tournament solutions. In contrast to
previous work, these bounds do not require restrictive structural
assumptions on the preference model and hold for a range of diﬀerent tournament solutions.
We develop selection procedures that satisfy the suﬃciency conditions for several popular
tournament solutions, yielding dueling bandit algorithms UCBTC, UCBUC, UCBBA and
UCBCO for the top cycle, uncovered set, Banks set and the Copeland set
respectively. The O((K^2 lnT)⁄g^2 ) bounds we derive are optimal in their
dependence on the time horizon T; and we show that the distributiondependent ‘margin’ g is lowerbounded
by the separation or the relative advantage of top cycle arms over nontop cycle arms.
We empirically validate these claims and evaluate the proposed algorithms, comparing
them to dueling bandit algorithms RUCB, SAVAGE and BTMB over synthetic and realworld
preference models. We show that the UCBTS algorithms perform competitively over
models that possess a Condorcet winner, but outperform the other algorithms over
more general models that do not possess a Condorcet winner.


PAST SEMINARS 

Series: Ph.D. Thesis Defense Title: New Techniques for Automatic Short Answer Grading  Speaker: Mr. Shourya Roy
Xerox Research Centre India
Bangalore  Faculty Advisor: Prof. Y. Narahari (IISc) Dr. Manish Gupta (Xerox Research Centre India)
 Date and Time: Tuesday, March 28, 2017, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Assessing learners' acquired knowledge by students is a key aspect of
the
pedagogical ecosystem. Conducting periodic assessment exercises by
manual
means is clearly monotonous, nonrewarding, and moreover, infeasible for
large student populations such as in massive online open courses. The
scope of computer assisted assessment has been predominantly
constrained
to "recognition" type questions (for example, multiple choice
questions).
Research towards automatic grading of students' constructed responses is
still in infancy and this thesis represents an attempt to advance the
stateoftheart in this area. In particular, the thesis focuses
attention
on automatic short answer grading (ASAG) which involves automatically
grading short answers to questions in natural language, having a length
of
a few words to a few sentences. We propose new techniques and novel
algorithms that could become the core of ASAG systems.
Unsupervised Approach
We first explore approaches based on textual similarity measures. We
advance the current art by applying wordembedding models and showing
that they provide a strong baseline. Second, we focus our attention on
the
vexed problem of unreliable performance of unsupervised ASAG techniques
caused by their sole reliance on instructor provided model answers. We
make an intriguing observation, "Wisdom of students": students' answers
to
a question contain significant lexical commonalities and more often than
not, the commonalities are related to the correct answer to the
question.
Harnessing classical sequential pattern mining techniques, we propose a
"fluctuation smoothing" approach that not only improves the performances
of ASAG techniques but makes them more reliable irrespective of how the
model answers are articulated.
Supervised Approach
Most prior work in supervised ASAG systems have considered groundtruth
scores of nominal or continuous type. We show that an ordinal regression
formulation with discrete ratio scores yields a superior performance
than
classification or regression. Besides, we demonstrate that considering
students' responses in an ensemble along with model answer based feature
helps handle certain types of questions in a much better way.
Transfer Learning Based Approach
While supervised techniques provide superior performance, they need
ongoing instructor involvement for creating labeled data in the form of
graded answerscripts. This undermines the benefit obtained by the
automation of the grading process. We propose an iterative transfer
learning based approach for ASAG by considering different questions as
different domains. Building on the supervised ensemble framework, we
employ canonical correlation analysis based common feature
representation
to transfer model answer based features from a source question to a
target
question and iteratively build the labeled data pool for the students'
response based classifier.
Selecting an Optimal Technique
We highlight that the performance of ASAG techniques depends on the
nature
and difficulty levels of questions as well as on the diversity of
students' answers. This is compounded by the fact that evaluation
measures
for ASAG techniques have remained fairly nonstandard and different
measures favor different ASAG techniques. Building on this observation,
we
propose a rigorous method to automatically learn a mapping from
questions
to ASAG techniques using minimal human expert/crowd) feedback. We do
this
by formulating the learning task as a contextual bandits problem and
provide a regret minimization algorithm that handles key practical
considerations such as noisy experts and similarity between questions.
 Series: M.Sc. (Engg) Colloquium Title: Supervised Classification of Missense Mutations as Pathogenic or Tolerated
using Ensemble Learning Methods  Speaker: Ms. Rashmi Balasubramanyam
M.Sc (Engg.) student at CSA department  Faculty Advisor: Prof. Chiranjib Bhattacharyya
 Date and Time: Tuesday, March 28, 2017, 10:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Missense mutations account for more than 50% of the mutations known to be involved
in human inherited diseases. Missense classification is a challenging task
that involves sequencing of the genome, identifying the variations, and
assessing their deleteriousness. This is a very laborious, time and cost
intensive task to be carried out in the laboratory. Advancements in bioinformatics
have led to several largescale nextgeneration genome sequencing projects, and
subsequently the identification of genome variations. Several studies have
combined this data with information on established deleterious and neutral
variants to develop machine learning based classifiers.
There are significant issues with the missense classifiers due to which missense
classification is still an open area of research. These issues can be classified
under two broad categories: (a) Dataset overlap issue  where the performance
estimates reported by the stateoftheart classifiers are overly optimistic
as they have often been evaluated on datasets that have significant overlaps
with their training datasets. Also, there is no comparative analysis of these
tools using a common benchmark dataset that contains no overlap with the
training datasets, therefore making it impossible to identify the best
classifier among them. Also, such a common benchmark dataset is not
available. (b) Inadequate capture of vital biological information of the
protein and mutations  such as conservation of longrange amino acid
dependencies, changes in certain physicochemical properties of the
wildtype and mutant amino acids, due to the mutation. It is also not
clear how to extract and use this information. Also, some classifiers
use structural information that is not available for all proteins.
In this study, we compiled a new dataset, containing around 2  15%
overlap with the popularly used training datasets, with 18,036 mutations
in 5,642 proteins. We reviewed and evaluated 15 stateoftheart missense
classifiers  SIFT, PANTHER, PROVEAN, PhDSNP, Mutation Assessor, FATHMM,
SNPs&GO, SNPs&GO3D, nsSNPAnalyzer, PolyPhen2, SNAP, MutPred, PONP2,
CONDEL and MetaSNP, using the six metrics  accuracy, sensitivity, specificity,
precision, NPV and MCC. When evaluated on our dataset, we observe huge
performance drops from what has been claimed. Average drop in the
performance for these 13 classifiers are around 15% in accuracy, 17% in
sensitivity, 14% in specificity, 7% in NPV, 24% in precision and 30% in MCC.
With this we show that the performance of these tools is not consistent on
different datasets, and thus not reliable for practical use in a clinical setting.
As we observed that the performance of the existing classifiers is poor in
general, we tried to develop a new classifier that is robust and performs
consistently across datasets, and better than the stateoftheart
classifiers. We developed a novel method of capturing longrange amino
acid dependency conservation by boosting the conservation frequencies of
substrings of amino acids of various lengths around the mutation position
using AdaBoost learning algorithm. This score alone performed equivalently
to the sequence conservation based tools in classifying missense mutations.
Popularly used sequence conservation properties was combined with this boosted
longrange dependency conservation scores using AdaBoost algorithm. This
reduced the class bias, and improved the overall accuracy of the classifer.
We trained a third classifier by incorporating changes in 21 important
physicochemical properties, due to the mutation. In this case, we
observed that the overall performance further improved and the class
bias further reduced. The performance of our final classifier is comparable
with the stateoftheart classifiers. We did not find any significant
improvement, but the classspecific accuracies and precisions are marginally
better by around 12% than those of the existing classifiers. In order to
understand our classifier better, we dissected our benchmark
dataset into: (a) seen and unseen proteins, and (b) pure and mixed proteins,
and analyzed the performance in detail. Finally we concluded that our
classifier performs consistently across each of these categories of seen, unseen,
pure and mixed protein.
 Series: M.Sc. (Engg) Colloquium Title: Computing Contour Trees for 2D Piecewise Polynomial Functions  Speaker: Girijanandan Nucha
MSc (Engg) student  Faculty Advisor: Prof. Vijay Natarajan
 Date and Time: Monday, March 27, 2017, 11:00 AM
 Venue: CSA Multimedia Class (Room No. 252, First Floor)
Abstract Contour trees are extensively used in scalar field analysis. The contour tree is a
data structure that
tracks the evolution of level set topology in a scalar field. Scalar fields are
typically available as
samples at vertices of a mesh and are linearly interpolated within each cell of the
mesh. A more
suitable way of representing scalar fields, especially when a smoother function
needs to be modeled,
is via higher order interpolants. We propose an algorithm to compute the contour
tree for such func
tions. The algorithm computes a local structure by connecting critical points using
a numerically
stable monotone path tracing procedure. Such structures are computed for each cell
and are stitched
together to obtain the contour tree of the function. The algorithm is scalable to
higher degree inter
polants whereas previous methods were restricted to quadratic or linear
interpolants. The algorithm
is intrinsically parallelizable and has potential applications to isosurface
extraction.
 Series: Ph.D. Thesis Defense Title: Resolving the Complexity of Some Fundamental
Problems in Computational Social Choice  Speaker: Mr. Palash Dey
Ph.D student  Faculty Advisor: Prof. Y. Narahari and Dr. Arnab Bhattacharyya
 Date and Time: Friday, March 24, 2017, 9:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In many real world situations, especially involving multiagent systems
and
artificial intelligence, participating agents often need to agree upon a
common alternative even if they have differing preferences over the
available alternatives. Voting is one of the tools of choice in these
situations. Common and classic applications of voting in modern
applications include collaborative filtering and recommender systems,
metaserach engines, coordination and planning among multiple automated
agents, etc. Agents in these applications usually have computational
power
at their disposal. This makes the study of computational aspects of
voting
crucial. This thesis is devoted to a study of computational complexity
of
several fundamental problems arising in the context of voting theory.
The typical setting for our work is an "election"; an election consists
of
a set of voters or agents, a set of alternatives, and a voting rule. The
vote of any agent can be thought of as a ranking (more precisely, a
complete order) of the set of alternatives. A voting profile comprises a
collection of votes of all the agents. Finally, a voting rule is a
mapping
that takes as input voting profile and outputs an alternative, which is
called the "winner" or "outcome" of the election. Our work can be
categorized into three parts as described below.
Part I: Preference Elicitation
In the first part of the thesis, we study the problem of eliciting the
preferences of a set of voters by asking a small number of comparison
queries (such as who a voter prefers between two given two alternatives)
for various interesting domains of preferences.
We commence with considering the domain of single peaked preferences on
trees. We show tight dependencies between query complexity of
preference elicitation and various parameters of the single peaked tree,
for example, number of leaves, diameter, path width, maximum degree of a
node, etc. We next consider preference elicitation for the domain of
single crossing preference profiles. We establish that the query
complexity of preference elicitation in this domain crucially depends on
how the votes are accessed and on whether or not any single crossing
ordering is known a priori.
Part II: Winner Determination in Elections
In the second part of the thesis, we undertake a study of computational
complexity of several important problems related to determining the
winner
of an election. We begin with a study of the following problem: Given an
election, predict the winner of the election under some fixed voting
rule
by sampling as few votes as possible. We establish optimal or almost
optimal bounds on the number of votes one needs to sample for many
commonly used voting rules. We next study efficient sampling based
algorithms for estimating the margin of victory of a given election for
many common voting rules.
Following this, we design an optimal algorithm for determining the
plurality winner of an election when the votes are arriving one by one
in
a streaming fashion. Our work resolves an intriguing question on finding
heavy hitters, that has remained open for more than 35 years, in the
data
stream literature. We also provide near optimal algorithms for
determining
the winner of a stream of votes for other popular voting rules, for
example, veto, Borda, maximin, etc.
Voters' preferences are often partial orders instead of complete orders.
This is known as the incomplete information setting in computational
social choice theory. We study the kernelization complexity (under the
complexity
theoretic framework of parameterized complexity) of the possible winner
problem and show that there do not exist kernels of size that is
polynomial in the number of alternatives for this problem for commonly
used voting rules. However, we show that the problem of coalitional
manipulation which is an important special case of the possible winner
problem admits a kernel whose size is polynomially bounded in the number
of alternatives for common voting rules.
Part III: Election Control
In the final part of the thesis, we study the computational complexity
of
various interesting aspects of strategic behavior in voting.
First, we consider the impact of partial information in the context of
strategic manipulation. We show that lack of complete information makes
the computational problem of manipulation intractable for many commonly
used voting rules. Next, we initiate the study of the computational
problem of detecting possible instances of election manipulation. We
show
that detecting manipulation may be computationally easy under certain
scenarios even when manipulation is intractable.
The computational problem of bribery is an extensively studied problem
in
computational social choice theory. We study computational complexity of
bribery when the briber is frugal in nature. We show for many common
voting rules that the bribery problem remains intractable even when the
briber's behavior is restricted to be frugal, thereby strengthening
intractability results from the literature.
 Series: Department Seminar Title: Learning from Untrusted Data  Speaker: Prof. Moses Charikar,
Computer Science Stanford University USA.  Date and Time: Friday, March 24, 2017, 3:00 PM
 Venue: CSA Lecture Hall (Room No. 117, Ground Floor)
Abstract The vast majority of theoretical results in machine learning and statistics assume that the available
training data is a reasonably reliable reflection of the phenomena to be learned or estimated. Similarly,
the majority of machine learning and statistical technique s used in practice are brittle to the presence
of large amounts of biased or malicious data. In this work we propose two novel frameworks in which
to study estimation, learning, and optimization in the presence of significant fractions of arbitrary data.
The first framework, which we termlistdecodable learning, asks whether it is possible to return a list of
answers, with the guarantee that at least one of them is accurate. For example, given a dataset of
n points for which an unknown subset of αn points are drawn from a distribution of interest, and no assu
mptions are made about the remaining (1−α)n points, is it possible to return a list of poly(1/α)
answers, one of which is correct? The second framework, which we term the semiverified
learning model considers the extent to which a small dataset of trusted data (drawn from th
e distribution in question) can be leveraged to enable the accurate extraction of information from a much
larger but untrusted dataset (of which only an αfraction is drawn from the distribution).
We show strong positive results in both settings, and provid e an algorithm for robust learning in a very
general stochastic optimization setting. This general result has immediate implications for robust esti
mation in a number of settings, including for robustly estimating the mean of distributions with bounded
second moments, robustly learning mixtures of such distributions, and robustly finding planted partitions
in random graphs in which significant portions of the graph have been perturbed by an adversary.
Speaker Bio: Moses Charikar is a professor of Computer Science at Stanford University.
He obtained his PhD from Stanford in 2000, spent a year in the research
group at Google, and was on the faculty at Princeton from 20012014. He is
broadly interested in the design and analysis of algorithms with an
emphasis on approximation algorithms for hard problems, metric embeddings
and algorithmic techniques for big data. His work on dimension reduction
won the best paper award at FOCS 2003. He was awarded the 2012 Paris
Kanellakis Theory and Practice Award for his work on locality sensitive
hashing, and was named a Simons Investigator in theoretical computer
science in 2014.
Host Faculty: Dr. Anand Louis
 Series: Ph.D. Thesis Defense Title: "Design of Quality Assuring Mechanisms with Learning, for Strategic
Crowds"  Speaker: Satyanath Bhat
Ph.D student  Faculty Advisor: Prof. Y Narahari
 Date and Time: Wednesday, March 22, 2017, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this thesis, we address several generic problems concerned with
procurement of tasks from a crowd that consists of strategic workers
with
uncertainty in their qualities. These problems assume importance as the
quality of services in a service marketplace is known to degrade when
there is (unchecked) information asymmetry pertaining to quality.
Moreover, crowdsourcing is increasingly being used for a wide variety of
tasks these days since it offers high levels of flexibility to workers
as
well as employers. We seek to address the issue of quality uncertainty
in
crowdsourcing through mechanism design and machine learning. As the
interactions in webbased crowdsourcing platform are logged, the data
captured could be used to learn unknown parameters such as qualities of
individual crowd workers. Further, many of these platforms invite bids
by
crowd workers for available tasks but the "strategic" workers may not
bid
truthfully. This warrants the use of mechanism design to induce truthful
bidding. There ensues a complex interplay between machine learning and
mechanism design, leading to interesting technical challenges. We
resolve
some generic challenges in the context of the following problems.
(1) Design of a quality eliciting mechanism with interdependent values
We consider an expert sourcing problem, where a planner seeks opinions
from a pool of experts. Execution of the task at an assured quality
level
in a cost effective manner turns out to be a mechanism design problem
when the individual qualities are private information of the experts.
Also, the task execution problem involves interdependent values, where
truthfulness and efficiency cannot be achieved in an unrestricted
setting
due to an impossibility result. We propose a novel mechanism that
exploits
the special structure of the problem and guarantees allocative
efficiency,
expost incentive compatibility and strict budget balance for the
mechanism, and expost individual rationality for the experts.
(2) Design of an optimal bidimensional crowdsourcing auction
We study the problem faced by an auctioneer who gains stochastic rewards
by procuring multiple units of a service from a pool of heterogeneous
strategic workers. The reward obtained depends on the inherent quality
of
the worker; the worker's quality is fixed but unknown. The costs and
capacities are private information of the workers. The auctioneer is
required to elicit costs and capacities (making the mechanism design
bidimensional) and further, has to learn the qualities of the workers
as
well, to enable utility maximization. To solve this problem, we design a
bidimensional multiarmed bandit auction that maximizes the expected
utility of the auctioneer subject to incentive compatibility and
individual rationality while simultaneously learning the unknown
qualities
of the agents.
(3) Design of a multiparameter learning mechanism for crowdsourcing
We investigate the problem of allocating divisible jobs, arriving
online,
to workers in a crowdsourcing platform. Each job is split into a certain
number of tasks that are then allocated to workers. These tasks have to
meet several constraints that depend on the worker performance. The
performance of each worker in turn is characterized by several intrinsic
stochastic parameters. In particular, we study a problem where each
arriving job has to be completed within a deadline and each task has to
be completed, honouring a lower bound on quality. The job completion
time
and quality of each worker are stochastic with fixed but unknown means.
We
propose a learning mechanism to elicit the costs truthfully while
simultaneously learning the stochastic parameters. Our proposed
mechanism
is dominant strategy incentive compatible and expost individually
rational with asymptotically optimal regret performance.
 Series: Ph.D. Thesis Defense Title: Incentive Design for Crowdfunding and Crowdsourcing Markets  Speaker: Mr. Praphul Chandra,
Hewlett Packard Enterprise, Bangalore
(ERP Candidate)  Faculty Advisor: Prof. Y. Narahari (IISc) and Dr. Sitaram Ramachandrula (Hewlett Packard Enterprise)
 Date and Time: Tuesday, March 21, 2017, 11:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract With the everincreasing trend in the number of social interactions
getting intermediated by technology (the world wide web) as the
backdrop, this thesis focuses on the design of mechanisms for
online communities (crowds)which strive to come together, albeit
in adhoc fashion, to achieve a social objective. Two examples of
such webbased social communities which are of central concern
in this thesis are crowdsourcing markets and crowdfunding platforms.
For these settings which involve strategic human agents, we design
mechanisms that incentivize contributions (effort, funds, or information)
from the crowd and aggregate these contributions to achieve the specified
objective. Our work is thus concerned with the challenge of designing mechanisms
which encourage social coordination and cooperation among large groups of
(often) anonymous users to achieve group efficiency (social welfare).
We address the following related challenges:
• Can we design mechanisms to solve the freerider problem in public
goods settings? Can large anonymous groups of individuals be incentivized
to contribute to create public goods?
• Can we design mechanisms that harness social networks to achieve
coordination of contributions towards a public good to ensure that
publicly desirable goods are successfully funded via private contributions?
How do we make such mechanisms fair?
• Can we design mechanisms that improve the efficiency of markets by
expanding the set of individuals who participate in the market? Can these
individuals be incentivized to increase the group efficiency and, if so, at what cost?
• Can we design mechanisms that make crowdsourcing markets more
equitable by offering participation opportunities to novices and higher
incentives to agents with high reliability? What is the price of reliability?
Using mechanism design as the principal design tool, the thesis attempts
to offer rigorous solutions to the above challenges.
 Series: Ph.D. Thesis Defense Title: NonParametric Clustering of Multivariate Count Data  Speaker: Ms. Lavanya Sita Tekumalla
 Faculty Advisor: Prof. Chiranjib Bhattacharyya
 Date and Time: Monday, March 20, 2017, 9:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract While there has been significant work in Bayesian nonparametric modeling
in the last decade there has been much less work on nonparametric
clustering of Multivariate Count Data. The first contribution of this
thesis addresses extensions to clustering with Poisson based models for
multivariate counts. While the Poisson is the most popular distribution for
count modeling, the Multivariate Poisson, often leads to intractable
inference and a suboptimal fit of the data. To address this, we introduce
a family of models based on the SparseMultivariate Poisson, that exploit
the inherent sparsity in multivariate data, leading to a better fit and
more efficient inference. We explore Dirichlet process mixture model
extensions and temporal nonparametric extensions to models based on the
Sparse Multivariate Poisson for practical use of Poisson based models for
nonparametric clustering of multivariate counts. A second contribution of
this thesis addresses moving beyond the limitations of Poisson based models
for nonparametric clustering, for instance in handling over dispersed data
or data with negative correlations. We explore, for the first time,
marginal independent inference techniques based on the Gaussian Copula for
multivariate count data in the Dirichlet Process mixture model setting.
This enables nonparametric clustering of multivariate counts without
limiting assumptions that usually restrict the marginals to belong to a
particular family. This inference technique can also work for mixed data (a
combination of counts, binary and continuous data) enabling Bayesian
nonparametric modeling to be used for a wide variety of data types. The
third contribution of this thesis addresses modeling a wide range of more
complex dependencies such as asymmetric and tail dependencies with Vine
Copula based Dirichlet process mixtures. While vine copula inference has
been well explored for continuous data, it is still a topic of active
research for multivariate counts and mixed multivariate data. An efficient
marginal independent inference approach based on extended rank likelihood,
is proposed in this thesis, extending the use vines for multivariate counts
and mixed data in practical clustering scenarios.
This thesis also explores the novel systems application of Bulk Cache
Preloading by analyzing I/O traces though predictive models for temporal
nonparametric clustering of multivariate count data. State of the art
techniques in the caching domain are limited to exploiting shortrange
correlations in memory accesses at the millisecond granularity or smaller.
We explore for the first time, Bulk Cache Preloading, the process of
proactively predicting data to load into cache, minutes or hours before
the actual request from the application, by leveraging longer range
correlation at the granularity of minutes or hours. Our approach involves
data aggregation, converting I/O traces into a temporal sequence of
multivariate counts, that we analyze with the temporal nonparametric
clustering models.
As an additional contribution, this thesis addresses multilevel
nonparametric admixture modeling for discrete data in the form of grouped
categorical data. Nonparametric topic models for document collections, is
well explored with admixture models such as the Hierarchical Dirichlet
Process. However, there exist scenarios, where a document requires being
associated with themes at multiple levels, where each theme is itself an
admixture over themes at the previous level, motivating the need for
multilevel admixtures. We propose the nested Hierarchical Dirichlet
Process to address this problem and apply a two level version of our model
for nonparametric entitytopic modeling to automatically learn entities in
the form of authors and topics from research corpora.
 Series: Department Seminar Title: Designing Efficient BudgetConstrained Incentive Schemes: To
Compete or To Cooperate?  Speaker: Dr. Ragavendran Gopalakrishnan
Conduent Labs  Date and Time: Thursday, March 16, 2017, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract This paper studies designing realworld performancebased incentive
schemes, which are necessarily budgetconstrained, must be simple to
understand and implement, and satisfy some fairness criteria.
Participants incur a cost of effort for their performance, which they
trade off with the incentives received. The resulting competition for
incentives is modeled as a noncooperative game. First, we characterize
budgetconstrained incentive schemes that maximize performance at Nash
equilibrium, and observe, interestingly, that the maximum performance is
a concave function of the available budget. Second, we study competitive
vs. cooperative fairness among high and low performing players to
quantify the efficiency loss in moving from Nash to dominant strategy
equilibrium; perhaps surprisingly, under a certain mixed fairness model,
this loss is zero, and the equilibrium is unique. Third, we perform
numerical experiments (when players are homogeneous/heterogeneous in
their type, and when the employer has only partial type information),
and observe interesting phenomena, e.g., an employer’s inability to
typediscriminate is not a significant disadvantage, and the expected
maximum average performance is quite robust to onesided typeestimation
error. Finally, using real employee data from a large BPO organization,
we show that our incentive scheme can result in up to a 29.8% increase
in average performance of its employees.
Host Faculty: Dr. Siddharth Barman
 Series: M.Sc. (Engg) Colloquium Title: Generalizations of Hitting, Covering and Packing problems on Intervals  Speaker: Mr. Datta Krupa
M.Sc student at CSA department  Faculty Advisor: Prof. Sathish Govindarajan
 Date and Time: Tuesday, March 14, 2017, 10:30 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Interval graphs are well studied structures. Intervals can represent
resources like jobs to be scheduled. Finding maximum independent set in
interval graphs would correspond to scheduling maximum number of
nonconflicting jobs on the computer. Most optimization problems on
interval graphs like independent set, vertex cover, dominating set, maximum
clique, etc can be solved efficiently using combinatorial algorithms in
polynomial time. Hitting, Covering and Packing problems have been
extensively studied in the last few decades and have applications in
diverse areas. While they are NPhard for most settings, they are
polynomial solvable for intervals. In this thesis, we consider the
generalizations of hitting, covering and packing problems for intervals.
For the general setting, we model the problems as mincost flow problems
using nontrivial reduction and solve it using standard flow algorithms.
Demandhitting problem which is a generalization of hitting problem is
defined as follows: Given n intervals, a positive integer demand for every
interval, m points, a real weight for every point, select a subset of
points H, such that every interval contains at least its demand many points
from H and sum of the weight of points in H minimized. When demands of
intervals are one we give dynamic programming based O(m+n) time algorithm
assuming that intervals and points are sorted. When demands are same, (say
k), we give O(m^2*n) time flow based algorithm. For the general case, we
make an assumption that no interval is contained in another interval.
Under this assumption, we give O(m^2*n) time flow based algorithm.
Demandcovering problem which is a generalization of covering problem is
defined as follows: Given n intervals, a real weight for every interval, m
points, a positive integer demand for every point, select a subset of
intervals C, such that every point is contained in at least its demand many
intervals from C and sum of the weight of intervals in C minimized. When
demand of points are one, we give dynamic programming based O(m+n log n)
time algorithm. When demands are same, (say k) we give O(m*n^2) time flow
based algorithm. For the general case, we give O(m*n^2) time flow based
algorithm.
kpack points problem which is a generalization of packing problem is
defined as follows: Given n intervals, an integer k, m points, a real
weight for every point, select a subset of points Y, such that every
interval contains at most k points from Y and sum of the weight of points
in Y is maximized. For kpack points problem, we give O(m^2 log m) time flow
based algorithm to solve it assuming intervals and points are sorted.
 Series: Ph.D. Colloquium Title: Optimization Algorithms for Deterministic,
Stochastic and Reinforcement Learning Settings  Speaker: Mr. Ajin George Joseph
PhD student at CSA department  Faculty Advisor: Prof. Shalabh Bhatnagar
 Date and Time: Monday, March 13, 2017, 2:30 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Optimization is a very important field with diverse applications in
physical, social and biological sciences and in various areas of
engineering. It appears widely in machine learning, information retrieval,
regression, estimation, operations research and a wide variety of
computing domains. The subject is being deeply studied and a lot
of algorithms are available in the literature. These algorithms which can
be executed (sequentially or concurrently) on a computing machine explore
the space of input parameters to seek high quality solutions to the
optimization problem with the search mostly guided by certain structural
properties of the objective function. In this thesis, we propose
an optimization algorithm which is gradientfree, i.e., does not employ
any knowledge of the gradient or higher order derivatives of the objective
function, rather utilizes objective function values
themselves to steer the search. The proposed algorithm is particularly
effective in a blackbox setting, where a closedform expression of the
objective function is unavailable and gradient or higherorder derivatives
are hard to compute or estimate. Our algorithm is inspired by the well
known cross entropy (CE) method. The CE method is a model based
search method to solve continuous/discrete multiextremal optimization
problems, where the objective function has minimal structure. The
proposed method seeks, in the statistical manifold of the parameters
which identify the probability distribution/model defined over the input
space to find the degenerate distribution concentrated on the global
optima (assumed to be finite in quantity). In the early part of the
thesis, we propose a novel stochastic approximation version of the CE
method to the unconstrained optimization problem, where the objective
function is realvalued and deterministic. The basis of the algorithm is a
stochastic process of model parameters which is probabilistically
dependent on the past history, where we reuse all the previous samples
obtained in the process till the current instant based on discounted
averaging. This approach can save the overall computational and storage
cost. Our algorithm is incremental in nature and possesses attractive
features such as stability, computational and storage efficiency and
better accuracy. We further investigate, both theoretically and
empirically, the asymptotic behaviour of the algorithm and find that the
proposed algorithm exhibits global optimum convergence for a particular
class of objective
functions.
Further, we extend the algorithm to solve the
simulation/stochastic optimization problem. In stochastic
optimization, the objective function possesses a stochastic characteristic, where the
underlying probability distribution in most cases is hard to comprehend
and quantify. This begets a more challenging optimization problem, where
the pretentious nature is due to the hardness in computing the objective
function values for various input parameters with absolute certainty. In
this case, one can only hope to obtain noise corrupted objective function
values for various input parameters. Settings of this kind can be found in
scenarios where the objective function is evaluated using a continuously
evolving dynamical system or through a simulation. We propose a
multitimescale stochastic approximation algorithm, where we integrate an
additional timescale to accommodate the noisy measurements and decimate
the effects of the gratuitous noise asymptotically. We found that if the
objective function and the noise involved in the measurements are well
behaved and additionally the timescales are compatible then our algorithm
can generate high quality solutions. In the later part of the thesis, we
propose algorithms for reinforcement learning/Markov decision processes
using the optimization techniques we developed in the
early stage. MDP can be considered as a generalized framework for
modeling planning under uncertainty. We provide a novel algorithm for the
problem of prediction in reinforcement learning, i.e., estimating the
value function of a given stationary policy of a model free MDP (with
large state and action spaces) using the linear function
approximation architecture. Here, the value function is defined as the
longrun average of the discounted transition costs. The resource
requirement of the proposed method in terms of computational and storage
cost scales quadratically in the size of the feature set. The algorithm is
an adaptation of the multitimescale variant of the CE method
proposed in the earlier part of the thesis for simulation optimization. We
also provide both theoretical and empirical evidence to corroborate the
credibility and effectiveness of the approach.
In the final part of the thesis, we consider a modified version
of the control problem in a model free MDP with large state and action
spaces. The control problem most commonly addressed in the literature is
to find an optimal policy which maximizes the value function, i.e., the
longrun average of the discounted transition payoffs. The contemporary
methods also presume access to a generative model/simulator of the MDP
with the hidden premise that observations of the system behaviour in the
form of sample trajectories can be obtained with ease from the model. In
this thesis, we consider a modified version, where the cost function to
be optimized is a realvalued performance function (possibly nonconvex) of
the value function. Additionally, one has to seek the optimal policy without
presuming access to the generative model. In this thesis, we propose a
stochastic approximation algorithm for this peculiar control problem. The
only information, we presuppose, available to the algorithm is the
sample trajectory generated using a priori chosen behaviour policy. The
algorithm is data (sample trajectory) efficient, stable, robust as well as
computationally and storage efficient. We also provide a proof of
convergence of our algorithm to a high performing policy relative to the
behaviour policy.
 Series: Department Seminar Title: Urban sustainability, preserving privacy  Speaker: Dr Rijurekha Sen
Max Planck Institute for Software Systems  Date and Time: Monday, March 13, 2017, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Developing regions are moving towards rapid urbanization, with tremendous
growth in urban population who are attracted by the economic prospects in
cities. The growth and management of urban infrastructure has to match
this population growth, to make our cities efficient, sustainable and more
livable. In this talk, I will give a brief overview of different projects
where I have used Computer Science methodologies for applications in urban
sustainability. I will describe one project in detail where we monitored
traffic queues at low latency for automated intersection management,
though the traffic was nonlaned and disorderly as is common in developing
countries. The second part of my talk will focus on another system for
privacy preserving sensing, where image capture devices can automatically
sense privacy preferences of people in its vicinity and edit photographs
to match these preferences. This aspect of security and privacy is
important to consider, as gathering information ubiquitously for better
urban management exposes citizens to risks of their privacy violation.
Speaker Bio: Rijurekha Sen is a Humboldt postdoctoral researcher at MaxPlanck
Institute for Software Systems. She works in the area of cyberphysical
systems and uses interdisciplinary Computer Science methods for
applications at the intersection of information technology and society.
She completed her PhD at IIT Bombay and has interned at different
industrial labs and startups like Microsoft Research India and SMU
Livelabs. Her dissertation on automated road traffic monitoring in
developing regions was awarded the ACM India Doctoral Dissertation Award,
2014.
Host Faculty: Prof. Matthew Jacob T
 Series: Department Seminar Title: Accelerating IndustryIISc research collaboration : Leveraging CSR & other investments opportunities  Speaker: Dr.Anurag Srivastava
Chief Operating Officer
SID, IISc  Date and Time: Friday, March 10, 2017, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract In this seminar, I would focus on CSR clarification on areas covered by 18th June, 2014, amendment notification on Schedule VII, section 135. I would also cover what is the current technology industry context for their research needs, what we are doing at SID to tap that and how we can collectively accelerate our association.
Speaker Bio: As the COO for SID, Dr.Anurag Srivastava works with the Chief Executive of SID and is responsible to drive and scale Industry and IISc collaboration to address industry’s innovation, applied research and breakthrough needs to provide global leadership in their markets. This is done through leveraging deep research talent, preexisting IPs of research wealth and state of the art research labs @ IISc. @ SID he will help set up the Innovation Hub (IHub) integrating the ecosystem of IISc research labs, start ups, fund sources and global research associations of faculty members in a very industry friendly model and collaborative work environment to drive Industry Innovation in India and globally wherever possible.
Dr Anurag was the Senior Vice President @ Wipro Technologies serving various business and technology leadership roles in his 16 years career@Wipro, including Platforms based Business Outcome Services head, Chief Technology Officer, EcoEnergy Business head, Consulting Business head, Chief Knowledge & technology Officer Wipro Infotech etc…He incubated new business lines of Cloud business, Internet of Things – Machine to Machine (IoTM2M) platform services, HOLMES platform for IT services hyperautomation @ Wipro. He accelerated innovation across business units, driving research and experimentation, coinnovating with customers, leveraging external ecosystem and ensuring Wipro’s readiness to address future technology opportunities. The portfolio also included driving patents, IPs and service productization to drive nonlinearity across Wipro’s IT business.
He worked in TISLIBM, Novell, HPVerifone, APARNess Technologies and Indian Institute of Science in various technology and business leadership positions earlier. He completed his PhD in Computer Science from Indian Institute of Science (IISc) Bangalore in the area of Cognitive Science, Machine Learning and pattern recognition. He has publications in international conferences, journals and patents and has been speaker in many forums, conferences amd panels.
Host Faculty: Prof.Y.N. Srikant
 Series: Department Seminar Title: Intelligent Inclusive Interaction Design  Speaker: Pradipta Biswas
CPDM, IISc  Date and Time: Friday, March 03, 2017, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The Intelligent Inclusive Interaction Design (I3D) Lab at CPDM
undertakes research in the field of human computer interaction,
intelligent user interfaces and inclusive design. Our present research is
investigating new modalities of interaction and in particular eye gaze
controlled interfaces. We are developing new target prediction and
multimodal fusion algorithms to improve accuracy and response times of
gaze controlled interfaces facilitating human machine interaction in
automotive and military aviation environments and working on detecting
usersâ€™ cognitive load by analysing their ocular parameters. We also
actively pursue research on Assistive Technology for spastic children and
on body posture tracking for developing smart manufacturing system.
This talk in particular will present underlying theories and video
demonstrations of our work on Inclusive User Modelling and Multimodal Gaze
Controlled systems.
Speaker Bio: Pradipta Biswas is an Assistant Professor at the Centre for Product
Design and Manufacturing of Indian Institute of Science. His research
focuses on user modelling and multimodal humanmachine interaction for
aviation and automotive environments and for assistive technology. He set
up and leads the Intelligent Inclusive Interaction Design (I3D) Lab at
CPDM, IISc. Earlier, he was a Senior Research Associate at Engineering
Department, Research Fellow at Wolfson College and Research Associate at
Trinity Hall of University of Cambridge. He completed PhD in Computer
Science at the Rainbow Group of University of Cambridge Computer
Laboratory and Trinity College in 2010 and was awarded a GatesCambridge
Scholarship in 2006. He also conducted a course on Human Computer
Interaction at Indian Institute of Technology, Mandi, guest lectured at
Indian Institute of Technology, Madras and was a vice chairman of ITUT
Focus Group on Smart TV. Besides academics, he was a keen rifle shooter
and won gold medals in Imperial Shooting Meet from 2010 to 2015.
Host Faculty: Prof. Vijay Natarajan
 Series: M.Sc. (Engg) Colloquium Title: Efficient Whole Program Path Tracing  Speaker: Sridhar Gopinath
 Faculty Advisor: Dr. Murali Krishna Ramanathan
 Date and Time: Thursday, February 16, 2017, 4:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract A whole program path (WPP) captures the runtime behavior of a
program in terms of computing the control flow trace of the execution. Obtaining
WPP has multiple benefits that include identifying hot paths, code coverage
analysis, bug detection and reproduction. Existing techniques to compute
WPPs are expensive due to the suboptimal insertion of instrumentation
resulting in the execution incurring significant space and time
overheads. This necessitates the design of an efficient instrumentation strategy to
obtain WPPs. More specifically, the goal is to insert minimum
instrumentation in the program to generate partial traces which can be
used to reconstruct any path precisely.
In this thesis, we design a novel and scalable whole program analysis to
achieve the aforementioned goal. Our approach is inspired by a simple
observation that for any pair of paths in the program, instrumenting one
edge is sufficient to distinguish them. Performing this for all pairs of
paths and identifying the minimum number of edges to instrument reduces
to the minimum hitting set problem. Because collecting all pairs of paths
is practically infeasible, we propose efficient strategies that avoid
collecting the paths explicitly. We employ approximations to overcome
the NPhardness of identifying the minimum instrumentation points. Our
techniques are designed to ensure that these approximations do not affect the precise
reconstruction of the paths.
We have implemented our approach and performed elaborate evaluation on
Java programs. Our experimental results on the DaCapo benchmark suite
demonstrates the efficacy of our approach across multiple dimensions. On
average, our approach instruments 9.5% of the overall number of CFG
edges in the program. The average runtime overhead to generate WPPs using our
approach is 1.97x. More importantly, compared to the stateoftheart in
WPP computation, we observe an average and maximum reduction in runtime
overheads by a factor of 2.8 and 5.4 respectively. Further, our
evaluation shows that our implementation is able to reconstruct WPPs precisely from
the obtained traces.
Speaker Bio: Sridhar Gopinath is a MSc (Engg) student in the Department of
Computer Science and Automation since Aug 2015. His research interests are in software
engineering and programming languages. He is a member of the Scalable Software Systems lab in CSA.
He received a B.E in Computer Science from SJCE, Mysore in 2015.
 Series: Department Seminar Title: Progress in ErrorCorrection: A Survey  Speaker: Prof. Venkatesan Guruswami
CMU, USA  Date and Time: Friday, February 10, 2017, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract Errorcorrecting codes play a crucial role in safeguarding data against
the adverse effects of noise during communication and storage. They are
also powerful tools that underlie several recent advances in theoretical
computer science and combinatorics. The central challenge in coding
theory is to construct codes with minimum possible redundancy for different
error models and requirements on the decoder, along with efficient algorithms
for errorcorrection using those codes. Much progress has been made
toward this quest in the nearly seven decades since the birth of coding theory.
Several fundamental problems, however, are still outstanding, and
exciting new directions continue to emerge to address current
technological demands as well as applications in computational complexity and
cryptography. This talk will survey some of our recent works on
errorcorrection in various models, such as:
 worstcase errors, where we construct list decodable codes with
redundancy as small as the target error fraction;
 i.i.d. errors, where we show polar codes enable efficient
errorcorrection even as the redundancy approaches Shannon capacity;
 bit deletions, where we give codes that can correct the largest known
fraction of deletions;
 single symbol erasure, a model of renewed importance for
tackling node failures in distributed storage, where we give novel
repair algorithms for ReedSolomon codes as well as simple new codes with
lowbandwidth repair mechanisms.
Host Faculty: Dr. Anand Louis
 Series: Department Seminar Title: Algorithmic and optimization aspects of
BrascampLieb inequalities  Speaker: Dr. Ankit Garg, Microsoft Research New England
 Date and Time: Friday, February 10, 2017, 11:00 AM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract The celebrated BrascampLieb (BL) inequalities (and their extensions)
are an important mathematical tool, unifying and generalizing numerous
inequalities in analysis, convex geometry and information theory. While
their structural theory is very well understood, far less is known about
computing their main parameters. We give polynomial time algorithms to
compute:
 Feasibility of BLdatum
 The optimal BLconstant
 A weak separation oracle for the BLpolytope
The algorithms are obtained by a simple efficient reduction of a given
BLdatum to an instance of the Operator Scaling problem defined by
Gurvits, for which the present authors provided a polynomial time
algorithm recently.
If time permits, I will describe the common problem unifying BL
inequalities, operator scaling and many such problems: testing the
NullCone (common zero set of all invariant polynomials) of a group
action on a vector space. A polynomial time algorithm for the NullCone
problems remains an interesting open problem.
This will be based on a joint work with Leonid Gurvits, Rafael Oliveira
and Avi Wigderson and another ongoing work with Peter Burgisser, Rafael
Oliveira, Michael Walter and Avi Wigderson.
Speaker Bio: Ankit Garg is a Postdoctoral researcher at Microsoft Research New
England. Before that he got his PhD in Computer Science from Princeton
University under the guidance of Prof. Mark Braverman and his
undergraduate degree from IIT Delhi. His research interests include
communication complexity, information complexity, algebraic complexity,
and more broadly, computational complexity and theoretical computer
science.
Host Faculty: Dr. Chandan Saha
 Series: Department Seminar Title: Parameterized Complexity of Biclique cover and Partition  Speaker: Davis Issac
Max Planck Institute for Informatik
Saarbruecken
Germany  Date and Time: Wednesday, February 01, 2017, 3:00 PM
 Venue: CSA Seminar Hall (Room No. 254, First Floor)
Abstract I will talk about my recent paper titled "On the parameterized complexity
of biclique cover and Partition" together with Sunil Chandran and Andreas
Karrenbauer published at IPEC 2016 . The problems that I will talk about
are biclique cover and biclique partition. In biclique cover, we are given
a bipartite graph and an integer $k$, and we want to find whether we can
cover all the edges of the graph with at most $k$ compete bipartite
graphs. In biclique partition, the only difference is that we want to
partition the edges instead of covering it..
We come up with an algorithm with $O(2^{k^2})poly(n)$ runnning time for
biclique partition whereas the best previously known fixed parameter
running time for the problem was $O(2^{2^k}poly(n)$. Our algorithm makes
use of a linear algebraic formulation of the problem and uses linear
algebraic techniques.
For biclique cover, we show that it is not possible to get running times
that are better than doubly exponential in terms of k assuming the
Exponential time hypothesis. We also show that there is no
subexponential kernel in terms of $k$ for biclique cover unless $P=NP$.
We achieve these two results by giving a reduction from 3SAT on $n$
variables to an instance of biclique cover with $k=O(log n)$.
Host Faculty: Prof. Sunil Chandran. L

