Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

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 technology-driven 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 industry-grade 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 computer-assisted 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 semi-automated 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 semi-supervised 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 counter-example 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.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Learning Tournament Solutions from Preference-based Multi-Armed 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 fixed but unknown stochastic preference model. Motivated by applications in information retrieval, e-commerce, crowd-sourcing, 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 satisfies various structural assumptions; such as being based on a random utility function or a feature-space 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 confidence 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 first proposing a generic UCB-based framework algorithm that can be instantiated for different tournament solutions by means of appropriately designed ‘selection procedures’. We show sufficiency conditions for the resulting dueling bandit algorithms to satisfy distribution-dependent, horizon-free bounds on natural regret measures defined 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 different tournament solutions.

We develop selection procedures that satisfy the sufficiency conditions for several popular tournament solutions, yielding dueling bandit algorithms UCB-TC, UCB-UC, UCB-BA and UCB-CO for the top cycle, uncovered set, Banks set and the Copeland set respectively. The O((K^2 ln⁡T)⁄g^2 ) bounds we derive are optimal in their dependence on the time horizon T; and we show that the distribution-dependent ‘margin’ g is lower-bounded by the separation or the relative advantage of top cycle arms over non-top 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 real-world preference models. We show that the UCB-TS algorithms perform competitively over models that possess a Condorcet winner, but out-perform the other algorithms over more general models that do not possess a Condorcet winner.

Video Archive Go Top

 

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, non-rewarding, 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 state-of-the-art 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 word-embedding 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 ground-truth 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 answer-scripts. 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 non-standard 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.

Video Archive Go Top

 

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 large-scale next-generation 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 state-of-the-art 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 long-range amino acid dependencies, changes in certain physico-chemical properties of the wild-type 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 state-of-the-art missense classifiers - SIFT, PANTHER, PROVEAN, PhD-SNP, Mutation Assessor, FATHMM, SNPs&GO, SNPs&GO-3D, nsSNPAnalyzer, PolyPhen-2, SNAP, MutPred, PON-P2, 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 state-of-the-art classifiers. We developed a novel method of capturing long-range 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 long-range 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 physico-chemical 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 state-of-the-art classifiers. We did not find any significant improvement, but the class-specific accuracies and precisions are marginally better by around 1-2% 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.

Video Archive Go Top

 

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.

Video Archive Go Top

 

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.

Video Archive Go Top

 

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 termlist-decodable 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 semi-verified 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 2001-2014. 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

Video Archive Go Top

 

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 web-based 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, ex-post incentive compatibility and strict budget balance for the mechanism, and ex-post individual rationality for the experts.

(2) Design of an optimal bi-dimensional 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 bi-dimensional) and further, has to learn the qualities of the workers as well, to enable utility maximization. To solve this problem, we design a bi-dimensional multi-armed 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 multi-parameter 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 ex-post individually rational with asymptotically optimal regret performance.

Video Archive Go Top

 

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 ever-increasing 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 ad-hoc fashion, to achieve a social objective. Two examples of such web-based 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 free-rider 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.

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Non-Parametric 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 non-parametric modeling in the last decade there has been much less work on non-parametric 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 sub-optimal fit of the data. To address this, we introduce a family of models based on the Sparse-Multivariate 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 non-parametric extensions to models based on the Sparse Multivariate Poisson for practical use of Poisson based models for non-parametric clustering of multivariate counts. A second contribution of this thesis addresses moving beyond the limitations of Poisson based models for non-parametric 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 non-parametric 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 non-parametric 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 non-parametric clustering of multivariate count data. State of the art techniques in the caching domain are limited to exploiting short-range correlations in memory accesses at the milli-second granularity or smaller. We explore for the first time, Bulk Cache Preloading, the process of pro-actively 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 non-parametric clustering models.

As an additional contribution, this thesis addresses multi-level non-parametric admixture modeling for discrete data in the form of grouped categorical data. Non-parametric 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 non-parametric entity-topic modeling to automatically learn entities in the form of authors and topics from research corpora.

Video Archive Go Top

 

Series: Department Seminar
Title: Designing Efficient Budget-Constrained 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 real-world performance-based incentive schemes, which are necessarily budget-constrained, 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 budget-constrained 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 type-discriminate is not a significant disadvantage, and the expected maximum average performance is quite robust to one-sided type-estimation 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

Video Archive Go Top

 

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 non-conflicting 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 NP-hard 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 min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms.

Demand-hitting 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.

Demand-covering 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.

k-pack 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 k-pack points problem, we give O(m^2 log m) time flow based algorithm to solve it assuming intervals and points are sorted.

Video Archive Go Top

 

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 gradient-free, 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 black-box setting, where a closed-form expression of the objective function is unavailable and gradient or higher-order 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 multi-extremal 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 real-valued 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 multi-timescale 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 long-run 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 multi-timescale 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 long-run 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 real-valued performance function (possibly non-convex) 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.

Video Archive Go Top

 

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 non-laned 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 post-doctoral researcher at Max-Planck Institute for Software Systems. She works in the area of cyber-physical systems and uses inter-disciplinary 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

Video Archive Go Top

 

Series: Department Seminar
Title: Accelerating Industry-IISc 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, pre-existing IPs of research wealth and state of the art research labs @ IISc. @ SID he will help set up the Innovation Hub (IHub) integrating the eco-system 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 (IoT-M2M) platform services, HOLMES platform for IT services hyper-automation @ Wipro. He accelerated innovation across business units, driving research and experimentation, co-innovating 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 non-linearity across Wipro’s IT business. He worked in TISL-IBM, Novell, HP-Verifone, APAR-Ness 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

Video Archive Go Top

 

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 human-machine 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 Gates-Cambridge 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 ITU-T 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

Video Archive Go Top

 

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 sub-optimal 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 NP-hardness 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 state-of-the-art 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.

Video Archive Go Top

 

Series: Department Seminar
Title: Progress in Error-Correction: 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
Error-correcting 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 error-correction 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 error-correction in various models, such as:

- worst-case 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 error-correction 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 Reed-Solomon codes as well as simple new codes with low-bandwidth repair mechanisms.

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: Department Seminar
Title: Algorithmic and optimization aspects of Brascamp-Lieb 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 Brascamp-Lieb (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 BL-datum - The optimal BL-constant - A weak separation oracle for the BL-polytope

The algorithms are obtained by a simple efficient reduction of a given BL-datum 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 Null-Cone (common zero set of all invariant polynomials) of a group action on a vector space. A polynomial time algorithm for the Null-Cone 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

Video Archive Go Top

 

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 sub-exponential 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

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

Copyright: CSA, IISc 2016      Phone: +91-80-22932368          Fax: +91-80-23602911 Travel Blog    Feedback    Credits