Theory Group

Recent News

• Nalli Sai Soumya is a co-winner of the Best BTP award at CSE Dept.

• Anantha Padmanabha joins the theory group

• Shreyas Pai joins the theory group

• FDP on Core CS Theory

• Narayanaswamy awarded the Best Teacher award (2023) in the CSE Dept

Confirmed Speakers :

1. Title : On the maximum degree of flow critical graphs
   Speaker : Benjamin Moore, IST Austria
   Date, Time & Venue : Tue, Oct 22, 2024, 3:30 PM - SSB 334
   [Abstract]

   A nowhere zero 3 flow (henceforth: NZ3F) is an orientation of a graph such that, at each vertex, the indegree minus the outdegree is divisible by 3. Grotzschs Theorem says that every triangle-free planar graph is 3-colourable. Tutte conjectured a wide-sweeping generalization: every 4-edge-connected graph admits a NZ3F. Lovasz, Thomassen, Wu and Zhang proved that 6-edge-connected graphs admit such a flow. We extend this result by showing that one can allow arbitrarily many 5-edge-cuts or 4-edge-cuts --- under some conditions. Brief Bio: Benjamin is a Canadian mathematician who is currently a postdoc at IST (Institute of Science and Technology), Austria. Prior to this, he was a postdoc at Charles University in Czechia. He did his PhD at the University of Waterloo, and Masters at Simon Fraser University.



2. Title : Planar cycle-extendable graphs
   Speaker : Aditya Dalwadi, CSE @IIT-M
   Date, Time & Venue : Tue, Oct 1, 2024, 3:30 PM - SSB 334
   [Abstract]

   A nontrivial connected graph G is said to be matching covered if each edge is part of some perfect matching. For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs — aka 1-extendable graphs since each edge extends to a perfect matching. In a similar fashion, we say that a matching covered graph G is cycle-extendable if (either) perfect matching of each even cycle Q extends to a perfect matching (of G). Equivalently, a matching covered graph is cycle-extendable if each even cycle can be expressed as a symmetric difference of two perfect matchings. Another motivation to work on cycle-extendable graphs arises from the ear decomposition theory of matching covered graphs (that is similar to the well-known ear decomposition theory of 2-connected graphs). From this viewpoint, a matching covered graph G is cycle-extendable if and only if each even cycle extends to an ear decomposition of G. As of now, there is no known NP characterization of cycle-extendable graphs (in general). Recently, we obtained NP (as well as P) characterizations of planar cycle-extendable graphs. Guo and Zhang (2004) obtained such a characterization for bipartite planar cycle-extendable graphs. We establish a characterization of all planar cycle-extendable graphs — in terms of K2 and four infinite families. As a first step, we reduce our problem to the class of “near-bricks” using a result of Carvalho and Little (2008). Thereafter, we reduce the minimum degree three or more case to "bricks" and prove that the only cycle-extendable planar simple bricks are wheels and prisms — using a result of Norine-Thomas (2007). For the minimum degree two case, we proceed by induction by bicontracting a vertex of degree two; this case comprises the bulk of our proof and case analysis. Two of the aforementioned four families are generalizations of wheels and prisms, whereas the other two are new families. This is joint work with Kapil Pause (CMI), Ajit Diwan (IIT Bombay) and Nishad Kothari.



3. Title : On Distance Magic Graphs: Characterization Challenges
   Speaker : Ravindra Kuber Pawar, PhD Scholar, BITS Goa
   Date, Time & Venue : Wed, Sep 25, 2024, 2:30 PM - SSB 334
   [Abstract]

   A simple, finite graph G is said to be distance magic if its vertices can be labeled in one-to-one manner using the numbers 1, 2, . . . , |V (G)| such that the sum of the labels in the open neighborhood of any given vertex is the same. This constant sum is called the magic constant of the graph. This definition raises two questions: which natural numbers can be magic constants? and which graphs are distance magic? It is believed that among all graphs on the given number of vertices only a fraction of them are distance magic. For example, among all simple graphs of order up to 10, there are only 23 such graphs. Furthermore, a forbidden subgraph characterization for this class of graphs is not possible, making it difficult to characterize them. In this talk, we will address both of the above questions. We will present an algorithm to generate such graphs of a given order with given magic constant. Additionally, we will discuss the current status of the computational complexity involved in determining whether a given graph G is distance magic. Furthermore, we will explore some spectral properties of these graphs and discuss results that relate the distance magic property to the graph’s spectrum. This work is in collaboration with Himadri Mukherjee (BITS Goa), Jay Bagga (BSU, USA) and Tarkeshwar Singh (BITS Goa).



4. Title : Equivalence classes, solitary patterns and cubic graphs
   Speaker : Dogiparthy Veera Venkata Narayana, CSE, IIT-M
   Date, Time & Venue : Thu, Sep 19, 2024, 3:30 PM - SSB 134
   [Abstract]

   Extensive research has been conducted on 2-connected cubic (3-regular) graphs. Petersen (1891) proved that every 2-connected cubic graph has a perfect matching; and Sch¨onberger (1934) showed that each edge in a 2-connected cubic graph is part of some perfect matching. In light of these well-known results, we set out to characterize those 2-connected cubic graphs in which every edge is part of at least two perfect matchings. An edge is referred to as a solitary edge if it belongs to a unique perfect matching. Thus, we can restate our objective as characterizing all 2-connected cubic graphs that do not contain any solitary edges. In the case of 2-connected graphs, there are graphs with n/2 solitary edges, where n is the number of vertices. The problem turns out to be more interesting in the case of 3-connected graphs. A connected graph G with two or more vertices is matching covered if each edge is part of at least one perfect matching. The concept of dependency relationship between edges, in a matching covered graph, was formally introduced and studied by Carvalho, Lucchesi and Murty (1999). Two edges are mutually dependent if every perfect matching containing either of them also contains the other. Clearly, this is an equivalence relation and thus induces a partition of the edge set; each part is refered to as an equivalence class. Observe that n/2 is an upper bound on the cardinality of any equivalence class. We provide a characterization of those matching covered graphs that attain this upper bound. It is worth noting that if any member of an equivalence class is solitary then so is every member; we refer to such an equivalence class as a solitary class. This immediately leads us to the notion of solitary pattern of a matching covered graph — the sequence of cardinalities of its solitary classes in nonincreasing order. For instance, K4 has solitary pattern (2, 2, 2) whereas the Petersen graph has solitary pattern (). Using the theory developed by Carvalho, Lucchesi and Murty, we prove that every 3-connected cubic graph G has one of the following ten solitary patterns: (2, 2, 2), (2, 2, 1), (2, 2), (2, 1, 1), (2, 1), (2), (1, 1, 1), (1, 1), (1) or (); consequently, G has at most six solitary edges. We also provide characterizations of 3-connected cubic graphs that have a fixed solitary pattern except for (1, 1), (1) and (). Finally, we deduce that every 2-connected cubic graph, except for θ,K4,C6 and the bicorn graph, has at most n/2 solitary edges, and equality holds if and only if its solitary edges comprise a solitary class (that is a perfect matching). This is joint work with Kalyani Gohokar (CMI) and Nishad Kothari, and has been submitted to a journal; the manuscript is available here: https://arxiv.org/abs/2409.00534.



5. Title : Bin Packing under Random Order: Breaking the Barrier of 3/2
   Speaker : Karnati Venkata Naga Sreenivasulu, IISc Bangalore
   Date, Time & Venue : Wed, Sep 11, 2024, 3:30 PM - Turing Hall (SSB 334)
   [Abstract]

   Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Kenyon [SODA 96] studied online bin packing under random-order arrival, where the adversary chooses the list of items, but the items arrive one by one according to an arrival order drawn uniformly randomly from the set of all permutations of the items. Kenyons seminal result established an upper bound of 1.5 and a lower bound of 1.08 on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is ~1.15. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. This conjecture has remained one of the major open problems in the area, as highlighted in the recent survey on random-order models by Gupta and Singla [Beyond the Worst-Case Analysis of Algorithms 20]. Recently, Albers et al. [Algorithmica 21] improved the upper bound to 1.25 for the special case when all the item sizes are greater than 1/3, and they improved the lower bound to 1.1. Ayyadevara et al. [ICALP 22] obtained an improved result for the special case when all the item sizes lie in (1/4,1/2], which corresponds to the 3-partition problem. The upper bound of 3/2 for the general case, however, has remained unimproved. In this paper, we make the first progress towards the conjecture, by showing that Best-Fit achieves a random-order ratio of at most 1.5−ε, for a small constant ε>0. Furthermore, we establish an improved lower bound of 1.144 on the random-order ratio of Best-Fit, nearly reaching the conjectured ratio. This is joint work with Anish Hebbar and Arindam Khan, and appeared in SODA 2024.
   
   Bio: KVN Sreenivas is a third-year PhD Student at the Indian Institute of Science Bengaluru (IISc). He completed his Masters by research at IISc and Bachelors from the Indian Institute of Technology Bombay. His research interests mainly lie in approximation and randomized algorithms. He is also an awardee of the Google PhD Fellowship.



6. Title : On the Composition of the Complexity Measures of Boolean Functions
   Speaker : Chandrima Kayal, IMSc Chennai
   Date, Time & Venue : Tue, Sep 10, 2024, 4:00 PM - Turing Hall (SSB 334)
   [Abstract]

   We can compose two Boolean functions f and g to obtain a new function (f o g), but what happens to the complexity measures? Do they compose? Precisely composition of complexity measures asks if M(f o g) = Theta(M(f). M(g)) for some particular complexity measure M. For understanding different complexity measures of Boolean functions this question plays a central role. Following a long line of work there are two big open problems in this area:

   1. Does approximate degree compose?
   2. Does randomized query complexity compose?

   Although these two measures are standard and well-studied, still it is not known if they behave nicely under composition or not. In this study, we have explored two different directions and generalized the existing results, which gives an affirmative answer to both for larger classes of functions. In this talk, we will describe some of the recent results and the related open problems.
   
   Talk is based on the two following works:
   

   1. On the Composition of Randomized Query Complexity and Approximate Degree joint work with Sourav Chakraborty, Rajat Mittal, Manaswi Parashaar, Swagato Sanyal, and Nitin Saurabh.
   2. Approximate degree composition for recursive functions joint work with Sourav Chakraborty, Rajat Mittal, Manaswi Parashaar, and Nitin Saurabh.


7. Title : Fast Algorithms and Data Structures for Regression
   Speaker : Deeksha Adil, ETH Zurich
   Date, Time & Venue : Thu, Aug 29, 2024, 11:00 AM - Turing Hall(SSB 334)
   [Abstract]

   In this talk, I will present state-of-the-art algorithms for $ell_{infty}$-norm regression. These algorithms involve new techniques that combine acceleration algorithms with advanced data structures. These combinations were not known before and are quite delicate to handle. I would start with an overview of the acceleration algorithms and the data structures, and explain how these can be made to work together.



8. Title : Lower Bounds for some Algebraic Models of Computation
   Speaker : Prerona Chatterjee, NISER Bhubaneswar
   Date, Time & Venue : Tue, Aug 27, 2024, 3:00 PM - Online
   [Abstract]

   Cross-listed as a department seminar.
   
   Algebraic circuits and formulas are two of the most natural models for computing polynomials, and proving superpolynomial lower bounds against these models are central questions in the field of complexity theory. A long line of works culminating in the recent breakthrough work of Limaye, Srinivasan and Tavenas proved the first super-polynomial lower bound against constant depth algebraic circuits and formulas. However, proving lower bounds in the general case continues to remain widely open. Another important model for computing polynomials is that of algebraic branching programs, whose power lies in between that of circuits and formulas.
   
   In this talk we will discuss the current state-of-the art for lower bounds against these models of computation in the general as well as some structured settings. I will then describe my recent work with Kush, Saraf and Shpilka (CCC 2024), in greater detail; and conclude with some future research directions that I am excited about, and also my teaching interests.
   
   About the Speaker: Dr. Prerona Chatterjee is currently a visiting faculty member at NISER Bhubaneswar. Before joining NISER, she did her PhD at TIFR Mumbai, and then spent two years as a postdoctoral researcher, first at the Czech Academy of Sciences and then at the Tel Aviv University, Israel. She works in the area of algebraic complexity theory.
   
   Google Meet Link : meet.google.com/hrx-dtmg-weq



9. Title : A new information complexity measure for streaming algorithms
   Speaker : Sumegha Garg, Rutgers University
   Date, Time & Venue : Mon, Aug 26, 2024, 2:30 PM - Turing Hall (SSB 334)
   [Abstract]

   In this talk, we will introduce a new notion of information complexity for one-pass and multi-pass streaming problems, and use it to prove memory lower bounds for the coin problem. In the coin problem, one sees a stream of 𝑛 i.i.d. uniform bits and one would like to compute the majority (or sum) with constant advantage. We show that any constant pass algorithm must use Ω(log 𝑛) bits of memory. This information complexity notion is also useful to prove tight space complexity for the needle problem, which in turn implies tight bounds for the problem of approximating higher frequency moments in a data stream.
   
   Joint works with Mark Braverman, Qian Li, Shuo Wang, David P. Woodruff and Jiapeng Zhang.
   
   Bio: Sumegha Garg is an Assistant Professor in the CS Department at Rutgers University. Before, she was a postdoctoral fellow at Stanford CS, and Rabin postdoctoral fellow in Harvards Theory of Computation group. She completed her PhD in Computer Science at Princeton University, advised by Mark Braverman. She received her bachelor’s degree in CSE from IIT, Delhi. She uses her background in computational complexity theory to answer questions in applied areas such as learning and data streaming. In particular, she is interested in memory lower bounds and theory of fair predictions.



10. Title : Reasoning about Typical Instances through Smoothed analysis
    Speaker : Aravindan Vijayaraghavan, Northwestern University
    Date, Time & Venue : Fri, Aug 2, 2024, 2:00 PM - Turing Hall (SSB 334)
    [Abstract]

    Smoothed analysis is a powerful paradigm in overcoming worst-case intractability for algorithmic problems in many domains including machine learning. In this talk, I will describe a general framework for showing polynomial time smoothed analysis guarantees, and demonstrate its use through applications for some basic problems in machine learning including learning latent variable models, 2-layer neural networks etc., and for problems in quantum entanglement certification. The main technical contribution that enables these smoothed analysis guarantees are new probabilistic techniques to prove lower bounds on the least singular value of random matrix ensembles with highly dependent entries.



11. Title : Range Avoidance via Turan-type Bounds on Hypergraphs
    Speaker : Neha Kuntewar, IIT Madras
    Date, Time & Venue : Fri, Jul 26, 2024, 11:00 AM - Turing Hall (SSB 334)
    [Abstract]



12. Title : Almost-Catalytic Computation
    Speaker : Bhabya Deep Rai, IIT Madras
    Date, Time & Venue : Thu, Jul 25, 2024, 3:00 PM - Turing Hall (SSB 334)
    [Abstract]

    Catalytic Turing Machines (introduced by Buhrman et al (2014)) is a model which has a very small working space, while giving access to another large full space (called catalytic space) with arbitrary contents. This catalytic space can be used for computation, under the condition that the initial contents of this full space get restored at the end. The class CL is the set of languages computed by catalytic Turing machines equipped with O(log n) workspace and polynomial size catalytic space. Buhrman et al (2014) demonstrated the power of the model by proposing efficient algorithms for the reachability problem in this model. However, designing algorithms for the catalytic computation model is still a challenging task. With this view, we relax the original restoration requirement and study cases where we do not need to restore the content of the catalytic tape for all possible contents. If the content of the catalytic tape is w in A (called the catalytic set), then the catalytic Turing machine needs to restore it at the end of the computation, and it is not a requirement when w is not in the catalytic set. We call such machines almost-catalytic Turing machines.
    
    We observe that to design catalytic algorithms for a problem, it suffices to design almost-catalytic algorithms for the problem where the catalytic set is the set of strings of odd weight (PARITY). Towards this, we consider two complexity measures of the set A which are maximized for PARITY. One is the random projection complexity (denoted by R(A)) and the other is the subcube partition complexity (denoted by P(A)). We show that, for all k ge 1, there exists a language A_k subseteq Sigma^* such that any Turing machine that uses space O(n^k) can be simulated by almost catalytic Turing machines that has random projection complexity of m/4 and exponentially large partition complexity. This is in contrast to the catalytic machine model where it is unclear if it can simulate Turing machines that uses even omega(log n) space. We further show improved simulations on these complexity parameters if we are simulating Turing machines that run in O(log^k n) space instead of O(n^k) space. Our main technical idea is that of using special logspace decodable codes to design almost catalytic algorithms. Finally, we explore limitations of a direct simulation via this approach, by demonstrating connections to parameters of linear codes. Enroute our study, we also demonstrate the power of an extra alphabet in the catalytic set by demonstrating that with an extra alphabet, the CL machines can simulate any polynomial space Turing machine as well.



13. Title : Local Algorithms for Variants of Graph Coloring
    Speaker : Keshav Tiwari, IIT Madras
    Date, Time & Venue : Thu, Jul 4, 2024, 2:30 PM - ALC Conference Room
    [Abstract]

    Cross Listed as an MS Seminar.
    
    Graph coloring is a fundamental algorithm problem in computer science. Given a graph G, the algorithmic task is to assign a color to each vertex such that no two adjacent vertices share the same color. The minimum number of colors used to perform this task is called the chromatic number of the graph. Where it is trivial to color the graph with n colors, it is NP-Hard to find the chromatic number of a graph. And the decision problem of determining whether for a given k, a graph G admits a k coloring is NP-Complete.
    
    Classical models and algorithms assume the ability to read the entire input and produce the entire output. However, for extremely large inputs, such as graphs with millions or billions of nodes, this becomes impractical due to excessive time and space requirements which makes it impractical for a single processor to process. Such situations can be dealt with, alternative computation models such as parallel and distributed models of computing, or requiring that the output is only approximate or other weaker guarantees. In this work we study, Local Computation Algorithms (LCAs). LCAs only read a small portion of the input and produce a small portion of the output. For instance, for graph coloring problem, given a vertex query in a graph, an LCA will read a limited number of vertices and output the color of the queried vertex according to a specific coloring scheme.
    
    In this study, we look into weaker notions of coloring. One such notion is weak coloring, where all vertices needs at least a minimum number of neighbors to be of different colors, and other notion is partial coloring, where a large fraction of vertices will have all their neighbors of different colors and a combination of weak and partial colorings. A graph is α-partially colored if at least (1 − α) fraction of vertices have all their neighbors of different colors, and a graph is weakly 2-colored if each vertex is colored with one of the two given colors and has a neighbor of different color. We have developed LCAs, that needs time sublinear in input size for weak 2-coloring problem, and takes constant time for α-partial weak 2-coloring problem for bounded maximum degree graphs. Also we have developed LCAs that take constant time for weak 2-coloring and α-partial coloring of hyperfinite graphs.
    
    



14. Title : On Succinct Data Structures for Certain Generalisations of Interval Graphs
    Speaker : Girish Balakrishnan, IIT Madras
    Date, Time & Venue : Thu, Jul 4, 2024, 11:30 AM - ALC Room
    [Abstract]

    Crosslisted as a PhD Seminar.
    
    In this work, we explore generalizations of interval graphs based on three different graph parameters, namely, boxicity d > 0, interval number t > 0, and vertex leafage k > 0 by designing succinct data structures for them. A data structure for graphs in the class of graphs mathcal{G} is called succinct if it takes log |mathcal{G}| + o(log |mathcal{G}|) bits of space. The graph parameters, boxicity, and interval number are defined for general graphs, whereas the graph parameters vertex leafage and leafage are defined for chordal graphs alone. These parameters let us define graph classes with a laminar structure with interval graphs as the base class. Utilizing this laminar structure we design data structure for the class of graphs with larger values of these parameters using the succinct data structure for the base class. For c > 0, a unit increase in any of the three parameters adds only n^{cn} number of graphs. So such a data structure design technique gives a space-efficient representation only when the parameters are bounded, since c depends on the parameters and the parameters can be O(n). Further, we prove that under these conditions the representations are succinct. We show that, for graph classes defined based on boxicity and interval number, the base class is interval graphs. However, for a succinct data structure for the graph class based on vertex leafage, a base class with vertex leafage of two and unbounded leafage is better suited than interval graphs that have both vertex leafage and leafage equal to two. It turns out that such a class of graphs is well-studied and is called path graphs. We present the design of succinct data structures for the following generalizations of interval graphs based on these three parameters:
    
    - path graphs, which is a strict super-class of interval graphs and a strict sub-class of chordal graphs,
    - graphs with bounded boxicity d > 0 and graphs with bounded interval number t > 0, and
    - chordal graphs with bounded vertex leafage k > 0 and unbounded leafage.
    
    The succinct data structures for graphs with bounded boxicity and interval number are obtained using the succinct data structure for interval graphs given by Acan et al. (LNTCS, volume 11646). In the case of chordal graphs with bounded vertex leafage, the succinct data structure is obtained using the succinct data structure for path graphs. The graph classes considered in this work are all factorial speed hereditary properties with simple structural characterizations that we obtain as part of our constructive lower bound argument for the cardinality of these graph classes. Our lower bound arguments, based on the partial coloring scheme introduced by Acan et al. (Theor. Comput. Sci. 2022) demonstrate that using this scheme we not only obtain the lower bound of the cardinality of the graph class under consideration but also its structural characterisation. As per Lozin 2018, the structural characterization of factorial speed hereditary properties is an open problem. We raise the question: Does boxicity structurally characterize the factorial speed hereditary property? We conclude that the answer is not immediately evident motivating further study.
    
    Web Conference Link : https://meet.google.com/wco-vqpu-zia



15. Title : Using a Geometric Lens to find k Disjoint Shortest Paths
    Speaker : Matthias Bentert, University of Bergen
    Date, Time & Venue : Wed, Mar 13, 2024, 10:00 AM - SSB 334
    [Abstract]

    Given an undirected graph and k pairs of terminal vertices (s_i, t_i), the k-Disjoint Shortest Paths (k-DSP) problem asks whether there are k pairwise vertex-disjoint paths P_i where P_i is a shortest s_i-t_i-path. Recently, Lochet [SODA ’21] provided an algorithm that solves k-DSP in n O(k^5^k) time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved O(n^(16k·k!))-time algorithm based on a novel geometric view on this problem. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.
    
    This is joint work with André Nichterlein, Malte Renken, and Philipp Zschoche.
    
    Speaker Bio: Matthias is a postdoctoral fellow at University of Bergen, Norway. His work is mainly in the area of Parameterized Algorithms & Complexity.



16. Title : Proportional Allocations of Indivisible resources: Insights via Matchings
    Speaker : Vishwa Prakash, Chennai Mathematical Institute
    Date, Time & Venue : Tue, Feb 6, 2024, 2:30 PM - CS15
    [Abstract]

    The problem of fair allocation of indivisible resources arises in various scenarios such as dividing chores among roommates, inheritance among family members, allocating CPU time slots to jobs, and so on. The task is to allocate a set of items fairly among a set of agents. An allocation is proportionally fair if all agents believe that they have received their fair share of the value according to how they value the items. Each agent only specifies the ranking of the items from best to worst and does not disclose their values.
    
    In this presentation, I will introduce a matching-based approach to finding an approximately proportional (WSD-PROP1) allocation in polynomial time. This approach also provides a complete characterization of these allocations as extreme points of a perfect matching polytope. Using this polytope, we can optimize any linear objective function over all such allocations. For example, this allows us to find a min-cost WSD-PROP1 allocation of goods or the most efficient WSD-PROP1 allocation of chores. In addition to fairness, we also guarantee economic efficiency, specifically Pareto Optimality.
    
    I will also discuss randomized fairness notions, such as Best-of-Both-Worlds (BoBW) fairness. Using our characterization, we present a polynomial-time algorithm to compute Ex-ante envy-free (WSD-EF) and Ex-post WSD-PROP1 allocations for both goods and chores.
    
    This presentation is based on joint work with my PhD advisor, Prajakta Nimbhorkar, titled "Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings", which will be presented at AAMAS 2024.



17. Title : Broadcast Domination and Multipacking in (di)graphs
    Speaker : Florent Foucaud, Clermont Auvergne University, France
    Date, Time & Venue : Thu, Jan 18, 2024, 11:00 AM - Turing Hall (SSB334)
    [Abstract]

    A dominating broadcast of a (di)graph $G$ is an assignment $f$ of non-negative integer weights to the vertices of $G$, such that each vertex $x$ with $f(x)=0$ is at (directed) distance at most $r$ from some vertex $y$ with $f(y)geq r$. The broadcast domination number of graph $G$ is the smallest cost (i.e. sum of all weights) of a dominating broadcast of $G$. This concept models a natural covering problem in telecommunications, where the graph represents a network and $f(x)$ is the emission power of a radio station; all nodes of the network must be covered by some radio station. Its nice feature is that, as shown by Heggernes and Lokshtanov in 2006, an optimal dominating broadcast can be computed in polynomial time (provided the graph is undirected), unlike most standard covering problems. We first discuss the integrality gap (for undirected graphs) between the optimum solutions of Broadcast Domination and its recently introduced dual problem, called Multipacking, for general graphs and for chordal graphs. Then, we focus on algorithmic questions. It turns out that both problems are NP-hard on directed graphs, and they are also hard in the realm of parameterized complexity, for the parameter solution cost. We present some polynomial-time and parameterized algorithms for special classes of digraphs.
    
    This is joint work with three groups of colleagues: Laurent Beaudou/Richard C. Brewster (http://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p086.pdf), Sandip Das/Joydeep Mukherjee/Sk Samim Islam (https://link.springer.com/chapter/10.1007/978-3-031-25211-2_23) and Benjamin Gras/Anthony Perez/Florian Sikora (https://link.springer.com/article/10.1007/s00453-021-00828-5).
    
    Brief Bio: Florent is an associate professor (maître de conférences) at the Université Clermont Auvergne. His research interests are in graph algorithms and graph theory.



18. Title : Fair Division via Quantile Shares
    Speaker : Vishnu V. Narayan,
    Date, Time & Venue : Wed, Dec 27, 2023, 11:00 AM - Turing Hall (SSB 334)
    [Abstract]

    We consider the problem of fair division, where a set of indivisible goods should be distributed fairly among a set of agents with combinatorial valuations. Broadly, there are two categories of fairness notions in the literature: envy-based fairness and share-based fairness. A fairness notion is universally feasible if it admits a fair allocation for every profile of monotone valuations. While some well-studied envy-based notions (such as EF1) are universally feasible, no known non-trivial share based notion (and no constant approximation of any of them) is feasible for all monotone valuations.
    
    We propose a novel share notion (the quantile share) where an agent assesses the fairness of a bundle by comparing it to her valuation in a random allocation. Our main result establishes a strong connection between the feasibility of quantile shares and the classical Erdős Matching Conjecture. Specifically, we show that if a version of this conjecture is true, then the 1/2e-quantile share is universally feasible. Furthermore, we provide unconditional feasibility results for additive, unit-demand and matroid-rank valuations for constant values of q. Finally, we discuss the implications of our results for other share notions.
    
    Joint work with Y. Babichenko, M. Feldman, and R. Holzman.
    
    
    
    Brief Bio: Vishnu V. Narayan is a postdoctoral fellow hosted by Michal Feldman at Tel Aviv University. His main research focus is on the fair division of indivisible items. Additionally, he is broadly interested in problems in the intersections of algorithms, combinatorics, and game theory. Earlier, he completed his Ph.D. in Computer Science at McGill University under the supervision of Adrian Vetta, and his M.Math. in Combinatorics and Optimization at the University of Waterloo with Joseph Cheriyan.



19. Title : Balance in Chaos
    Speaker : Krithika Ramaswamy, IIT Madras
    Date, Time & Venue : Fri, Jun 23, 2023, 4:00 PM - CSB 15
    [Abstract]

    Ramsey Theory is a branch of Combinatorics that deals with patterns in large arbitrary structures. In the context of edge-colored graphs where each edge is colored with one color from a finite set of colors, a fundamental problem in the area is concerned with the existence of monochromatic subgraphs (all edges have the same color) of a specific type. In this talk, we will discuss questions in a subarea of Ramsey Theory known as Zero-Sum Ramsey Theory where the interest is in showing the existence of and/or finding balanced subgraphs instead of monochromatic subgraphs, where by a balanced subgraph we mean one which has an equal number of edges of each color. Specifically, we will discuss the complexity of finding balanced connected subgraphs, trees and paths in bicolored graphs. We give fixed-parameter tractability results using color coding, representative sets and reductions to detecting multilinear monomials in polynomials. En route, we give combinatorial results on the existence of small balanced connected subgraphs, trees and paths. This is a joint work with P. S. Ardra (IIT Palakkad), Saket Saurabh (Institute of Mathematical Sciences and University of Bergen) and Roohani Sharma (Max Planck Institute for Informatics).



20. Title : Hierarchical Fractionally Intersecting families
    Speaker : Niranjan Balachandran, IIT Bombay
    Date, Time & Venue : Wed, Jun 7, 2023, 4:00 PM - CSB 15
    [Abstract]

    Suppose $Lsubsetmathbb{N}_0$. A family $mathcal{F}subsetmathcal{P}([n])$ is said to be $L$-intersecting if for distinct $A,B$ in $mathcal{F}$ we have $|Acap B|in L$. The problem of determining the size of a maximum $L$-intersecting family is a well-studied problem in extremal combinatorics which draws on ideas from several diverse toolkits, including the well-known Linear Algebra method.
    
    A more recent variant describes what one may call a fractional intersecting family when the set $L$ consists of proper fractions of the form $0



21. Title : Foundations of Lattice-based Cryptography
    Speaker : Rajendra Kumar,, Weizmann Institute of Science, Israel
    Date, Time & Venue : Mon, Mar 20, 2023, 3:00 PM - MR1
    [Abstract]

    Public key cryptography is essential for internet security. RSA and Diffie-Hellman are the most widely used public-key cryptosystems for internet traffic. However, recent progress in building quantum computers threatens RSA and Diffie-Hellman security, as they are vulnerable to quantum adversaries. To address this, organizations like the National Institute of Standards and Technology (NIST) and the European Telecommunications Standards Institute (ETSI) have started standardizing and deploying cryptosystems that are secure against quantum attacks. Recently, NIST has chosen Kyber and Dilithium, lattice-based candidates, as primary algorithms for security against quantum adversaries. The security of these cryptosystems crucially relies on the assumption that the best-known algorithms for the lattice problems cannot be significantly improved. In this talk, I will discuss the connections between the security of lattice-based cryptosystems and the hardness of lattice problems. I will talk about classical and quantum algorithms for lattice problems. I will also discuss the works on the fine-grained security of lattice-based Crypto.



22. Title : Breaking folklore barrier for Maximal k-edge-connected subgraph partition
    Speaker : Chaitanya Nalam, University of Michigan
    Date, Time & Venue : Mon, Mar 6, 2023, 4:00 PM - MR1
    [Abstract]

    In the problem of maximal k-edge-connected partition, given a weighted graph G=(V, E) with n vertices and m edges, we need to find the unique partition V1,V2,... of the vertex set V such that each induced subgraph G[V_i] has mincut at least k. This classical problem has been studied since the 70s. A folklore algorithm takes ilde{O}(mn) time by simply computing the minimum cut recursively. All previous efforts [Henzinger et.al SODA 15, Chechik et al SODA 17, Forster et al SODA 20] can speed up this folklore algorithm only in unweighted or when k is small enough. In this talk, I will explain a new algorithm that breaks this folklore barrier in weighted graphs. It takes ilde{O}(mn^{0.8}) time, which is, in particular, independent from k. The key technique is to localize the famous Karger s random contraction technique. Based on joint work (https://arxiv.org/abs/2302.02290) with Thatchaphol Saranurak.



23. Title : On p-centered colorings of grids
    Speaker : Mathew Francis, ISI Chennai
    Date, Time & Venue : Tue, Feb 28, 2023, 3:00 PM - CS25
    [Abstract]

    Given a graph G and a positive integer p, a p-centered coloring φ of G is a coloring of the vertices of G using a set of colors Q such that for every connected subgraph H of G, either there exists i∈ Q such that |φ-1(i)∩ V(H)|=1 or |φ(V(H))|>p or in other words, every connected subgraph of G either contains a vertex with a unique color or contains more than p colors.
    
    The notion of p-centered colorings of graphs was introduced by Nešetřil and Ossona de Mendez [Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, 27(6):1022–1041, 2006] in the course of their development of the theory of "structurally sparse" graph classes. Dębski, Felsner, Micek and Schröder [Improved bounds for centered colorings, SODA 2020] showed using entropy compression that graphs of bounded degree have p-centered colorings using just O(p) colors: they showed that for any positive integer p, every graph G having maximum degree Δ has a p-centered coloring using O(Δ2-1/p p) colors. However, their technique does not provide an explicit construction of a p-centered coloring using O(p) colors for graphs of bounded maximum degree, and they remark that an explicit construction of such a coloring is not known even for the planar grid. In this paper, we give a simple and direct construction of a p-centered coloring of the planar grid using O(p) colors.
    
    A preprint of the work can be found at https://arxiv.org/abs/2207.11496



24. Title : Fast Multivariate Multipoint Evaluation over Finite Fields
    Speaker : Dr. Sumanta Ghosh, Caltech, USA
    Date, Time & Venue : Thu, Feb 16, 2023, 2:30 PM - CS15
    [Abstract]

    Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. The straightforward algorithm for this problem is to iteratively evaluate the input polynomial at each input point. The question of obtaining faster-than-naive  (ideally, linear time)  algorithms or this problem is a natural and fundamental question in computer algebra. Besides, fast algorithms for this problem are closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. Nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck. However, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans in 2008 and Kedlaya-Umans in 2011 gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables n is at most d^{o(1)} where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case as an open problem. In this talk, we present two new algorithms for this problem. The first one is a nearly linear time (algebraic) algorithm for not-too-large fields of small characteristics. For the large variable case, this is the first nearly linear time algorithm for this problem over any large enough field. The second gives a nearly linear time (non-algebraic) algorithm over all finite fields. We also discuss an application to data structure upper bound of polynomial evaluation and an application to rigidity upper bound on Vandermonde matrices. The talk is based on joint work with Vishwas Bhargava, Zeyu Guo, Mrinal Kumar, Chandra Kanta Mohapatra, and Chris Umans.



25. Title : Complexity of Geometric Constraint Systems
    Speaker : Meera Sitharam, Professor of Computer Science and Affiliate Professor of Mathematics, University of Florida
    Date, Time & Venue : Mon, Feb 6, 2023, 4:00 PM - Aryabhatta Hall
    [Abstract]

    The talk will consist of two parts, both on graphs underlying geometric constraint systems over discrete sets of primitive geometries that underlie diverse application domains from soft matter modeling, kinematics, matrix completion and machine learning.
    
    PART I: We settle a decade-old conjecture and completely characterize graphs G and their non-edges f such that across all 3-dimensional Euclidean realizations of a given G-linkage, f attains lengths in a single interval. More precisely, given any assignment of (Euclidean) edge-lengths for G, f attains a single interval of length values across all 3-dimensional point configurations for which the pairwise distances agree with the given edge lengths. Although related to the minor-closed class of so-called 3-flattenable graphs, this class is not minor closed, has no obvious well quasi-ordering, and there are infinitely many minimal graphs-nonedge pairs - w.r.t. edge contractions - in the complement class. Our characterization overcomes these obstacles, is based on the 2 forbidden minors of the class of 3-flattenable graphs, and contributes to the theory of Cayley configurations used for analyzing distance-constrained configuration spaces in a range of application domains. Based on this result, generalizations to higher dimensions and efficient algorithmic characterizations will be discussed.
    
    PART II: We discuss 3 problems that connect the 150 year old Maxwellian quest to combinatorially characterize graph rigidity, to derandomization of determinantal identity testing, and parametrized complexity of (geometric constraint) graph decomposition.



26. Title : On the border complexity of binomials (& more)
    Speaker : Pranjal Dutta, NUS Singapore
    Date, Time & Venue : Wed, Dec 21, 2022, 2:30 PM - SSB MR 1
    [Abstract]

    The border complexity of polynomials plays an integral role in GCT (Geometric complexity theory) to approach P != NP. It tries to formalize the notion of approximating a polynomial via limits (Burgisser FOCS 01). This raises whether VP ?= VP; as the approximation involves exponential precision that may not be efficiently simulable. In (ToCT 20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials, which has a small border-SUM[2]-PROD-SUM circuit (or binomial complexity). In this talk, we will discuss the converse of Kumar s result, which ramifies in a surprising new formulation of Waring rank and border Waring rank. We will further discuss that the border of bounded top-fanin depth-3 circuits (border-Σ^[k]ΠΣ for constant k) is relatively easy– it can be computed by a polynomial-size algebraic branching program (ABP). Then, we will discuss several exponential separations between related polynomials contained in the border. This talk is mostly based on three works -- (1) Demystifying the border of depth-3 algebraic circuits (FOCS 21, pdf) with Prateek Dwivedi (IIT Kanpur) and Nitin Saxena (IIT Kanpur), (2) Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits (FOCS 22, pdf), with Nitin Saxena (IIT Kanpur), and (3) Border complexity via elementary symmetric polynomials (preprint, pdf) with Fulvio Gesmundo (Saarland University), Christian Ikenmeyer (University of Warwick), Gorav Jindal (MPI, Saarbrücken), and Vladimir Lysikov (QMATH, University of Copenhagen).



27. Title : LP-Duality Theory and the Cores of Games
    Speaker : Vijay Vazirani, US Irvine
    Date, Time & Venue : Mon, Dec 12, 2022, 11:00 AM - CS15
    [Abstract]

    The core is a quintessential solution concept in cooperative game theory and LP-duality theory has played a central role in its study, right from its early days to the present time. The classic 1971 paper of Shapley and Shubik showed the ``right' way of exploiting this theory --- in the context of characterizing the core of the assignment game.
    
    The LP-relaxation of this game has the following key property: the polytope defined by its constraints has integral vertices; in this case, they are matchings in the underlying graph. Similar characterizations for several basic combinatorial optimization games followed; throughout, this property was established by showing that the underlying linear system is totally unimodular (TUM).
    
    We will first exploit TUM further via a very general formulation due to Hoffman and Kruskal (1956). The way to take this methodology to its logical next step is to use total dual integrality (TDI). In the process, we address new classes of games which have their origins in two major theories within combinatorial optimization, namely perfect graphs and polymatroids.
    
    Whereas the core of the assignment game is always non-empty, that of the general graph matching game can be empty. We show how to salvage the situation --- again using LP-duality in a fundamental way.
    
    Based on: Link 1, Link 2, Link 3.
    
    BIO: Vijay Vazirani got his undergraduate degree from MIT in 1979 and his PhD from the University of California, Berkeley in 1983. He is currently a Distinguished Professor at the University of California, Irvine. He has made fundamental contributions to several areas of the theory of algorithms, including algorithmic matching theory, approximation algorithms and algorithmic game theory, as well as complexity theory. His current work is on algorithms for matching markets; his co-edited book on this topic will be published by Cambridge University Press in March 2023. Here is a flyer:https://www.ics.uci.edu/~vazirani/flyer.pdf He is an ACM Fellow, a Guggenheim Fellow and the recipient of the 2022 INFORMS John von Neumann Theory Prize.



28. Title : Cycle-extendability versus planarity
    Speaker : Nishad Kothari, IIT Madras
    Date, Time & Venue : Tue, Oct 18, 2022, 3:00 PM - CSB 34
    [Abstract]

    For most problems pertaining to the study of perfect matchings, one may restrict attention to the class of matching covered graphs (i.e., connected graphs with the property that each edge belongs to some perfect matching). Such graphs are also known as 1-extendable graphs - since each edge extends to a perfect matching. In the same spirit, we say that a matching covered graph G is cycle-extendable if (either) perfect matching of any even cycle Q extends to a perfect matching (of G) - which is equivalent to saying that G-V(Q) has a perfect matching for each even cycle Q.
    
    There is extensive literature on the study of matching covered graphs, and one of the most important ingredients is an ear decomposition theory (similar to ear decomposition theory of 2-connected graphs). From this vantage point, a matching covered graph G is cycle-extendable if and only if each even cycle may be extended to an ear decomposition of G.
    
    As of now, there is no known NP characterization of cycle-extendable graphs (in general). Recently (July 2022), Zhang, Wang, Yuan, Ng and Cheng obtained such a characterization for cycle-extendable claw-free graphs (where claw-free means that there is no induced sub- graph isomorphic to K_{1,3}).
    
    We are currently working on obtaining NP characterizations of (i) cubic graphs and (ii) planar graphs that are cycle-extendable. In my recent talk (August 2022), I discussed the cubic bipartite case and its resolution. In this talk, I will be discussing the planar case — for which we have partial results (as of now), and a conjecture (that we are working on). This is on-going and joint work with Rajat Adak (IIT-H), Marcelo H. de Carvalho (UFMS Brazil), Ajit Diwan (IIT-B) and Kapil Pause (CMI). I will present the necessary background, and describe our aforementioned results. The talk will be self-contained.
    
    Note:This talk is a follow-up to my previous t-meet talk (30th August, 2022). If you missed that, or if you would like to refresh your memory, here is a handout to help you.



29. Title : PAC Learning on a Quantum Computer : A New ERM Algorithm and Sample Complexity Bounds
    Speaker : Arun Padakandla, Univ. of Tennessee at Knoxville
    Date, Time & Venue : Thu, Sep 15, 2022, 2:15 PM - Aryabhatta Hall
    [Abstract]

    In this talk, I will address a quantum analogue of the fundamental classical PAC learning problem. In contrast to a conventional computer, data is encoded on a quantum computer by modifying specific attributes of sub-atomic particles. For example, the axis of spin of an electron or the plane of polarization of a photon can be modified to encode data. The behavior of these particles is governed by the unique laws of quantum mechanics. In particular, extracting or learning from data encoded on sub-atomic particles is via quantum measurements. We are thus led to a problem of PAC learning Quantum Measurement Classes. I will present a new Quantum Empirical Risk minimization algorithm that respects quantum non-commutativity. Analyzing its complexity, I present upper bounds on the sample complexity of learning measurement classes. In the latter part of my talk, I will provide an overview of some of my findings in classical information theory.
    
    Speaker Bio : Arun Padakandla holds a PhD from the Univ. of Michigan and held a postdoctoral fellowship with the NSF Center for Science of Information at Purdue University. He is currently on the faculty at the Univ. of Tennessee at Knoxville. His interests are in quantum computation, quantum algorithms and quantum information.



30. Title : Cycle-extendable Graphs
    Speaker : Nishad Kothari, IIT Madras
    Date, Time & Venue : Tue, Aug 30, 2022, 3:00 PM - CSB34
    [Abstract]

    For most problems pertaining to the study of perfect matchings, one may restrict attention to the class of ‘matching covered graphs’ (i.e., connected graphs with the property that each edge belongs to some perfect matching). Such graphs are also known as 1-extendable graphs — since each edge extends to a perfect matching. In the same spirit, we say that a matching covered graph G is cycle-extendable if (either) perfect matching of any even cycle Q extends to a perfect matching (of G) — which is equivalent to saying that G − V (Q) has a perfect matching for each even cycle Q.
    
    There is extensive literature on the study of matching covered graphs, and one of the most important ingredients is an ear decomposition theory (similar to ear decomposition theory of 2-connected graphs). From this vantage point, a matching covered graph G is cycle-extendable if and only if each even cycle may be extended to an ear decomposition of G.
    
    As of now, there is no known NP characterization of cycle-extendable graphs (in general). Recently (July 2022), Zhang, Wang, Yuan, Ng and Cheng obtained such a characterization for cycle-extendable claw-free graphs (where claw-free means that there is no induced sub- graph isomorphic to K1,3).
    
    We are currently working on obtaining NP characterizations of (i) cubic graphs and (ii) planar graphs that are cycle-extendable, and we have resolved the cubic bipartite case - which I will be discussing in this talk. It turns out that a cubic bipartite graph is cycle- extendable if and only if it is obtained from repeated ‘splicings’ of cubic C4 (i.e., C4 with two additional nonadjacent edges) and K3,3.
    
    This is on-going and joint work with Rajat Adak (IIT-H), Marcelo H. de Carvalho (UFMS Brazil), Ajit Diwan (IIT-B) and Kapil Pause (CMI).
    
    I will present the necessary background, and describe our aforementioned results. The talk will be self-contained.



31. Title : Fast multivariate multipoint evaluation over finite fields
    Speaker : Mrinal Kumar, IIT Bombay
    Date, Time & Venue : Fri, Aug 19, 2022, 11:00 AM - Aryabhatta Hall
    [Abstract]

    Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. A straightforward algorithm for this problem is to just iteratively evaluate the polynomial at each of the inputs. The question of obtaining faster-than-naive (and ideally, close to linear time) algorithms for this problem is a natural and fundamental question in computational algebra. In addition to its own inherent interest, faster algorithms for multipoint evaluation are closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition.
    
    Nearly linear time algorithms have been known for the univariate multipoint evaluation for close to five decades due to a work of Borodin and Moenck but fast algorithms for the multivariate (or, even bivariate) version have been much harder to come by. In a significant improvement to the state of art for this problem in 2008, Umans and Kedlaya-Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables is at most d^{o(1)} where d is the degree of the input polynomial in every variable.
    
    In this talk, we will discuss two new algorithms for this problem: the first is a simple and natural algebraic algorithm over not-too-large fields of small characteristic and the second is a (non-algebraic) algorithm for this problem over all finite fields. Both these algorithms run in nearly linear time even when the number of variables is large. We will also discuss an application to an upper bound for data structures for polynomial evaluation and to an upper bound on the rigidity of Vandermonde matrices.
    
    The talk is based on joint works with Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Chandra Kanta Mohapatra and Chris Umans.



32. Title : Power of Programs over Monoids : Towards the PLP Conjecture
    Speaker : Janani Sundaresan, Rutgers University
    Date, Time & Venue : Tue, Mar 2, 2021, 4:00 PM - https://meet.google.com/moh-pbtq-wyg
    [Abstract]

    Programs over monoids can be viewed as a series of if-else statements or instructions which query the input indices and output an element over a monoid. Programs either accept or reject based on the final output. Monoids have been an effective tool in characterizing computational resources. For example, a language (equivalently every family of Boolean functions) can be computed by constant depth polynomial-size circuits if and only if it can be computed by a polynomial length program over an aperiodic monoid.
    In a more general setting, how does the algebraic structure of the monoid affect the computational power of programs over it? A monoid is called universal if for every language, there exists a program computing it over the monoid. A monoid is said to have the polynomial length property if any program over it can be reduced to polynomial length without changing the language accepted. The PLP conjecture is the following powerful dichotomy - any monoid is universal if and only if it does not have the polynomial length property.
    The conjecture has been confirmed for the case when the monoids are groups. It is still open for other kinds of monoids. A particularly appealing structure is that of aperiodic monoids. An important aperiodic monoid that captures the difficulty of the problem is a monoid called the BA2. We show the conjecture for the case of BA2 when the program has a polynomial sized witness for the zero set. This talk will present the development of a graph-theoretic representation that not only settles the above case but also can be a potential tool for the general form of the conjecture as well. We also extend known results about the computational power of the BA2 monoid while computing PARITY.
    
    This is joint work with Manasi Kulkarni and Jayalal Sarma. The work has been accepted for presentation at LATA 2021.



33. Title : More for less: The delights of divide and conquer algorithms
    Speaker : C. Pandu Rangan, IIT Madras
    Date, Time & Venue : Tue, Nov 24, 2020, 4:00 PM - Google Meet
    [Abstract]

    Algorithmic problem solving differs from mathematical problem solving through its focus on efficiency. While we may be able to solve a problem in various ways, the major concern here is on designing efficient solutions. Over the past few decades, several clever paradigms have evolved but mindless application of these ideas may not result in good solutions. There is an art, there are subtleties and nuances and that is why, when an idea is applied with insight you get the aha moment!!. Let us enjoy one such moment during this meet!!
    
    This talk is dedicated to super heroes of our department who through their amazing talent and efforts, scaled new peaks in professional achievements. Dr. Jayalal the best teacher award winner, Prof Krishna Nandivada for IBM award, Dr.Shweta Agrawal for Swarna Jayanthi award. (my advanced apologies for those who are missed out by me..it is definitely for all the achievers..) . There is another exciting thing happening in our dept , consistently for the past few years, starting from the days of the headship of Prof PSK. a good wave of new faculty members have joined and enriched our dept. This is a welcome talk to the recent arrivals!!!!!!



34. Title : A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization
    Speaker : Pranjal Dutta, CMI & IIT Kanpur
    Date, Time & Venue : Tue, Sep 22, 2020, 4:00 PM - Google Meet
    [Abstract]

    For a polynomial f, we study the sum-of-squares representation (SOS), i.e.f = c_1*f_1^2 + ... + c_s*f_s^2, where c_i are field elements and the f_i are polynomials. The size of the representation is the number of monomials that appear across the polynomials f_i. Its minimum is the support-sum S(f) of f.
    
    For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of a full-support univariate polynomial, f of degree d is S(f) >= d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) >= d^{0.5+varepsilon(d)}, for a sub-constant function varepsilon(d)>omega(sqrt{loglog d/log d}), implies that VP is different from VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Theta(d).
    
    We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P.
    
    This is based on joint work with Prof. Nitin Saxena (CSE, IIT Kanpur) and Prof. Thomas Thierauf (Aalen University). The full version of the paper is available here.



35. Title : Algorithms and lower bounds for de-Morgan formulas of low-communication leaf gates
    Speaker : Sajin Koroth, Simon Fraser University
    Date, Time & Venue : Tue, Sep 15, 2020, 4:00 PM - Google Meet
    [Abstract]

    Computational problems with an “efficient” parallel algorithms are an important computational class in the theory and practice of algorithms. Although it is widely believed that there are inherently sequential problems (class P of poly-time solvable problems) that do not have efficient parallel algorithms (denoted by class NC^1), we do not know of any such formal separations. Circuit complexity models computation as familiar Boolean logic circuits and efficient parallel algorithms are modeled by a class of circuits known as de-Morgan formulas. Settling the P vs NC^1 problems amounts to proving super polynomial-size lower bounds for de-Morgan formulas for a function in P. But as P vs NC^1 is a hard problem with a long history and meta-mathematical barriers to proving such a separation, the best size lower bound we know for de-Morgan formulas for a function in P is only cubic. The cubic lower bound is a celebrated result from the 90’s due to Hastad and is for a function in P known as the Andreev function. A natural approach to making progress in circuit complexity is to augment the circuit model for which we can prove lower bounds with the function that is hard for the said circuit model. In this talk, we focus on a natural generalization of de-Morgan formulas in which the Andreev function is easy to compute. In de-Morgan formulas, the circuit has access to the individual bits of the input. In our generalization, the circuit can access any Boolean function of the input as long the function has low communication complexity. Naturally, this is equivalent to giving access to a “pre-processed” input where pre-processing is done with functions of low communication complexity. Our model generalizes various earlier works where the pre-processing functions are bipartite (a function that only looks at one half of the input, motivated from combinatorics), parities, etc as all of these functions have low communication complexity. We prove an almost quadratic lower bound for a natural function (generalized inner product) and prove associated results like pseudo-random generators and SAT algorithms for this model. An interesting feature of our result is the reliance on a famous result from quantum query complexity due to Reichardt (which was also the basis for the lower bound on circuits with bipartite formulas at the bottom due to Avishay Tal), and we do not know of a classical way to prove this result. The focus of the talk would be on the result from quantum query complexity and its use to prove the nearly quadratic lower bound.
    
    Joint work with Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira. The full version of the paper available at ECCC-TR-2020-018.



36. Title : The optimal analysis for approximating boolean Max-2CSP (and beyond) in the streaming model
    Speaker : Chi-Ning Chou, Harvard University
    Date, Time & Venue : Wed, Sep 9, 2020, 5:30 PM - Online
    [Abstract]

    TBA



37. Title : Polynomial Data Structure Lower Bounds in the Group Model
    Speaker : Alexander Golovnev, Georgetown University
    Date, Time & Venue : Fri, Sep 4, 2020, 5:30 PM - Online
    [Abstract]

    Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80’s. We prove a polynomial (n^Omega(1)) lower bound for an explicit range counting problem of n^3 convex polygons in R^2 (each with n^{O~(1)} facets/semialgebraic complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing—in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k = n^{1-delta}). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.



38. Title : On the Mystery of Negations in Circuits : Structure vs Power
    Speaker : Sai Jayasurya, IIT Madras -> Google
    Date, Time & Venue : Thu, Aug 20, 2020, 4:00 PM - Google Meet
    [Abstract]

    n this talk, we will present a quick introduction to the role that negation gates in play in the computation of Boolean functions. Specifically, we will be interested in exploring how the way negation gates are connected affects the computational power of circuits. We will particularly explore the case when the negations are independent with each other and prove limitations of such negation gates. We will look into a measure of power of negations in a circuit called decrease capacity and relate it to a measure of functions called decrease. We will define a parameter of Boolean functions called "thickness" and show that it indicates how negations can be used to reduce the depth of circuits computing the function.



39. Title : Power of Decision Trees with Monotone Queries
    Speaker : Prashanth Amireddy, IIT Madras -> Flipkart
    Date, Time & Venue : Tue, Aug 18, 2020, 4:00 PM - Google Meet
    [Abstract]

    The Decision Tree (DT) model of computation of a Boolean function f: {0,1}^n to {0,1} is a binary tree that allows a bit of the input at each internal node of the tree. It branches at each internal node of the tree depending on the value of the bit queried and finally outputs the label of the leaf reached. The minimum height, number of leaves of the decision tree for a function in the worst case are very well-studied parameters of this model.
    
    In this talk, we will introduce the generalisation of this model called the Monotone Decision Tree (or MDT) model, where instead of simple input bits, any monotone function over the input bits can be queried. With this definition, the complexity measures of an MDT (like height and size of the tree) computing a function f can be seen as the measures of “non-monotonicity” of the function f. We first reinforce this intuition, by exactly characterizing the monotone decision tree complexity in terms of alternation of the Boolean function (which is yet another well-studied measure of non-monotonicity of Boolean functions). We study non-deterministic and randomized variants of this model and establish similar connections.
    
    We then define the decision tree complexity classes DT(mon-C) for standard circuit complexity classes C (like AC^0 or TC^0), and compare them with C itself. We also study the randomised variant RDT(mon-C) and show that DT(mon-TC^0) = RDT(mon-TC^0) = TC^0; and DT(mon-AC^0) subseteq RDT(mon-AC^0) subseteq AC^0. Towards solving AC^0 vs DT(mon-AC^0), we give an upper bound on the number of negations required to compute the functions in DT(mon-AC^0).
    
    This is based on joint work with Sai Jayasurya and Jayalal Sarma.



40. Title : The Multiplayer Colonel Blotto Game
    Speaker : Ben Edelman, Harvard University
    Date, Time & Venue : Wed, Aug 12, 2020, 7:00 PM - Online meet.google.com/gjq-rbvf-zfj
    [Abstract]

    One of the oldest games in game theory is the Colonel Blotto game, a model of resource competition across simultaneous fronts (e.g., two-party elections). It is notoriously difficult to describe equilibria for the game despite its apparent simplicity. The technical difficulty lies in finding a joint distribution that (a) has desired single-variable marginals and (b) almost surely satisfies a joint budget constraint. Recently, we introduced a natural multiplayer extension of Blotto (a model for, e.g., multi-party elections) and found equilibria for many parameter settings. Notably, unlike prior work, our derivation is in the form of an efficient sampling algorithm with a proof of correctness. In this talk, I will motivate the problem of finding Blotto equilibria, present some classic solutions in the two-player version of the game, and sketch our multiplayer solution, all for the continuous setting. Based on joint work with Enric Boix-Adserà and Siddhartha Jayanti: https://arxiv.org/abs/2002.05240.



41. Title : On Pure Space, Catalytic Space and Codes
    Speaker : Sagar Bisoyi, IIT Madras
    Date, Time & Venue : Fri, May 29, 2020, 11:30 AM - A M Turing Hall
    [Abstract]

    MS Seminar



42. Title : Simple, Credible, and Approximately-Optimal Auctions
    Speaker : Santhoshini V, Harvard University
    Date, Time & Venue : Tue, Apr 21, 2020, 3:00 PM - Online
    [Abstract]

    The work that I am planning to present is my recent work on design of simple, approximately revenue-optimal and credible multi-item auctions with Maxwell Fishelson (MIT), Costis Daskalakis (MIT), Vasilis Syrgkanis (MSR) and Brendan Lucier (MSR). In this work, we build a general framework to construct approximately revenue-optimal multi-item auctions from single-item auctions which satisfy a certain "type-loss tradeoff" property. We demonstrate that several commonly used single-item auction formats like VCG/second-price, first-price, all-pay, satisfy this property, thereby proving the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments. This also enables us to design the first static, credible, and approximately revenue-optimal multi-item, multi-bidder auction.



43. Title : A Quadratic Kernel for Tracking Paths Problem
    Speaker : Pratibha Choudhary, IIT Jodhpur
    Date, Time & Venue : Wed, Mar 11, 2020, 2:30 PM - A M Turing Hall (BSB 361)
    [Abstract]

    Given a graph G, terminal vertices s and t, and an integer k, the Tracking Paths problem asks if there exists at most k vertices in G, which if marked as trackers would ensure that a unique sequence of trackers is encountered in each s-t path. The problem was first proposed by Banik et al. in their paper in CIAC 2017, where they gave some results (including NP-completeness) for a restricted version of the problem where only shortest s-t paths in the graph are taken into consideration. We prove that the problem of tracking paths is NP-complete and fixed-parameter tractable (LATIN 2018). In this talk, I shall explain how to derive a quadratic kernel for the problem of finding a tracking set of size k, i.e. a polynomial time algorithm which, given an instance of the problem, either gives an equivalent instance with O(k^2) vertices and edges, or replies that there does not exist a tracking set of size k. For the case of d-degenerate graphs, it can be shown that there exists a linear kernel i.e. O(dk).



44. Title : Homomorphisms of signed graphs and the first no-homomorphism lemma
    Speaker : Reza Naserasr, Université de Paris, IRIF, CNRS, Paris, France
    Date, Time & Venue : Thu, Feb 27, 2020, 2:00 PM - ALC (MR1)
    [Abstract]

    We will introduce notion of homomorphisms of signed graphs and introduce the motivation of this study. We will then consider the first no-homomorphism lemma which provides a set of necessary conditions for a signed graph $(G, sigma)$ to admit a homomorphism to a signed graph $(H,pi)$. We will then search for signed graphs $B$ with the property that a homomorphism from a signed planar graph $(G, sigma)$ to $B$ exists as soon as conditions of the no-homomorphism lemma are satisfied. Observing that the question captures the 4CT, we will formulate a conjecture that extends this well known theorem and we give main ideas of a proof of a case which strengthen the 4CT (proof uses 4CT of course).



45. Title : Matchings under preferences with Lower Quotas
    Speaker : Girija Limaye, IIT Madras
    Date, Time & Venue : Tue, Feb 25, 2020, 3:00 PM - Turing Hall
    [Abstract]

    We consider a setting involving residents and hospitals, where both residents and hospitals have a preference order over a subset of the other side and each hospital specifies an upper-quota and a lower-quota. We consider the problem of matching residents to hospitals such that a resident is matched to at most one hospital and a hospital is matched to at most upper-quota-many residents. A matching is feasible if every hospital fulfills its lower-quota. Among all such feasible matchings, our goal is to compute one that is optimal according to the preferences. This problem models important applications like course-allocation, assigning teaching assistants in academic institution. When lower quotas are not present, stability is a well-studied notion of optimality. However in presence of lower quotas, there exist instances that admit no stable, feasible matching. For such instances, different relaxations like almost-stability, popularity and envy-freeness are studied. In this talk, we will first focus on envy-freeness. We will present combinatorial problems specific to envy-free matchings when the preference lists are strict or when they contain ties. We will present NP-hardness results and approximation algorithm when the preferences are strict. However, there exist lower-quota instances which do not admit a feasible, envy-free matching. We will present a new notion of optimality called relaxed stability such that any instance with lower quotas is guaranteed to admit a feasible, relaxed stable matching.
    
    Popular matchings in above setting is also a well-studied problem. We will explore popular matchings in presence of lower quotas where only one side has a preference ordering.



46. Title : Grundy and partial Grundy coloring of graphs
    Speaker : Shaily Verma, IIT Delhi
    Date, Time & Venue : Tue, Jan 28, 2020, 4:00 PM - Turing Hall
    [Abstract]

    Let c be a proper k-coloring of a graph G with color classes V1, V2,..., Vk. A vertex v ∈ Vi is called a Grundy vertex if v has a neighbor in each color class Vj for every j < i. The proper k-coloring c is a Grundy k-coloring if every vertex v ∈ Vi is a Grundy vertex for all i, 1 ≤ i ≤ k. The proper k-coloring c of G is a partial Grundy k-coloring if there exists at least one Grundy vertex in each color class Vi, 1 ≤ i ≤ k. The maximum integer k such that there exists a Grundy (or partial Grundy) k-coloring of G is called Grundy number (or partial Grundy number) and it is denoted by Γ(G) (or ∂Γ(G)). I will talk about the results I obtained in my PhD thesis on Grundy coloring and partial Grundy coloring in subclasses of bipartite graphs. It is known that the problems to determine Grundy number or partial Grundy number for bipartite graphs are NP-complete problems. We prove that both the problems remain NP-complete for perfect elimination bipartite graphs. We also give structural characterizations for the Grundy number of some special bipartite permutation graphs, which is a proper subclass of perfect elimination bipartite graphs. We give an upper bound on the partial Grundy number of a general graph, which is better than an existing upper bound. We also prove that the partial Grundy number of chain graphs achieve this new upper bound, where the class of chain graphs is a proper subclass of perfect elimination bipartite graphs.



47. Title : Achieving Collusion-resistant Unidirectional Proxy Re-encryption without Pairing in the Random Oracle Model
    Speaker : Arinjitha Paul, IIT Madras
    Date, Time & Venue : Tue, Jan 28, 2020, 2:00 PM - Turing Hall
    [Abstract]



48. Title : Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs
    Speaker : Dhannya S.M., IIT Madras
    Date, Time & Venue : Mon, Jan 13, 2020, 3:00 PM - CS24
    [Abstract]

    Given a hypergraph H, the conflict-free colouring problem is to colour vertices of H using minimum colours so that in every hyperedge e of H, there is a vertex whose colour is different from that of all other vertices in e. Our results are on a variant of the conflict-free colouring problem considered by Cheilaris et al., known as the 1-Strong Conflict-Free (1-SCF) colouring problem, for which they presented a polynomial time 2-approximation algorithm for interval hypergraphs. We show that an optimum 1-SCF colouring for interval hypergraphs can be computed in polynomial time. Our results are obtained by considering a different view of conflict-free colouring which we believe could be useful in general. For interval hypergraphs, this different view brings a connection to the theory of perfect graphs which is useful in coming up with an LP formulation to select the vertices that could be coloured to obtain an optimum conflict-free colouring. The perfect graph connection again plays a crucial role in finding a minimum colouring for the vertices selected by the LP formulation



49. Title : Combinatorics of Pseudo-Bordered Words
    Speaker : Manasi Kulkarni, IIT Madras
    Date, Time & Venue : Tue, Dec 3, 2019, 4:00 PM - Turing Hall
    [Abstract]

    The concepts of pseudo-bordered and pseudo-unbordered words are in large part motivated by, the research in theoretical DNA computing, and by quest to understand how these and other notions in combinatorics on words evolve when “identity” function is replaced with “pseudo-identity” functions.Furthermore, a word w is said to be θ-bordered (or pseudo-bordered) if there exists a word v in Σ^+ that is a proper prefix of w, while θ(v) is a proper suffix of w. The aim of the talk is to present results pertaining to pseudo-(un)bordered words, in particular, disjunctivity of set of all words with exactly i θ-borders, D_θ(i) for all i ge 1 and D_θ (i)D(i) for all i ge 2 where D(i) is the set of all words with exactly i borders.



50. Title : Coalitions and Monopolies in Graphs
    Speaker : David Peleg, Weizmann Institute of Science
    Date, Time & Venue : Tue, Aug 27, 2019, 3:30 PM - AM Turing Hall
    [Abstract]

    The talk will give an overview of results concerning static and dynamic monopolies in graphs from graph theoretic and algorithmic standpoints.



51. Title : Compact Labeling Schemes
    Speaker : David Peleg, Weizmann Institute of Science
    Date, Time & Venue : Tue, Aug 27, 2019, 2:00 PM - AM Turing Hall
    [Abstract]

    Labeling schemes are schemes for labeling the nodes of a graph in a way that will allow one to efficiently extract information concerning various properties of the nodes locally and directly from their labels. Of particular interest are compact label-based representations (i.e., ones using short labels). The talk will survey some known results concerning labeling schemes for graphs, including upper and lower bounds for several interesting functions and graph families, and will also discuss directions for future research.



52. Title : Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors.
    Speaker : Fabrice Mouhartem, IIT Madras
    Date, Time & Venue : Tue, Jul 23, 2019, 2:00 PM - Turing Hall
    [Abstract]

    We are organizing a talk today at 2 pm by Fabrice Mouhartem who has recently joined the department. The talk will be on a long standing open problem in Cryptography which has very recently been resolved and is based on the following results:
    
    - Fiat-Shamir: From Practice to Theory. (At STOC this year. Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum and Daniel Wichs.) The work is a merge of the following two e-print articles: https://eprint.iacr.org/2018/1004 and https://eprint.iacr.org/2018/1248
    
    - Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors.
    (To appear at Crypto this year. Chris Peikert and Sina Shiehian.)



53. Title : Ciphertext policy attribute based encryption based on LWE
    Speaker : Rajarshi Biswas, IIT Madras
    Date, Time & Venue : Wed, Apr 10, 2019, 2:00 PM - ALC Room
    [Abstract]

    This is cross-listed as an MS Seminar.
    
    Access control on encrypted data is a desirable property in many applications e.g. encrypted storage in distributed environments. This can be achieved by public key encryption schemes but the main disadvantage is that implementing any access control policy requires the encryptor to encrypt separately to each user that satisfies the policy. Attribute based encryption (ABE) is a cryptographic scheme that overcomes this disadvantage by letting the encryptor encrypt a message directly to a policy and letting users’ keys be issued according to credentials. In more detail, a ciphertext is associated with a pair (P, m) where P is an access control policy and m is a message, and a user is provided a key corresponding to credentials x. The ciphertext can be decrypted to reveal m if and only if P(x) = 1.
    
    ABE can be categorized into to two types depending on whether the access-structure (policy) is embedded in the ciphertext, namely ciphertext-policy ABE, or in the key, namely key-policy ABE. While key-policy ABE schemes (KP-ABE) have received a lot of attention [BS03, SW05, GPSW06, OSW07, GGH+13, BNS13, HW13, Boy13], and can be constructed from various standard assumptions, much less is known about ciphertext-policy schemes (CP-ABE). The few known constructions [BSW07, Wat11] are restrictive in the policies they can support and are all based on various assumptions on bilinear maps. Since CP-ABE are arguably more natural than KP-ABE, it is important to address this gap. In this work, we construct the first ciphertext policy attribute-based encryption (ABE) system for circuits with short ciphertexts from lattices. The security of our solution is based on the sub exponential hardness of the learning with errors (LWE) problem. We construct our attribute-based system using techniques from the KP-ABE scheme of Boneh et al. [BGG+14] and homomorphic signatures (HTDF) by Gorbunov et al. [GVW15]. However our scheme is only secure when the adversary is limited to making a single key request, i.e. single key CP-ABE. Additionally, we show that key-policy attribute-based encryption scheme based on linear secret sharing schemes (LSSS) by Boyen [Boy13] is completely insecure against a general ABE adversary. We demonstrate an attack based on bonsai lattice basis extension technique by [CHKP10] which allows an adversary to obtain secret keys for policies and decrypt cipher-texts encrypted under attributes which do not satisfy the policy.



54. Title : The polymorphic gateway between structure and algorithms: Constraint Satisfaction and Beyond
    Speaker : Venkatesan Guruswami, CMU, USA
    Date, Time & Venue : Tue, Mar 26, 2019, 4:00 PM - A M Turing Hall
    [Abstract]

    This talk is cross-listed as a TCS-IITM Computer Science and Engineering Seminar.



55. Title : A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
    Speaker : Gopal Pandurangan, University of Houston, USA
    Date, Time & Venue : Tue, Mar 12, 2019, 3:00 PM - A M Turing Hall
    [Abstract]

    This talk is cross-listed as a department seminar.
    
    The distributed minimum spanning tree (MST) problem is one of the central problems in distributed computing. In this talk, we present a randomized (Las Vegas) distributed algorithm that constructs a MST in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in ilde{O}(D + sqrt{n}) time and exchanges ilde{O}(m) messages (both with high probability), where n is the number of nodes of the network, D is the diameter, and m is the number of edges.This is the first distributed MST algorithm that is simultaneously optimal with respect to both time and message complexities.
    This work is joint with Peter Robinson and Michele Scquizzato and appeared in STOC 2017.
    Brief Bio: Gopal Pandurangan (http://www.cs.uh.edu/~gopal) is a Professor in the Department of Computer Science at the University of Houston and a VAJRA visiting professor at the Indian Institute of Technology, Madras. He received his Ph.D. from Brown University, Masters from SUNY Albany, and B.Tech. from IIT Madras (all in Computer Science). He has held faculty and visiting positions at Nanyang Technological University (Division of Mathematical Sciences) in Singapore, Brown University, Purdue University, and Rutgers University. His research interests are in theory and algorithms, distributed computing, networks, large-scale data, and computational biology. He has published over 100 refereed papers in these areas. His work has appeared in JACM, SICOMP, ACM TALG, STOC, FOCS, SODA, PODC, SPAA, and RECOMB. His research has been supported by research grants from the US National Science Foundation, US-Israeli Binational Science Foundation, and the Singapore Ministry of Education.



56. Title : Parametric Shortest Paths in Planar Graphs
    Speaker : Jaikumar Radhakrishnan, TIFR Mumbai
    Date, Time & Venue : Fri, Mar 8, 2019, 4:00 PM - Aryabhatta Hall
    [Abstract]

    For a directed graph G with n vertices, including two vertices s and t, and edge weights that vary linearly with a parameter lambda, the cost of the shortest s-t path is a piece-wise linear function of lambda. The number of pieces in this function is the parametric shortest path complexity of G. We show that there is a sequence of planar graphs, where the n-th graph has n vertices and parametric complexity n^{c log n}, for a constant c > 0.
    
    Graphs with similar parametric complexity were constructed by Carstensen (1983) and Mulmuley & Shah (2001) but their graphs were non-planar. Gusfield (1980) showed that the parametric complexity of an n vertex graph is at most n^{d log n}, for a constant d > 0, hence these constructions and ours are optimal. Nikolova, Kelner, Brand and Mitzenmacher (2006) conjectured that the parametric complexity of planar graphs is polynomially bounded; our construction refutes this conjecture.
    
    (This is joint work with Kshitij Gajjar, TIFR.)
    
    This is the 7th talk of the TCS-IIT Madras Computer Science and Engineering Colloquium Series.



57. Title : The Story of Obfuscation
    Speaker : Shweta Agrawal, IIT Madras
    Date, Time & Venue : Tue, Mar 5, 2019, 4:00 PM - Turing Hall
    [Abstract]

    The primitive of obfuscation has captured the imagination of the cryptographic community in recent times. Informally, an obfuscation of a circuit C is a circuit C' that retains the functionality of C but provably hides everything about C except its input-output behavior. In more detail, C'(x) = C(x) for any input x, but C' hides "everything else" about C.
    We need to define the term "everything else", and this turns out to be of paramount importance. For the strongest notion of "everything else", the notion of obfuscation is provably impossible to achieve (via a beautiful counterexample that involves a Turing machine eating itself). This led to the weaker notion of "best possible obfuscation" but this looked so weak that it was unclear whether it was good for anything.
    In a series of beautiful works in the last 6 years, the crypto community discovered to its surprise and delight that this weak notion was actually immensely useful, and enabled a whole host of "never seen before" crypto, a veritable crypto wonderland. But whether this notion could be achieved based on any reasonable mathematical conjectures has been a central open question. Starting from the seminal work of Garg, Gentry, Halevi, Raykova, Sahai and Waters (FOCS 2013) and ending with my upcoming work (Eurocrypt 2019), I will tell you the highlights of this journey, from constructions to attacks to applications and beyond.



58. Title : Breaking the Circuit Size Barrier for Secure Computation Under DDH
    Speaker : Rachit Garg, IIT Madras
    Date, Time & Venue : Tue, Feb 26, 2019, 3:00 PM - ALC Room
    [Abstract]

    This is a presentation of the paper -
    
    Breaking the Circuit Size Barrier for Secure Computation Under DDH Elette Boyle, Niv Gilboa and Yuval Ishai
    
    



59. Title : Realizability of Graph Specifications: Characterizations and Algorithms
    Speaker : David Peleg, Weizmann Institute of Science, Israel
    Date, Time & Venue : Tue, Feb 19, 2019, 3:00 PM - Turing Hall
    [Abstract]

    This is cross-listed as a department seminar.
    
    The study of graphs and networks often involves studying various parameters of the graph vertices, capturing different aspects of the graph structure, such as the vertex degrees or the distances between the vertices. Given an n-vertex graph G and a parameter of interest f, one may associate with G a vector F(G) = (f1,...,fn) giving the value of f for each vertex. This vector can be thought of as the f-profile of the graph. This paper concerns the dual problem, where given an n-entry f-specification vector F = (f1,...,fn), we need to decide whether it is possible to find a graph G realizing this specification, namely, whose f-profile F(G) conforms to F. The paper introduces the notion of graph realiziations and illustrates a number of example problems related to finding graph realiziations for given specifications.
    
    (Based on joint work with Amotz Bar-Noy, Keerti Choudhary and Dror Rawitz)
    
    Speaker bio: Prof. David Peleg is the Norman D. Cohen Professorial Chair of Computer Science at the Weizmann Institute of Science, Rehovot, Israel. His research interests span algorithms (specifically graph algorithms and approximation algorithms), distributed computing, communication networks and mobile robot systems. His pioneering contributions have been recognized by the Edsger W. Dijkstra Prize in Distributed Computing, awarded jointly by ACM and EATCS in 2008, Prize for Innovation in Distributed Computing awarded by the Colloquium on Structural Information and Communication Complexity (SIROCCO) in 2001 among others. He is a fellow of the Association of Computing Machinery (ACM) since 2017.



60. Title : Identity-based Group Encryption revisited
    Speaker : Kanika Gupta, IIT Madras
    Date, Time & Venue : Tue, Feb 5, 2019, 2:30 PM - Turing Hall
    [Abstract]

    This is cross-listed as an MS Seminar.



61. Title : Optimal Matchings under Classifications
    Speaker : Nada Abdul Majeed Pulath, IIT Madras
    Date, Time & Venue : Mon, Jan 28, 2019, 2:30 PM - A M Turing Hall
    [Abstract]

    In this work, we consider the problem of computing an optimal matching in a bipartite graph where elements of one side of the bipartition specify preferences over the other side, and one or both sides can have capacities and classifications. The input instance is a bipartite graph G=(A U P,E), where A is a set of applicants, P is a set of posts, and each applicant ranks its neighbors in an order of preference, possibly involving ties. Moreover, each vertex v in A U P has a quota q(v) denoting the maximum number of partners it can have in any allocation of applicants to posts - referred to as matching. A classification for a vertex u is a collection of subsets of neighbors of u. Each subset (class) has an upper quota denoting the maximum number of vertices from the class that can be matched to u. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the vertices and classes.
    
    We consider two well-studied notions of optimality namely popularity and rank-maximality. The notion of rank-maximality involves finding a matching in G with the maximum number of rank-1 edges, subject to that, the maximum number of rank-2 edges and so on. We present an O(|E|^2)-time algorithm for finding a feasible rank-maximal matching when each classification is a laminar family. We show an analogous result for computing a popular matching amongst feasible matchings (if one exists) in a bipartite graph with posts having capacities and classifications and applicants having a quota of one.



62. Title : Stability, Popularity, and Lower Quotas
    Speaker : Meghana Nasre, IIT Madras
    Date, Time & Venue : Thu, Dec 20, 2018, 11:00 AM - Turing Hall
    [Abstract]

    We consider the problem of assigning a set of men to a set of women where each participant ranks members of the opposite side in an order of preference. This is called the stable marriage problem in literature.
    
    It is well known that every instance of the stable marriage problem admits a "stable matching" which can be computed efficiently by the Gale and Shapley algorithm.
    
    In this talk we consider three variants of the stable marriage problem where
    (a) Preference lists can contain ties,
    (b) Preference lists can be incomplete,
    (c) Vertices can have lower quotas.
    
    For each of these variants a different notion of optimality is applicable; yet we show that, simple extensions of the Gale and Shapley algorithm computes an optimal matching in each of them. The talk is based on three papers -- Z. Kiraly (Algorithmica 2011), T. Kavitha (SICOMP 2014) and Nasre and Nimbhorkar (FSTTCS 2017).



63. Title : Parallel Dynamic Graph Algorithms in Constant Rounds
    Speaker : Saurabh Sawlani, Georgia Tech
    Date, Time & Venue : Thu, Dec 13, 2018, 11:00 AM - Turing Hall
    [Abstract]

    We study the maintenance of dynamic graphs under batches of edge insertions and deletions in the massively parallel model of computation. In this model, the graph is stored on a number of machines, each having space strongly sub-linear with respect to the number of vertices. Our goal is to handle batches of updates and queries, where the data for each batch fits onto one machine, in constant rounds of parallel computation, as well as to reduce the total communication between the machines. This setting corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication in the static setting have been elusive for problems as simple as connectivity of undirected graphs. We give data structures for handling batches of updates in constant rounds of communication for a wide range of fundamental problems in graph algorithms, including c-edge-connectivity for c <= 3, minimum spanning trees, and triangle counting. Furthermore, for many of the problems, we use further partitioning techniques to reduce the total communication to sub-linear per update/query batch without increasing the number of communication rounds. Our techniques combine sequential data structures for dynamic graphs, structural observations of graphs, as well as distributed data structures supporting parallel updates and queries in batch. Due to the wide applicability of our approaches, we believe it represents a practically-motivated workaround to the current difficulties in designing more efficient massively parallel static graph algorithms.



64. Title : Constrained PRFs for NC1 in Traditional Groups
    Speaker : Shota Yamada, AIST, Japan
    Date, Time & Venue : Thu, Nov 29, 2018, 3:00 PM - Turing Hall
    [Abstract]

    We propose new constrained pseudorandom functions (CPRFs) in traditional groups. Traditional groups mean cyclic and multiplicative groups of prime order that were widely used in the 1980s and 1990s (sometimes called pairing-free groups). Our main constructions are as follows.
    
    - We propose a selectively single-key secure CPRF for circuits with depth $O(log n)$ (that is, NC1 circuits) in traditional groups where $n$ is the input size. It is secure under the $L$-decisional Diffie-Hellman inversion ($L$-DDHI) assumption in the group of quadratic residues $QR_q$ and the decisional Diffie-Hellman (DDH) assumption in a traditional group of order $q$ in the standard model.
    - We propose a selectively single-key private bit-fixing CPRF in traditional groups. It is secure under the DDH assumption in any prime-order cyclic group in the standard model.
    - We propose adaptively single-key secure CPRF for NC1 and private bit-fixing CPRF in the random oracle model.
    
    To achieve the security in the standard model, we develop a new technique using correlated-input secure hash functions.
    
    The talk will be based on our work that appeared at Crypto 2018. The paper is available at https://eprint.iacr.org/2018/154
    
    



65. Title : Approx-SVP in Ideal Lattices with Pre-processing
    Speaker : Alice Pellet-Mary, ENS Lyon, France
    Date, Time & Venue : Tue, Oct 30, 2018, 4:00 PM - Turing Hall (BSB 361)
    [Abstract]

    Finding a short non zero vector in an Euclidean lattice is a well-studied problem which has proven useful to construct many cryptographic primitives. The current best asymptotic algorithm to find a relatively short vector in an arbitrary lattice is the BKZ algorithm.
    
    This algorithm recovers a vector which is at most $2^{n^{alpha}}$ times larger than the shortest non zero vector in time $2^{n^{1-alpha}}$ for any $alpha$ between 0 and 1.
    
    In order to gain in efficiency, it is sometimes interesting to use structured lattices instead of general lattices. An example of such structured lattices are principal ideal lattices. One may then wonder whether, on the security front, it is easier to find short vectors in a structured lattice or not. Until 2016, there was no known algorithm which would perform better on principal ideal lattices than the BKZ algorithm (either classically or quantumly). In 2016, Cramer et al. proposed a quantum algorithm that finds a $2^{sqrt n}$ approximation of the shortest non zero vector in polynomial time. However, the BKZ algorithm remained the best algorithm in the classical setting or for approximation factor smaller than $2^{sqrt n}$ in the quantum setting.
    
    In this talk, I will present an algorithm that extends the one of Cramer et al. and improves upon the BKZ algorithm for principal ideal lattices, both quantumly and classically. This algorithm is heuristic and non uniform (or equivalently it needs an exponential time pre-processing).



66. Title : Decision problems on linear recurrence sequences
    Speaker : Nikhil Balaji, University of Ulm, Germany
    Date, Time & Venue : Fri, Sep 7, 2018, 3:30 PM - A M Turing Hall
    [Abstract]

    Given a linear recurrence sequence (LRS) with initial conditions defining an infinite sequence, the Skolem problem asks if zero ever occurs in this sequence? Decidability of the Skolem problem has been open for several decades. Currently it is known to be decidable for LRS of order up to 4. The best complexity lower bound known is NP-hardness from a 2003 paper of Blondel and Portier. A recent work due to Ouaknine and Worrell shows that decidability of certain related problems on LRS would solve long standing open problems in Diophantine approximation.
    
    In this talk, I will give a different proof of the NP-hardness lower bound, which is arguably simpler and yields a subclass of LRS for which the Skolem problem is NP-complete. I will also mention a few open problems closely related to the Skolem problem.
    
    Along the way, we see how this simple problem relates to verification of probabilistic systems and program termination and highlight a few related questions.
    
    (Partly based on joint work with S. Akshay and Nikhil Vyas)
    
    



67. Title : Two-round Multiparty Secure Computation under Minimal Assumptions
    Speaker : Akshayaram Srinivasan, UC Berkeley
    Date, Time & Venue : Thu, Aug 9, 2018, 3:30 PM - Turing Hall
    [Abstract]

    This is cross-listed as a department seminar.



68. Title : Functional Encryption and Indistinguishability Obfuscation for Turing Machines from (Nearly) Minimal Assumptions
    Speaker : Monosij Maitra, IIT Madras
    Date, Time & Venue : Tue, Jul 17, 2018, 3:00 PM - Turing Hall
    [Abstract]

    Functional Encryption (FE) is a generalisation of public key encryption (PKE) enabling fine grained access control on encrypted data. Traditional PKE allows issuing only secret keys that enable decryption of a ciphertext CT(m) to retrieve either the encoded message m or nothing else. FE aims to give out secret keys corresponding to functions f from a class of functions F and ciphertexts correspond to messages m from the domain M of f. Given such a function key and a FE ciphertext CT(m), it enables the decryptor to learn f(m) and nothing else. Naturally enough the idea of FE has a lot of applications in todays scenario of cloud computing.
    
    Program obfuscation aims to alter a program into an unintelligible one such that its functionality is still preserved. While the most natural idea of program obfuscation, called Virtual Black-box obfuscation, was shown to be impossible for all functions, a weaker version of this notion called Indistinguishability obfuscation (iO) requires that obfuscation of any two functionally equivalent circuits of same size are computationally indistinguishable. Although non-obvious, iO has been shown to be a very powerful notion in the last decade resulting in various practical and theoretical applications in cryptography that were almost out of reach before its advent.
    
    FE for circuits has been shown to imply iO with a sub-exponential loss in reduction and iO is also widely believed to be an inherently sub-exponential assumption. Therefore, replacing applications of iO by polynomially secure FE has garnered a lot of interest recently with extensive results. Another interesting direction initiated by Goldwasser et. al. [GKP+13] that has also seen further substantial research efforts is that of modelling functions as Turing machines and Random Access machines instead of circuits. Such a representation leads to direct advantages like supporting unbounded inputs, fixed description size and input specific runtimes. Our results in the above context are as follows:
    
    1. We construct iO for Turing machines with bounded inputs from the same assumptions as required in the circuit model, namely, sub-exponentially secure FE for circuits. The previous best constructions [KLW15, AJS17] require sub-exponentially secure iO for circuits, which in turn requires sub-exponentially secure FE for circuits [AJ15, BV15].
    
    2. We provide a new construction of single input FE for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact FE for circuits. The previously best known construction by Ananth and Sahai [AS16] relies on iO for circuits, or equivalently, sub-exponentially secure FE for circuits.
    
    3. We provide a new construction of Multi-input FE for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string x_i of unbounded length. We rely on sub-exponentially secure FE for circuits, while the only previous construction [BGJS15] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation (pc-diO).
    
    All our results require a mild assumption of decomposability on the underlying circuit FE schemes. Roughly speaking, a decomposable FE scheme asserts a long string to be encrypted bit-by-bit, using shared randomness across bits. This property is already satisfied by almost all existing circuit FE schemes to the best of our knowledge. Our techniques are new and from first principles, and avoid usage of sophisticated iO specific machinery that were used in all relevant prior work.
    
    



69. Title : A Logical Approach to Parameterized Complexity
    Speaker : Subhadra Nanda, IIT Madras
    Date, Time & Venue : Wed, Jul 4, 2018, 3:00 PM - Turing Hall
    [Abstract]

    This is cross listed as an MS Seminar.



70. Title : Strengthening Fredman’s Lower Bound on Orthogonal Range Querying
    Speaker : Swaroop N P, IMSc Chennai
    Date, Time & Venue : Tue, Jul 3, 2018, 3:00 PM - Turing Hall
    [Abstract]

    In this paper, we focus on a lower bound by Fredman on data structures supporting range querying on a set of m points in R^n . Such a data structure usually maintains a set of canonical sets and on a range query outputs a disjoint union of the appropriate canonical sets. In the proof of his lower bound, Fredman exploits a combinatorial tradeoff between the sizes of canonical subsets and the total number of canonical subsets required to cover all query ranges. In particular, he shows that the arithmetic mean of these two quantities has to be Omega(m log^n m). Our first result shows that this tradeoff can be strengthened, namely, that the geometric mean of the canonical set sizes and number of canonical sets is Omega(m log^n m). Our second result is an alternate proof of this tradeoff in the one dimensional setting. By interpreting range querying as factorizing a boolean matrix, we formulate a non-linear optimization problem. Then, using the Lagrangian dual of this problem to derive a lower bound on its optimal value, we obtain a stronger claim than Fredman’s tradeoff in the one dimensional setting, namely, that both the canonical set sizes and the number of canonical sets is Omega(m log m).



71. Title : Graph Partitioning on Low Threshold-Rank and Semi-Random Graphs
    Speaker : Rakesh Venkat, Hebrew University of Jerusalem, Israel
    Date, Time & Venue : Thu, Jun 28, 2018, 11:00 AM - Turing Hall
    [Abstract]

    Graph partitioning refers to a class of algorithmic problems that ask for a partition of an input graph $G$ into two or more parts, while optimizing an objective function that measures the quality of the partition. One natural criteria that is of both theoretical and practical significance is that the cuts are sparse: they split the graph into balanced parts with very few interactions across the parts. Although these problems are usually NP-Hard to approximate (up to large factors) in the general case, input graphs in practice often have some kind of structure that could help one find better sparse cuts more efficiently. This presents us with the natural question of designing algorithms that give better guarantees or are more efficient for such input instances. In this talk, we will mainly focus on how the Sparsest Cut problem can be solved efficiently on a class of graphs called low threshold-rank graphs. The Sparsest Cut objective measures the sparsity of a cut in terms of edges going across the cut, normalized by the size of the partition. While the best known approximation guarantee for this problem is $O(sqrt{log n})$ in general, we show that one can do much better on graphs which already have a clustered structure, using an efficient and intuitive algorithm. Our algorithm also furnishes a generalization of a geometric theorem of Goemans on embedding finite metric spaces into $ell_1$. In the latter part of the talk, we will briefly look at a natural semi-random model of generating clustered input graphs where a better objective is to consider the number of boundary vertices on the cut, as opposed to edges across it. We will see an outline of how to exactly recover a sparse vertex-cut for a wide range of the model parameters using Semidefinite Programming.
    
    (Based on joint works with Amit Deshpande, Prahladh Harsha, Anand Louis and Yuval Rabani).
    
    Speaker Bio: The speaker is a postdoctoral fellow at the Hebrew University of Jerusalem, Israel. Prior to this, he obtained his PhD from the Tata Institute of Fundamental Research, Mumbai. His research interests are in Approximation Algorithms, Spectral Graph theory, and Hardness of Approximation.



72. Title : Lower Bounds for Special Classes of Syntactic Multilinear ABPs
    Speaker : Ramya C., IIT Madras
    Date, Time & Venue : Wed, Jun 27, 2018, 3:00 PM - Turing Hall
    [Abstract]

    Algebraic Branching Programs(ABPs) are edge-labelled layered directed acyclic graphs with a dedicated source node s and terminal node t with edges labelled by variables or constants. The polynomial computed by an ABP is the sum over all s to t paths, product of edge labels in the corresponding path. ABPs are standard models for computing polynomials that have been studied time and again in the context of lower bounds and identity testing. While the challenge of proving super-polynomial lower bounds for Algebraic Branching Programs still seems to be a distant dream, naturally the focus has been on restricted classes of ABPs. Syntactic multilinear ABPs are restrictions of ABPs where every variable is allowed to occur at most once in every path from the source to terminal node.
    
    Proving lower bounds for syntactic multilinear ABPs remains a long-standing open question in Algebraic Complexity Theory. The current best known bound is barely quadratic in the number of variables [Alon-Kumar-Volk, CCC 2017]. In this talk, we develop a framework for proving lower bounds for syntactic multilinear ABPs. We will show that rather than looking at the ABP, it might be beneficial to convert the ABP to a syntactic mulilinear formula with a super polynomial blow-up in the size and then exploit the structural limitations of resulting formula to obtain exponential lower bounds for special classes of multilinear ABPs as well as multilinear circuits. In particular, we prove exponential lower bounds for sum of Oblivious Read-Once ABPs - where every variable appears as edge labels in exactly one layer of the ABP. En route, we will also prove super-polynomial lower bounds for a special class of syntactic multilinear arithmetic circuits.



73. Title : Algorithms and Data Structures for Geometric Intersection Query Problems
    Speaker : Rahul Saladi, UIUC, USA
    Date, Time & Venue : Tue, Jun 26, 2018, 11:00 AM - Turing Hall
    [Abstract]

    This is cross-listed as a department seminar.



74. Title : Lower Bounds for Energy Complexity of Boolean Functions
    Speaker : Samir Otiv, Maximl Labs
    Date, Time & Venue : Wed, Jun 13, 2018, 4:00 PM - Turing Hall
    [Abstract]

    Energy complexity of a Boolean circuit C (EC(C)​)​ is the maximum number of gates (excluding the inputs) that output a 1. The energy complexity of a function f (EC(f)) is the energy of the minimum energy circuit computing f.​​ In an earlier talk, new upper bounds for energy complexity of Boolean functions were presented - namely circuits with at most DT(f)^3 energy computing f, where DT(f) is the decision tree depth complexity of the function f.
    
    In this talk, we show new techniques to obtain lower bounds on EC(f). We introduce the notion of continuous positive paths using which we show the following lower bounds.​​ We define a parameter, positive sensitivity (psens(f)) which is similar to the sensitivity of Boolean functions and show that for any f, EC(f) ​is at least psens(f)/3​.​
    
    ​Further, for a monotone function f, denote KW^+(f) as the cost of the monotone Karchmer-Wigderson game for $f$. We show that EC(f) = ​Omega(​KW^+(f)​. Thus, any circuit computing the perfect matching function, must have Omega(sqrt(n)) energy.​ 
    
    We obtain stronger lower bounds for energy complexity in ​for constant depth circuit. We show ​that a​ny depth 3 circuit computing parity on n bits require an energy of Omega(n).​
    
    The talk is based on a joint work with Krishnamoorthy Dinesh and Jayalal Sarma, and it forms a part of a joint paper accepted at 24th International Computing and Combinatorics Conference (COCOON 2018).
    
    



75. Title : Energy, Decision Tree Depth, and Quantum Communication Complexity of Boolean Functions
    Speaker : Krishnamoorthy Dinesh, IIT Madras
    Date, Time & Venue : Thu, May 17, 2018, 3:00 PM - A M Turing Hall
    [Abstract]

    This is cross-listed as a PhD Seminar.



76. Title : Linear Equivalence to Vandermonde Polynomials
    Speaker : Ramya C., IIT Madras
    Date, Time & Venue : Tue, May 1, 2018, 2:00 PM - A M Turing Hall
    [Abstract]

    The Polynomial Equivalence Problem is a fundamental problem in algebraic complexity theory and has gained significant attention in the literature [Kayal SODA 11, Kayal STOC 12]. It is the problem of testing if the two given polynomials are equivalent upto linear change of co-ordinates. We say two polynomials f and g are linearly equivalent if g can be obtained from f by applying an invertible linear transformation A on the set of variables of f. Even the most restricted cases of this problem are as hard as graph isomorphism [Agrawal, Saxena 06] and some cases are not even known to be decidable.
    
    We study the case when one of the two polynomials is fixed to be the Vandermonde polynomial. Vandermonde matrices are standard matrices used in polynomial interpolation and error correcting codes. Vandermonde polynomial is the determinant of the symbolic Vandermonde matrix.
    
    In this talk we will focus on testing if a given polynomial is linearly equivalent to the Vandermonde polynomial. We show a deterministic polynomial time algorithm for the problem when the input polynomial is given as linear factors. In the case when f is given as a black-box, we devise a randomized polynomial time algorithm.
    
    In association with the above computational problem we understand the group of symmetries of the Vandermonde polynomial.
    
    This is cross-listed as a PhD Seminar.



77. Title : Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps
    Speaker : Krishnamoorthy Dinesh, IIT Madras
    Date, Time & Venue : Tue, Jan 30, 2018, 4:00 PM - Turing Hall
    [Abstract]

    For a Boolean function, a combinatorial parameter of interest is the sensitivity defined as the maximum number of bit flips (for any input) that can change the function value over all inputs. An algebraic parameter of interest is the degree of a Boolean function which is the degree of the real multilinear polynomial that agree with the function on Boolean inputs. Nisan and Szegedy (1992) conjectured that for every Boolean function, the degree of the function is at most polynomial in its sensitivity which is now called as the Sensitivity Conjecture. From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function f, the communication complexity of a related function F(x,y) defined as f(x oplus y) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f in the Fourier expansion of f).
    
    A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures, it suffices to upper bound alternation of any Boolean function by a polynomial in sensitivity and logarithm of sparsity, respectively. We show that there exists a family of Boolean functions for which alternation is at least exponential in sensivity and alternation is at least exponential in log-sps(f). Despite this exponential gap, we show that both the conjectures are true for functions with the alternation upper bounded by poly(log n). Enroute the proof, we derive new relationship between deg(f), deg_2(f) and alternation of any Boolean function. We show more applications of this new relation.
    
    This is joint work with Jayalal Sarma (IITM), and is to appear in CALDAM 2018.



78. Title : Discovering the Roots: Uniform Closure Results for Algebraic Classes under Factoring
    Speaker : Pranjal Dutta, CMI, Chennai
    Date, Time & Venue : Wed, Jan 17, 2018, 3:00 PM - Turing Hall
    [Abstract]

    Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. I will talk about generalizing it to a matrix recurrence that approximates all the roots "simultaneously". I will also discuss an interesting property of multivariate polynomial factorization which shows that under a random linear transformation Ï„ , f(Ï„x) completely factors via power series roots. Combining these, I will establish that for an algebraic circuit f(x_1, . . . , x_n) of size s, each factor has size at most a polynomial in: s and the degree of the square-free part of f.For the remaining time, I will talk about different model of interest when the given polynomial f is of degree poly(n) and can be computed by a formula (resp. Algebraic Branching Program) size n^{O(log n)} . I will show how to find a similar size formula (resp. ABP) factor in randomized poly(n^{log n})-time.
    
    The talk will be self-contained.
    
    This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur).



79. Title : Property Testing in the Presence of Erased Data
    Speaker : Nithin Mahendra Varma, Boston University, USA
    Date, Time & Venue : Mon, Jan 8, 2018, 3:00 PM - A M Turing Hall
    [Abstract]

    Property testing is a formal framework to design algorithms for large datasets. The traditional definition of property testing [Rubinfeld & Sudan 96, Goldreich, Goldwasser & Ron 98] abstracts datasets as functions and assumes that an algorithm (also called tester) can query points in the domain of a function to obtain the corresponding values. The task of the tester is to distinguish, with probability 2/3, between the case that the function f being queried belongs to a set (property) P and the case that f is far from every function in P, for an appropriate measure of distance.
    
    One of the key assumptions in the above definition, that the tester has access to function values at all of the queried domain points, is not applicable to most real-life datasets. It could be the case that some or several of the function values are kept hidden for privacy reasons, or erased by mistake or by an adversary. Querying such erased points does not provide an algorithm with any information about the function. Moreover, it might happen that, an algorithm, by not knowing the locations of these erasures, makes a lot of queries to erased points and turns out entirely useless. In the talk, I will describe the erasure-resilient property testing model that we defined to account for the occurrence of erasures in datasets. We will then present and analyse our erasure-resilient tester for monotonicity of functions. We will also briefly discuss some ongoing work that explores the connections between property testing, erasure-resilient property testing, and tolerant property testing [Parnas-Ron-Rubinfeld 2006].
    
    Joint work with Kashyap Dixit, Sofya Raskhodnikova and Abhradeep Thakurta.



80. Title : Hazard-free Circuits : Power & Limitations
    Speaker : Balagopal Komarath, Saarland University, Germany
    Date, Time & Venue : Wed, Dec 6, 2017, 3:00 PM - Turing Hall
    [Abstract]

    This talk is cross-listed as a department seminar.



81. Title : Popular Matchings with Lower Quotas
    Speaker : Meghana Nasre, IIT Madras
    Date, Time & Venue : Tue, Dec 5, 2017, 11:00 AM - Turing Hall
    [Abstract]

    In this talk, we consider the problem of computing an optimal matching in a bipartite graph in the presence of preferences and capacities. This models several real world scenarios like assigning medical interns to hospitals, student TAs to courses and so on. The input to our problem is a bipartite graph G = (R U H, E) where elements of both R and H have preferences over a subset of elements from the other set. Each element in H has an upper and lower quota denoting the maximum and the minimum number of elements of R that are assigned to it in any feasible matching.
    
    Stability is a de-facto notion of optimality in such settings. It is well-known that a stable and feasible matching need not exist in the presence of lower quotas. We address this issue by considering an alternative to stability namely popularity. We show that every instance that admits a feasible matching also admits a popular matching. We present an efficient algorithm to compute a maximum cardinality popular matching.
    
    This is joint work with Prajakta Nimbhorkar (Chennai Mathematical Institute) and is accepted for publication at FSTTCS 2017 (to be held in Kanpur in December 2017). The talk will be self-contained.



82. Title : Complexity measures of Boolean functions
    Speaker : Swagato Sanyal, NUS & NTU Singapore
    Date, Time & Venue : Mon, Dec 4, 2017, 11:00 AM - Turing Hall
    [Abstract]

    This talk is cross-listed as a department seminar.



83. Title : A Distributed Conductance Testing Algorithm
    Speaker : Yadu Vasudev, IIT Madras
    Date, Time & Venue : Thu, Nov 23, 2017, 3:00 PM - Turing Hall
    [Abstract]

    We study property testing problems in the distributed CONGEST model. In particular, we look at the problem of testing whether a graph has conductance at least $Phi$ or is $epsilon$-far from having conductance at least $Phi^2$ in the CONGEST model. In the classical property testing model, there is a algorithm for testing conductance of bounded-degree graphs with query complexity $sqrt{n}$. We show that for graphs with arbitrary degree there is an $O(log n)$ round algorithm for testing algorithm in the CONGEST model. In fact, we show that the algorithm works even when the size of the graph is not known apriori. We also prove a matching lower bound for the problem.



84. Title : Distributed Scheduling for Adhoc Networks through Efficient Sampling of Independent Sets
    Speaker : Peruru Subrahmanya Swamy, EE Dept, IIT Madras
    Date, Time & Venue : Tue, Oct 24, 2017, 4:00 PM - Turing Hall
    [Abstract]

    In this work, we design distributed link scheduling algorithms for large adhoc networks. We model the interference in the adhoc network using a graph, and the set of independent sets of the graph constitute the interference-free schedules. Under this setting, we propose two classes of scheduling algorithms that generate interference-free schedules by appropriately sampling the independent sets: (i) Gibbs sampling based schedulers (ii) Greedy sampling based schedulers. The Gibbs sampling based algorithms with appropriately chosen potentials maximize the throughput, and are suited for networks with high data-rate requirements. However, the problem of computing these potentials is NP-hard. One of our key contributions is to propose an free energy approximations based framework to learn the potentials of the Gibbs distribution. Greedy sampling based algorithms offer a good trade off between the throughput and the delay, and are suited for delay-sensitive applications. In particular, we prove that they support a constant fraction of the maximum throughput with a constant delay. Further, the parameters of these greedy algorithms can be easily computed unlike the Gibbs sampling based algorithms.



85. Title : On Depth Five Arithmetic Circuits with Sum and Powering Gates
    Speaker : Raghavendra Rao B V, IIT Madras
    Date, Time & Venue : Tue, Sep 19, 2017, 4:00 PM - Turing Hall
    [Abstract]

    It is known that over fields of large size, any homogeneous degree d polynomial f computed by an arithmetic circuit of size s can be computed by depth five circuits with sum and powering gates of size 2^sqrt(n log d log s log n). In this talk we will focus on depth five circuits with sum and powering gates. We show that any homogeneous depth five circuit with sum and powering gates and restricted middle fan-in computing the product of n variables x_1x_2... x_n requires a top fan-in of 2^(Omega(n)). Our proof involves upper bounding the dimension of projected multilinear derivatives of powers of projections of power symmetric polynomials. This is a joint work with Christian Engels and Karteek Sreenivasaiah.



86. Title : An Efficient Certificateless Proxy Re-Encryption Scheme without Pairing
    Speaker : Arinjitha Paul, IIT Madras
    Date, Time & Venue : Fri, Sep 15, 2017, 11:00 AM - Turing Hall
    [Abstract]

    Proxy re-encryption (PRE) is a cryptographic primitive introduced by Blaze, Bleumer and Strauss to provide delegation of decryption rights. PRE allows re-encryption of a ciphertext intended for Alice to a ciphertext for Bob via a semi-honest proxy, who should not learn anything about the underlying message. In 2003, Al-Riyami and Patterson introduced the notion of certificateless public key cryptography which offers the advantage of identity-based cryptography without suffering from the key escrow problem. The existing certificateless PRE (CLPRE) schemes rely on costly bilinear pairing operations. In ACM ASIA-CCS SCC 2015, Srinivasan et al. proposed the first construction of a certificateless PRE scheme without resorting to pairing in the random oracle model. However, in this work, we demonstrate a flaw in the CCA-security proof of their scheme. Also, we present the first construction of a CLPRE scheme without pairing which meets CCA security under the computational Diffie-Hellman hardness assumption in the random oracle model.
    
    This is joint work with S.Sharmila Deva Selvi and C. Pandu Rangan, and is accepted at Eleventh International Conference on Provable Security (ProvSec 2017).



87. Title : Building Arithmetic Circuits over Read-Once Formulas
    Speaker : Ramya C., IIT Madras
    Date, Time & Venue : Thu, Aug 31, 2017, 2:00 PM - Turing Hall
    [Abstract]

    This is cross-listed as a PhD Seminar.



88. Title : Load Balancing on Graphs with "Smart" Loads
    Speaker : William Kumar Moses Jr., IIT Madras
    Date, Time & Venue : Wed, Aug 30, 2017, 3:00 PM - Turing Hall
    [Abstract]

    This is cross-listed as a PhD Seminar



89. Title : Alternation, Degree and Sensitivity : New Bounds and Super-linear Gaps
    Speaker : Krishnamoorthy Dinesh, IIT Madras
    Date, Time & Venue : Tue, Aug 29, 2017, 2:00 PM - Turing Hall
    [Abstract]

    This is cross-listed as a PhD Seminar.



90. Title : On Weak-Space Complexity over Complex Numbers
    Speaker : Raghavendra Rao B V, IIT Madras
    Date, Time & Venue : Tue, Aug 22, 2017, 4:00 PM - Turing Hall
    [Abstract]

    Two decades ago, Blum, Shub and Smale (BSS) proposed an algebraic variant of Turing Machines where tape cells can store real or complex numbers. In this talk, we give a brief overview of the BSS model of computation and complexity classes. Defining right notion of space is a challenging and an unfinished task for the BSS model of real computation. We consider the of weak-space defined by Nauraois (2007). For weak-space bounded, division-free computations over BSS machines over complex numbers with =?0 tests, we show the following: 1) The Boolean part of the weak log-space class is contained in the deterministic log-space, i.e. BP(LOGSPACE_W)subseteq DLOG. 2) There is a set Lin NC^1_C that cannot be decided by any deterministic BSS machine whose weak-space is bounded above by a polynomial in the input length, i.e., NC^1_C otsubseteq PSPACE_W. This is a joint work with Pushkar Joglekar and Siddhartha Sivakumar.



91. Title : Derandomizing Isolation in the Space-Bounded setting
    Speaker : Gautam Prakriya, University of Wisconsin-Madison
    Date, Time & Venue : Thu, Aug 10, 2017, 2:00 PM - Turing Hall
    [Abstract]

    Isolation is the process of singling out a solution to a problem that may have many solutions. It plays an important role in the design of parallel algorithms where it allows us to ensure that multiple parallel processes all work towards the same global solution. For example the best parallel algorithms for finding perfect matchings in graphs hinge on isolations for this reason. Isolations are also an ingredient in sequential algorithms for NP complete problems like Hamiltonicity. In the algebraic setting Isolations help avoid cancellations and allow us to reduce multivariate polynomial identity testing to univariate polynomial identity testing. All of these algorithms are randomized, and the only reason is the use of the Isolation Lemma - that for any set system over a finite universe, a random assignment of small integer weights to the elements of the universe has a high probability of yielding a unique set of minimum weight in the system.
    
    This talk is about the possibility of deterministic isolation in the space-bounded setting. The question is: Can one always make the accepting computation paths of nondeterministic space-bounded machines unique without changing the underlying language and without blowing up the space by more than a constant factor? I will present some partial results towards the resolution of this question, obtained jointly with Dieter van Melkebeek.



92. Title : Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs
    Speaker : Saikrishna Badrinarayanan, University of California, Los Angeles (UCLA)
    Date, Time & Venue : Tue, Aug 8, 2017, 3:00 PM - Turing Hall
    [Abstract]

    We focus on achieving universally composable (UC) secure computation using hardware setup assumptions - specifically, using physically unclonable functions (PUFs). Briefly, a PUF is a hardware object that can not be cloned and, given any input, outputs a uniformly random string. Previous work showed the feasibility of unconditional UC-secure two party computation if adversarial PUFs are stateless and an impossibility result if they are stateful. In this work, we go beyond this seemingly tight result by allowing any adversary to create stateful PUFs with an a-priori bounded state. This is also motivated by practical scenarios, where the size of a physical object may be used to compute an upper bound on the size of its memory.
    
    We also introduce a new model where any adversary is allowed to create a malicious PUF that may encapsulate other (honestly generated) PUFs within it, such that the outer PUF has oracle access to all the inner PUFs. Similar adversaries have previously also been considered in other settings - for example, in the tamper-proof hardware token model. We note that all previous UC secure constructions based on PUFs suffer from explicit attacks in this stronger adversarial model.
    
    In both these models, we construct unconditional UC-secure protocols for any two party functionality.
    
    This is based on joint work with Dakshita Khurana, Rafail Ostrovsky and Ivan Visconti.



93. Title : New results and techniques for finding min-cuts in the CONGEST Model
    Speaker : Mohit Daga, IIT Madras
    Date, Time & Venue : Wed, Aug 2, 2017, 3:00 PM - Turing Hall
    [Abstract]

    This is cross-listed as an MS Seminar.



94. Title : Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
    Speaker : Santhoshini V, IIT Madras
    Date, Time & Venue : Tue, Jul 25, 2017, 4:00 PM - Turing Hall
    [Abstract]

    We studied the complexity of estimating the optimum value of a Boolean 2CSP (arity two constraint satisfaction problem) in the single-pass streaming setting, where the algorithm is presented the constraints in an arbitrary order. We give a streaming algorithm to estimate the optimum within a factor approaching 2/5 using logarithmic space, with high probability. This beats the trivial factor 1/4 estimate obtained by simply outputting 1/4 th of the total number of constraints.
    
    The inspiration for our work is a lower bound of Kapralov, Khanna, and Sudan (SODA 2015) who showed that a similar trivial estimate (of factor 1/2) is the best one can do for Max CUT. This lower bound implies that beating a factor 1/2 for Max 2CSP, in particular, to distinguish between the case when the optimum is m/2 versus when it is at most (1/4+ eps) m, where m is the total number of constraints, requires polynomial space. We complement this hardness result by showing that one can distinguish between the case in which the optimum exceeds (1/2 + eps)m and the case in which it is close to m/4.
    
    We also prove that estimating the size of the maximum acyclic subgraph of a graph, when its edges are presented in a single-pass stream, within a factor better than 7/8 requires polynomial space.
    
    The talk will not assume any prior knowledge in the area.
    The talk is based on a joint work Venkatesan Guruswami and Ameya Vellingker last summer at CMU as an SN Bose scholar and the work will be presented in APPROX 2017.



95. Title : Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction
    Speaker : Purnata Ghosal, IIT Madras
    Date, Time & Venue : Tue, Jul 18, 2017, 4:00 PM - Turing Hall
    [Abstract]

    Abstract. We initiate the study of polynomials parameterized by degree by arithmetic circuits of small syntactic degree. We define the notion of fixed parameter tractability and show that there are families of polynomials of degree $k$ that cannot be cannot be computed by homogeneous depth four $Sigma Pi^{sqrt{k}} Sigma Pi^{sqrt{k}}$ circuits. Our result implies that there is no parameterized depth reduction for circuits of size $f (k)poly(n)$ such that the resulting depth four circuit is homogeneous.
    
    We show that testing identity of depth three circuits with syntactic degree $k$ is fixed parameter tractable with $k$ as the parameter. Our algorithm involves an application of the hitting set generator given by Shpilka and Volkovich [APPROX-RANDOM 2009]. Further, we show that our techniques do not generalize to higher depth circuits by proving certain rank-preserving properties of the generator by Shpilka and Volkovich.
    
    This is based on a joint work with Om Prakash and Raghavendra Rao. The work will be presented at COCOON 2017



96. Title : Algebraic Weighting Schemes and the NL vs UL Problem
    Speaker : Madhuri R., IIT Madras
    Date, Time & Venue : Tue, Jun 20, 2017, 2:00 PM - BSB 361
    [Abstract]

    This is cross-listed as an MS Seminar.



97. Title : Study of Scheduling with Machine Availability Constraints
    Speaker : Sharmili N Murthy, IIT Madras
    Date, Time & Venue : Thu, Jun 8, 2017, 2:00 PM - BSB 361
    [Abstract]

    This is crosslisted as an MS Seminar.



98. Title : Greedy Tree Packaging: History and Applications
    Speaker : Mohit Daga, IIT Madras
    Date, Time & Venue : Thu, Mar 30, 2017, 4:00 PM - BSB 361
    [Abstract]

    We will discuss an interesting notion of greedy tree packaging introduced by Karger in STOC 96 with applications in finding cuts in graphs. The idea, quite simply put, is to construct a number of trees greedily and give guarantees with respect to the min cut and the edges in the greedy trees constructed. Thorup et al. in STOC 01 improved the analysis and showed that if there are a specific number of greedy trees constructed then one of them passes through a min-cut only once. In this talk, we will introduce tree packaging and discuss the important Chernoff bound style technique of pessimistic estimation used for the analysis. We will also give the use cases of tree packaging in dynamic connectivity [Thorup et al., STOC 01], minimum k-way connectivity [Thorup et al., STOC 08] and distributed connectivity [Nanongkai et al., DISC 14].



99. Title : Popularity in the Generalized Hospital Residents Setting
    Speaker : Amit Rawat, IIT Madras
    Date, Time & Venue : Wed, Mar 15, 2017, 3:00 PM - BSB 361
    [Abstract]

    This is cross listed as an MS Seminar.



100. Title : Frequent-Itemset Mining using Locality-Sensitive Hashing
     Speaker : Rameswar Pratap, IIIT Bangalore
     Date, Time & Venue : Wed, Mar 15, 2017, 12:00 PM - BSB 361
     [Abstract]

     Frequent Itemset Mining is one of the most well known techniques to extract knowledge from data. The Apriori algorithm is a classical algorithm for the frequent itemset mining problem. A significant bottleneck in Apriori is the number of I/O operation involved, and the number of candidates it generates. In our work, we investigate the role of LSH techniques to overcome these problems, without adding much computational overhead. We propose randomized variations of Apriori that are based on asymmetric LSH defined over Jaccard similarity and Hamming distance.



101. Title : A Dichotomy Theorem for Labelled Undirected Reachability
     Speaker : Vidhya Ramaswamy, IIT Madras
     Date, Time & Venue : Fri, Feb 24, 2017, 4:00 PM - BSB 361
     [Abstract]

     Fix an algebraic structure (A, *). Given a graph G=(V, E) whose edges are labeled with elements from A, two nodes s and t, and a subset F of A, the A-Reach problem asks if there is a path p (need not be simple) from s to t whose yield (result of the operation in the ordered set of the labels of the edges constituting the path) is in F. On the complexity frontier of this problem, we show the following results.

     1. When A is a group whose size is polynomially bounded in the size of the graph (hence equivalently presented as a multiplication table at the input), and the graph is undirected, the A-Reach problem is in L. Building on this, using a decomposition (Beaudry, Lemieux and Therein, 1997), we show that, when A is a fixed quasi-group, and the graph is undirected, the A-Reach problem is in L. In contrast, we show NL-hardness of the problem over bidirected graphs, when A is a matrix group over rational numbers. When A is a fixed aperiodic monoid, we show that the problem is NL-complete.
     2. As our main theorem, we prove a dichotomy for graphs labelled with fixed aperiodic monoids by showing that for every fixed aperiodic monoid A, the A-Reach problem is either in L or is NL-complete.
     3. We show that there exists a monoid M, such that the reachability problem in general DAGs can be reduced to A-Reach problem for planar non-bipartite DAGs labelled with M. In contrast, we show that if the planar DAGs that we obtain above are bipartite, the problem can be further reduced to reachability testing in planar DAGs and hence is in UL.

     (This is joint work with K.S. Sunil and Jayalal Sarma and is accepted for presentation at LATA 2017)


102. Title : Learning Algorithms for Sparsely Oriented Circuits
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Tue, Feb 21, 2017, 4:00 PM - Meeting Room 1
     [Abstract]

     In this talk we look into learning functions which are computed by circuits whose non-monotonicity is limited. The main objective in learning given blackbox access to a function f from a specific family of functions, is to come with a hypothesis h which agrees with f on an epsilon fraction of inputs, with minimal number of queries. Bshouty and Tamon (1996) came up with a learning algorithm for learning family of monotone functions based on the low-degree learning algorithm of Linial, Mansour and Nisan (1993). A function is said to be monotone if if it is computed by a monotone circuit, i.e, circuits without negations. The natural next step is to study learning problems for non-monotone circuits. A well studied notion of non-monotonicity is to limit the number of negation gates allowed in the circuit computing f.
     
     In this talk, we would first see a learning algorithm of Blais et. al (2014) which established a learning algorithm for functions computed by limited non-monotone circuits where the non-monotonicity is parameterized by the number of negations in the circuit. We then show how to obtain a learning algorithm for functions computed by limited non-monotone circuits where the non-monotonicity is parametrized with a new parameter called orientation. We will recall a characterization of minimal orientation of a function proved by Koroth and Sarma (2014) and then use this characterization to obtain a learning algorithm from the learning algorithm of Blais et. al.
     
     On the lower bounds front, we will outline a bound obtained by Blais et al (2014) matching their learning algorithm. We will also see the intuition behind their lower bound strategy, which is based on hardness amplification developed by Feldman et. al (2011) using a specific Fourier analytic property of Boolean functions called noise sensitivity . Based on this intuition and our characterization of orientation we outline a strategy for obtaining learning lower bounds for functions of limited orientation. We then show some major hurdles in implementing our strategy.



103. Title : LTL can be more succinct
     Speaker : Sreejith A.V., University of Warsaw, Poland
     Date, Time & Venue : Tue, Feb 14, 2017, 2:30 PM - BSB 361
     [Abstract]

     This is cross listed as a department seminar.



104. Title : Linear Sketching and One-way Communication
     Speaker : Swagato Sanyal, TIFR Mumbai
     Date, Time & Venue : Tue, Feb 7, 2017, 3:00 PM - BSB 361
     [Abstract]

     Linear sketch complexity of a Boolean function f on a set of n inputs, introduced by Kannan, Mossel and Yaroslavtsev, is, in informal terms, the smallest integer d such that the value of the function can be concluded with high probability from the evaluation of d random F_2-linear functions (or parities) of the input. One-way communication complexity of the function F(x,y):=f(x+y) (+ denotes the bit-wise xor of two strings here) is, in informal terms, the minimum amount of communication needed between two players (popularly referred to as Alice and Bob) each of whom holds only a part of the full input (x,y), and who wish to jointly compute F(x,y) by exchanging one message.
     
     Linear sketch complexity of a Boolean function f can be seen to upper bound the one-way communication complexity of the function F(x,y):=f(x+y) (+ denotes the bit-wise xor of two strings here). This is because given a cheap linear sketching, the players of the communication game can simulate it with communication comparable to the cost of the sketch. Kannan et al. conjectured that linear sketch complexity is also a lower-bound on the complexity of this communication problem. In other words, linear sketch complexity characterizes the complexity of the communication problem. The motivation of this conjecture comes from the observation that all known communication protocols are obtained from some underlying linear sketching. The authors proved a similar statement when the inputs are sampled from uniform distribution. We improve on the parameters of their result in this work. Our proof uses Fourier analysis of Boolean functions and information theory.



105. Title : Two examples of Optimal Algorithms via Randomized Rounding: Multi-Constrained Bandit problem and Column Sparse Packing Programs
     Speaker : Karthik Abinav Sankararaman, University of Maryland, College Park
     Date, Time & Venue : Thu, Jan 12, 2017, 2:00 PM - BSB 361
     [Abstract]

     Here we present algorithms for two problems:
     (1) Bandit problem with both local and global constraints: In this work we consider bandit problem with both local constraints and global constraints. For this problem, we give an optimal algorithm via a combination of UCB-style algorithm coupled with randomized rounding. This is based on joint work with Alex Slivkins.
     (2) K-Column Sparse Packing Programs: In this work, we consider the class integer programs known as: k-column sparse packing programs. We consider how to take a fractional solution and describe a randomized rounding to round this to an integer solution. We show that this turns out to give an integer solution whose value matches with the integrality gap. This is based on joint work with Brian Brubach, Aravind Srinivasan, Pan Xu.



106. Title : Branching Program Size Lower Bounds via Projective Dimension
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Fri, Dec 16, 2016, 11:00 AM - BSB 361
     [Abstract]

     This is cross listed from a PhD seminar announcement.



107. Title : Distributed Property Testing Algorithms
     Speaker : Yadu Vasudev, TU Dortmund, Germany
     Date, Time & Venue : Thu, Dec 15, 2016, 2:30 PM - BSB 361
     [Abstract]

     This is cross listed as a CSE department seminar.



108. Title : Space Complexity of Algebraic Reachability : a Dichotomy Theorem
     Speaker : K.S. Sunil, IIT Madras
     Date, Time & Venue : Fri, Dec 9, 2016, 3:00 PM - BSB 361
     [Abstract]

     This is cross listed from a PhD seminar announcement.



109. Title : Deterministic protocols in the SINR model without knowledge of coordinates
     Speaker : William Kumar Moses Jr., IIT Madras
     Date, Time & Venue : Tue, Dec 6, 2016, 4:00 PM - MR1
     [Abstract]

     The SINR (Signal-to-Interference-plus-Noise-Ratio) model is a communication model for ad-hoc wireless networks, which has been extensively studied in recent years. It models the hardness of communication in wireless networks by explicitly considering the interference created by concurrently transmitting devices as well as the ambient noise. Several fundamental communication problems have already been solved in this model, including broadcast, wake-up, and backbone creation. However, previous solutions have been complex and are either randomized or require additional knowledge like the physical coordinates of the devices.
     
     This assumption that we know the physical coordinates of the devices severely restricts the deployment of ad-hoc wireless networks in the real world. Furthermore, deterministic algorithms are preferable to randomized algorithms when the running times are competitive. In this work, we look at how we might remove this dependency on the knowledge of devices locations using an interesting combinatorial idea called a strongly selective family. We develop a useful tool which we then use to deterministically solve various communication problems in this model.
     
     There are 2 takeaways from this talk:

     • You get a feel for the algorithms involved in solving problems on wireless networks.
     • You see an application of the combinatorial tool known as a strongly selective family.


110. Title : Sum of Products of Read-Once Formulas
     Speaker : Ramya C., IIT Madras
     Date, Time & Venue : Tue, Nov 29, 2016, 4:00 PM - MR1
     [Abstract]

     Polynomials are the most basic objects in algebra. It is natural to ask how to compute polynomials efficiently? That is, given a polynomial we want to understand the number of arithmetic operations needed to compute it. Leslie G. Valiant introduced the notion of arithmetic circuits as a model for computing polynomials and defined algebraic analogues of the classes P and NP - polynomials that are efficiently computable (class VP) and those not known to be efficiently computable (class VNP). While there is a polynomial time algorithm for computing the determinant of a matrix, the permanent (viewed as a polynomial) is not known to be easily computable. In fact, Valiant showed that permanent is VNP-complete and conjectured that permanent cannot be computed by polynomial size arithmetic circuits. Subsequent to Valiants conjecture, proving lower bounds for circuits computing permanent have been of much interest. While the answer to Valiants conjecture seems to be at a distance, we look at restricted classes of arithmetic circuits. A read-once formula(ROF) is a formula in which every input variable appears as a leaf at most once. The polynomial computed by an ROF is called a Read-Once Polynomial(ROP). Observe that ROFs are a subclass of the more general multilinear formulas where every gate in the formula computes a multilinear polynomial. Raz [Journal of the ACM, 2009] showed that any multilinear formula (hence read-once formulas) computing determinant or permanent of an n x n matrix must have size super-polynomial in n. We study limitations of polynomials computed by circuits built over ROFs. In particular, we show
     (i) An exponential (2^{Omega(n/ log n)}) lower bound for sum of ROFs computing an explicit polynomial in VP on 2n variables.
     (ii) An exponential lower bound for depth two arithmetic circuits built over ROFs of unbounded depth computing permanent of an n x n matrix. We have an additional restriction that the number of variables with + gates as a parent in a proper sub formula of the ROF is bounded by sqrt{n}.
     Our proof techniques are built on the measure developed by Kumar et. al.[ACM Transactions on Computation Theory, 2016] and are based on a non-trivial analysis of ROFs under random partitions. Further, our results exhibit strengths and provide more insight into the lower bound techniques introduced by Ran Raz [Journal of the ACM, 2009].
     ------------------------------------------------------------------
     Joint work with B.V.Raghavendra Rao. To appear in FSTTCS 2016.
     



111. Title : Computing on Encrypted Data: Overview and a New Construction
     Speaker : Shweta Agrawal, IIT Madras
     Date, Time & Venue : Tue, Nov 8, 2016, 4:00 PM - BSB 361
     [Abstract]

     In this talk, I will first present a high level overview of some fascinating recent results in cryptography that allow for computing on encrypted data. I will particularly focus on the cryptographic primitive of `functional encryption`, which generalises public key encryption. Functional encryption goes beyond the all or nothing paradigm that binds public key encryption, and allows fine grained access to encrypted data. In functional encryption, a secret key is associated with a circuit C, and ciphertext is associated with some data X and decryption reveals C(X) and nothing else.
     
     In the second part of the talk, I will present some new results, in which we provide a new construction for functional encryption which simultaneously achieves (and in some cases, improves) the best of all parameters known across all functional encryption schemes from standard assumptions -- ciphertext size, number of key requests permitted to the attacker, security definition and function family being supported. We also demonstrate some attacks on existing schemes in stronger but natural usage scenarios than considered by the schemes. The paper is available here.



112. Title : Verifiable Functional Encryption
     Speaker : Saikrishna Badrinarayanan, UCLA, USA
     Date, Time & Venue : Thu, Sep 15, 2016, 2:00 PM - BSB 361
     [Abstract]

     In light of security challenges that have emerged in a world with complex networks and cloud computing, the notion of functional encryption has recently emerged. In this work, we show that in several applications of functional encryption (even those cited in the earliest works on functional encryption), the formal notion of functional encryption is actually not sufficient to guarantee security. This is essentially because the case of a malicious authority and/or encryptor is not considered. To address this concern, we put forth the concept of verifiable functional encryption, which captures the basic requirement of output correctness: even if the ciphertext is maliciously generated (and even if the setup and key generation is malicious), the decryptor is still guaranteed a meaningful notion of correctness which we show is crucial in several applications.
     We give a general compiler from any functional encryption scheme into a verifiable functional encryption scheme with the only additional assumption being the Decision Linear Assumption over Bilinear Groups (DLIN). We also give a generic compiler in the secret-key setting for functional encryption which maintains both message privacy and function privacy. Our positive results are general and also apply to other simpler settings such as Identity-Based Encryption, Attribute-Based Encryption and Predicate Encryption. We also give an application of verifiable functional encryption to the recently introduced primitive of functional commitments.
     Finally, in the context of indistinguishability obfuscation, there is a fundamental question of whether the correct program was obfuscated. In particular, the recipient of the obfuscated program needs a guarantee that the program indeed does what it was intended to do. This question turns out to be closely related to verifiable functional encryption. We initiate the study of verifiable obfuscation with a formal definition and construction of verifiable indistinguishability obfuscation.
     This is based on joint work with Vipul Goyal, Aayush Jain and Amit Sahai.



113. Title : Network Oblivious Transfer
     Speaker : Srinivasan Raghuraman, MIT, USA
     Date, Time & Venue : Mon, Aug 29, 2016, 2:00 PM - BSB 361
     [Abstract]

     Motivated by the goal of improving the concrete efficiency of secure multiparty computation (MPC), we study the possibility of implementing an infrastructure for MPC. We propose an infrastructure based on oblivious transfer (OT), which would consist of OT channels between some pairs of parties in the network. We devise information-theoretically secure protocols that allow additional pairs of parties to establish secure OT correlations using the help of other parties in the network in the presence of a dishonest majority. Our main technical contribution is an upper bound that matches a lower bound of Harnik, Ishai, and Kushilevitz (Crypto 2007), who studied the number of OT channels necessary and sufficient for MPC. In particular, we characterize which n-party OT graphs G allow t-secure computation of OT correlations between all pairs of parties, showing that this is possible if and only if the complement of G does not contain the complete bipartite graph K_{n-t,n-t} as a subgraph.
     Joint work with Ranjit Kumaresan (MIT) and Adam Sealfon (MIT).



114. Title : Tensor rank of homogeneous formulas
     Speaker : Mrinal Kumar, Rutgers University
     Date, Time & Venue : Mon, Jul 4, 2016, 3:00 PM - BSB 361
     [Abstract]

     A multivariate polynomial P is said to be set-multilinear if there is a partition of the set X of variables into X1, X2, ..., Xd such that ever monomial with a non-zero coefficient in P contains exactly one variable from each Xi. For instance, the determinant, the permanent are set multilinear with each Xi being the set of variables in a row/column. As we will see set-multilinear polynomials are in a natural one to one correspondence with tensors.
     In a surprising result, Raz showed that for an appropriate range of parameters, if a set-multilinear polynomial is computable by a small formula, then the tensor rank of the associated tensor is not too large. Thus, constructing explicit tensors of nearly full rank is a possible approach to proving arithmetic formula lower bounds, an extremely sought-after problem in arithmetic circuit complexity.
     In this talk, we will see an extremely short and simple proof of Razs result for homogeneous formulas, with substantially improved parameters.
     Based on joint work with Suryajith Chillara, Ramprasad Saptharishi and V. Vinay.



115. Title : Parallel algorithms for Biconnnected Components
     Speaker : Meher Chaitanya, IIIT Hyderabad
     Date, Time & Venue : Tue, Feb 9, 2016, 4:00 PM - CS34
     [Abstract]

     In this talk I will present an algorithm for finding the Biconnected components of a given graph. Our algorithm is based on evidence that finding the bridges of a graph is usually easier and faster in the parallel setting. We use this property to first decompose the graph into independent and maximal 2-edge-connected subgraphs. To identify the articulation points in these 2-edge connected subgraphs, we convert this into a problem of finding the bridges on an auxiliary graph. It is interesting to note that during the conversion process, the size of the graph may increase. However, we show that this small increase in size and the run time is offset by the consideration that finding bridges is faster in a parallel setting. Our algorithm is on average 2.45x faster than the best known current algorithms and nearly 10x faster than the serial Hopcroft-Tarjan algorithm. We will end the talk by providing some applications where the Biconnected component decomposition is useful.
     
     Speaker Bio: Meher Chaitanya is currently a M.S. by research student at the International Institute of Information Technology, Hyderabad, where he is affiliated to the Center for Security Theory and Algorithmic Research. Prior to this he was a software engineer at Nvidia. His current areas of research are studying various ways of separating graphs, and their cost-benefit analysis with respect to problems such as shortest paths and betweenness centrality.
     
     Host : Meghana Nasre



116. Title : Algorithms for Stable Instances of Graph Partitioning problems
     Speaker : Aravindan Vijayaraghavan, Northwestern University
     Date, Time & Venue : Tue, Dec 29, 2015, 11:00 AM - BSB 361
     [Abstract]

     We investigate the notion of stability that was proposed by Bilu and Linial for studying practically interesting instances of graph partitioning and clustering problems. Such instances have stable optimal solutions that do not change upon small perturbations of the instance (multiplicative perturbations to the edge weights up to some factor). I will show how we can obtain exact polynomial-time algorithms for stable instances of Max Cut and Minimum Multiway cut. Our algorithms are based on a structural result showing that certain LP or SDP relaxations of these problems become integral under sufficient stability. I will end this talk with some directions for future work. Based on joint work with Konstantin Makarychev and Yury Makarychev



117. Title : Balanced Allocation: Patience is not a Virtue
     Speaker : William Kumar Moses Jr., IIT Madras
     Date, Time & Venue : Mon, Dec 28, 2015, 3:00 PM - BSB 361
     [Abstract]

     Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm Greedy[d] of Azar et al. places each ball by probing d > 1 random bins and placing the ball in the least loaded of them. It ensures a maximum load that is exponentially better than the strategy of placing each ball uniformly at random. Vocking showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at an additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that combines the simplicity of Greedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d] is to probe until a different bin size from the first observation is located, then place the ball. Although the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires only d probes on average per ball (in both the standard and the heavily-loaded settings). Thus the number of probes is no greater than either that of Greedy[d] or Left[d]. More importantly, we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the standard and heavily-loaded settings. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice.



118. Title : Reed Muller codes achieve capacity on erasure channels
     Speaker : Vishvajeet Nagargoje, IIT Madras
     Date, Time & Venue : Tue, Sep 22, 2015, 4:00 PM - BSB 361
     [Abstract]

     Transmission of information reliably and efficiently across channels is one of the fundamental goals of coding and information theory. In this respect, efficiently decodable deterministic coding schemes which achieve capacity provably have been elusive until as recent as 2008, even though schemes coming close to doing so in practice existed for long.
     
     Arikans polar codes revived the interest in the problem, and in that respect, we look at recent results by Urbanke et al. which show that codes with sufficient symmetry achieve capacity on erasure channels under maximum a posteriori decoding. The claim follows from the following observations :
     

     • Extrinsic information transfer(EXIT) functions capture the probability of error under MAP decoding
     • EXIT functions are monotone and have sharp thresholds
     • The code being 2-transitive implies that the all EXIT functions are equal to the average EXIT function.
     • inally the area theorem for the average EXIT function concludes that threshold occurs at $epsilon$ = 1 - R

     It is quite remarkable to see how Urbanke and his group use complexity theoretic results in boolean function analysis to prove their claim. The techniques they use apply to any sequence of codes that have increasing block lengths and are doubly transitive. This is a rare occurrence in information theory where symmetry alone implies optimal performance. One of the oldest and most widely used codes - Reed Muller codes are doubly transitive if we give evaluations at all points in the underlying field. Polar codes are doubly transitive too and we thus have a different proof of the fact that they achieve capacity on these channels.
     
     (Summer project with Prof. Prahladh Harsha and Prof. Vinod Prabhakaran, School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai.)


119. Title : Reversible Pebbling on Trees
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Jul 28, 2015, 4:00 PM - BSB 361
     [Abstract]

     Various forms of pebble games played on graphs are used to derive resource(space, depth, alternations)-efficient generic algorithms (algorithms that work for a large class of problems). In fact, some of the best algorithms that we know can be derived from pebble games. The reversible pebble game is used to derive space-efficient algorithms for reversible computation (Bennet 1979). Recently, Siu Man Chan (Chan 13) showed that reversible pebbling number, Raz-Mckenzie pebble number, and Dymond-Tompa pebble number of any DAG are the same. We consider two questions:-
     - Is reversible pebbling number related to parameters other than various pebbling numbers?
     - Computing irreversible pebbling numbers of DAGs is PSPACE-complete. But, we know that irreversible pebbling number of trees can be computed in polynomial time. Siu Man Chan has showed that computing reversible pebbling number of DAGs is PSPACE-complete. What is the complexity of computing reversible pebbling number of trees?
     
     We answer both questions by showing that reversible pebbling number of any tree is just one more than its edge-rank coloring number. The edge-rank coloring of trees is computable in polynomial time.
     
     (This is joint work with Jayalal Sarma and Saurabh Sawlani, and has been accepted for presentation at COCOON 2015)



120. Title : Leader Election in Sparse Dynamic Networks with Churn
     Speaker : Sumathi S., IIT Madras
     Date, Time & Venue : Tue, May 19, 2015, 4:00 PM - BSB 361
     [Abstract]

     We investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which upto a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighborhood and thus hinder their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability and well-connectedness to establish a leader that can maintain good communication with rest of the nodes. Since the dynamics could change eventually, it is also essential to re-elect a new leader whenever the current leader has either left the network or is not well-connected with rest of the nodes. In such re-elections, care must be taken to avoid premature and spurious leader election resulting in more than one leader present in the network at the same time.
     
     We assume a broadcast based communication model in which each node can send up to $O(log^3 n)$ bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in $O(log n)$ rounds, detect and reachconsensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leaders ability to communicate is unhealthy, a new leader is re-elected in a further $O(log^2 n)$ rounds. Our running times hold with high probability, and, furthermore, we are guaranteed with high probability that there is at most one leader at any time.



121. Title : Classifying Connected $f$-Factor Problems based on $f$
     Speaker : Rahul C.S., IIT Madras
     Date, Time & Venue : Tue, May 12, 2015, 3:00 PM - BSB 361
     [Abstract]

     A graph is a mathematical structure widely used for modeling networks and in many other applications. Finding subgraphs satisfying degree and connectivity constraints is a well studied problem over many years. Given an undirected graph G=(V,E) having n vertices and a function f:V->mathbb{N}$, an $f$-factor H is a spanning subgraph such that degree of each vertex v in H is $f(v)$, for every v in V. We consider the problem of computing an $f$-factor which is connected. We observe that the computational hardness of the problem vary depending on the smallest value in the range of $f$. When $f(v)$>=c for every v in V and some constant c, the problem is shown to be NP-Complete. When $f(v)$>=|V|/2 for every v in V, the problem is polynomial time solvable. Thus, when the lower bound on the range of $f$ is too small the problem is hard and when it is too large, the problem is easy. Motivated by this observation, we attempt to explore the codomain of $f$ and understand how the hardness of the problem vary along with change in $f$. Further we come up with an algorithm and a hardness result.
     
     We had shown that the problem of computing a connected $f$-factor is hard even when $f(v)$>= n^{1-epsilon} for some constant 0= n/3 for every v in V. In this talk we present a polynomial time algorithm for computing connected $f$-factor where $f(v)$>= n/c for every v in V and some constant c. The same algorithm can be used to solve for the case where $f(v)$>= n/polylog(n) for every v in V in time n^{O(polylog(n))}$. This means the problem cannot be NP-Complete unless Exponential Time Hypothesis(ETH) is false. Similarly, we give a subexponential time reduction from Hamiltonian cycle problem where $f(v)$>= n/{log^{1+epsilon}} n(epsilon>0) for each vertex v. This implies there does not exist a polynomial time algorithm for the problem unless ETH is false. Thus, this infinite class of problems parameterized by $epsilon$ is in NP-Intermediate.



122. Title : Finding Odd Cycle Transversals in Perfect Graphs
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Mar 31, 2015, 3:00 PM - BSB 361
     [Abstract]

     Abstract: Given an undirected simple graph, a set of vertices is an odd cycle transversal if it has at least one vertex from every odd cycle. Equivalently, the graph obtained by deleting such a set is bipartite. Odd cycle transversals generalize the classical vertex covers in a natural way. One of the largest classes of graphs on which a minimum vertex cover can be obtained in polynomial time is the class of perfect graphs. Perfect graphs, introduced by Claude Berge, link various areas of mathematics like graph theory, combinatorial optimization, mathematical programming,information theory, geometry, convexity theory and polyhedral theory. Perfect graphs also have nice algorithmic properties. They can be recognized in polynomial time and are amenable to polynomial-time algorithms based on semi-definite programming. However, finding a minimum odd cycle transversal is NP-hard on perfect graphs. We study the complexity of this problem on weighted perfect graphs and show that it admits a 2-approximation. Our algorithm is obtained through appealing to the Lovasz theta function computation and the polyhedral characterization of perfect graphs based on the vertex cover polytope description. We then show hardness results in the approximation and parameterized settings.



123. Title : Longest Path, Reachability and Max-poly Weighting Schemes
     Speaker : Saurabh Sawlani, IIT Madras
     Date, Time & Venue : Tue, Mar 24, 2015, 2:00 PM - BSB 361
     [Abstract]

     (This is an MS Seminar)
     The Longest Path problem on graphs is an important problem in the context of computational complexity theory. The problem is NP-complete for general graphs, while for directed acyclic graphs, it has a polynomial-time algorithm, and it has important implications for scheduling problems. For smaller subclasses of graphs, the problem has interesting implications in relation to space complexity classes. A weighting scheme on a graph G(V;E), is an assignment of non-negative weights to each edge e in E. A weighting scheme is called max-unique with respect to a source vertex s, if for every vertex v in V , there is at most one path of maximum weight from s to v in G. Limaye, Mahajan and Nimbhorkar (2009) proposed an unambiguous non-deterministic log-space algorithm which solves the Longest Path Problem on max-unique DAGs with a unique sink. As our main contribution, we improve this result relaxing the restriction of maximum-weight-paths from unique to polynomially many. We do this by employing a three variable inductive counting technique combined with a method of verifying unambiguously. As a main application of our result, we give a reduction from the Reachability problem on general weighted DAGs to the Longest Path problem on single-sink DAGs, while preserving the max-unique/max-poly property of the weighting scheme of the graph. A consequence of this result is that it suffices to construct a max-poly weighting scheme for DAGs to show that NL = UL.



124. Title : A Method to Construct Counterexamples for Greedy Algorithms
     Speaker : Jagadish M., IIT Bombay
     Date, Time & Venue : Thu, Mar 12, 2015, 3:00 PM - BSB 361
     [Abstract]

     Problem solving is the focus of any algorithm design course. Being able to disprove wrong strategies is a critical part of the problem solving process.
     ​We will see a method that is useful for such a task.
     The type of task we are interested in is as follows. We are given an optimization problem P and a greedy algorithm that is purported to solve the problem P. The goal is to construct an instance of P on which the algorithm fails to give the correct answer. Such an instance is called a *counterexample*. We will discuss a method to identify counterexamples for many graph-theoretic problems.



125. Title : Towards Making Space-bounded Non-Determinism Unambiguous
     Speaker : Anant Dhayal, IIT Madras
     Date, Time & Venue : Tue, Feb 24, 2015, 4:00 PM - BSB 361
     [Abstract]

     This is an MS Seminar.



126. Title : New Circuit Lower and Upper Bounds via Combinatorial Arguments
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Feb 24, 2015, 3:00 PM - BSB 361
     [Abstract]

     We study the space complexity of the Tree Evaluation Problem (TEP). This problem was introduced by Cook et. al. to separate the complexity classes P (polynomial-time) and L (logspace). The approach suggested is to consider models of computation that captures larger and larger classes of algorithms solving TEP and prove lower bounds against them. We introduce a restricted form of the well-studied branching program model, called Bitwise Independent Non-deterministic Thrifty Branching Programs (BINTBP), and show that BINTBPs capture the most space efficient algorithms used for solving TEP. We then prove tight lower bounds for BINTBPs essentially showing that currently known algorithms are the best possible ones on the BINTBP model.
     We also study circuit complexity of deciding graph properties (such as Perfect Matching, 2-colourability etc.) on constant-width grid graphs. The objective is to design polynomial-size constant-depth circuits for these problems. For example, adding two n-bit numbers using carry-lookahead logic only takes polynomial (in n) number of gates and constant depth. We show that deciding 2-colourability, existence of perfect matching and deciding if vertex/edge-disjoint paths exist between two designated vertices in constant-width grid graphs can be done using polynomial-size constant depth circuits.



127. Title : Exact and Approximation Algorithms for Computing Connected f-Factors
     Speaker : Rahul C.S., IIT Madras
     Date, Time & Venue : Tue, Feb 17, 2015, 4:00 PM - BSB 361
     [Abstract]

     Given an undirected graph G=(V,E) and a function f:V->N, an f-factor H is a spanning subgraph such that dH(v)=f(v) for every v in V. The problem of computing an f-factor is polynomial time solvable. We consider the problem of computing a connected f-factor. The Hamiltonian cycle problem is a special case of connected f-factor problem. Even when f(v)=d for every v in V and some constant d, the problem is shown to be NP-hard. When f(v)>=|V|/2 for every v in V, the problem is polynomial time solvable. Motivated by the observation that the hardness of the problem vary along with change in f, we attempt to explore the spectrum of values f and come up with a dichotomy result on connected f-factors. Further we come up with exact and approximation algorithms for optimization version and special cases of the same. We use the techniques from the literature to show that the problem of computing connected f-factor is hard even when f(v)>=|V|^(1-ε) for some constant 0<ε<1. At the other end of the spectrum, we come up with algorithms for the problem of computing connected f-factor when f(v)>=|V|/2.5 for every v in V and for the case where f(v)>=|V|/3 for every v in V. Both these algorithms can be extended to solve the optimization versions of the same. As a special case, we consider the metric version of the problem and give a 3-approximation algorithm. For the case where f(v)>=|V|/c for every v and for some constant c, we give a (1+ε)-approximation algorithm.



128. Title : Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
     Speaker : Christian Engels, University Saarland, Germany
     Date, Time & Venue : Tue, Feb 17, 2015, 4:00 PM - BSB 361
     [Abstract]

     In this talk, we will show dichotomy theorems for the computation of polynomials corresponding to evaluation of graph homomorphisms in Valiants model. We are given a fixed graph $H$ and want to find all graphs, from some graph class, homomorphic to this $H$. These graphs will be encoded by a family of polynomials.

     In this talk we give dichotomies for the polynomials for outerplanar graphs, planar graphs and graphs of bounded genus.



129. Title : Tree Path Labelling : an extension of the Consecutive Ones Property
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Feb 3, 2015, 4:00 PM - CS 34
     [Abstract]

     The consecutive ones property associated with 0-1 matrices is very well studied, and the results range from characterizations to canonizations. In this work we consider a natural generalization of the Consecutive Ones Property.

     This is joint work with Anju Srinivasan.



130. Title : Parameterized Analogues of Probabilistic Computation
     Speaker : Ankit Chauhan, IIT Madras
     Date, Time & Venue : Tue, Jan 27, 2015, 4:00 PM - BSB 361
     [Abstract]

     TBA



131. Title : Decremental all-pairs ALL shortest paths
     Speaker : Meghana Nasre, IIT Madras
     Date, Time & Venue : Tue, Jan 20, 2015, 4:00 PM - BSB 361
     [Abstract]

     Given a directed positive edge weighted graph G, we consider the all-pairs ALL shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in G. In the traditional dynamic all-pairs shortest paths problem one is interested in maintaining the distance matrix and possibly one shortest path between every pair of vertices. For this problem Demetrescu and Italiano (JACM 2004) gave an efficient algorithm which relies on the novel concept of locally shortest paths. However, this result does not immediately give an efficient decremental algorithm for the more general problem of all-pairs ALL shortest paths.

     In this talk, we first present the notion of locally shortest paths, their useful properties, and then generalize them to locally shortest path tuples. These tuples form the basis for our decremental all-pairs ALL shortest paths algorithm. We also briefly discuss the application to decremental betweenness centrality, a measure that is widely used for analysis of large complex networks.

     This is joint work with Matteo Pontecorvi and Vijaya Ramachandran and was presented recently at ISAAC 2014.



132. Title : How to Use Bitcoin to Design Fair Protocols
     Speaker : Ranjit Kumaresan, MIT, USA.
     Date, Time & Venue : Fri, Dec 12, 2014, 10:30 AM - CS25
     [Abstract]

     Abstract: We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model.

     One of our main contributions is the definition of an ideal primitive, which we call $mathcal{F}_{mathrm{CR}}^star$ ($mathrm{CR}$ stands for ``claim-or-refund'), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the $mathcal{F}_{mathrm{CR}}^star$ functionality, and is otherwise independent of the Bitcoin ecosystem. We also show an efficient realization of $mathcal{F}_{mathrm{CR}}^star$ that requires only two Bitcoin transactions to be made on the network.

     Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to $mathcal{F}_{mathrm{CR}}^star$ per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.

     This is joint work with Iddo Bentov (Technion). The article may be downloaded from http://eprint.iacr.org/2014/129.pdf



133. Title : Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
     Speaker : Sayan Bhattacharya, IMSc, Chennai
     Date, Time & Venue : Tue, Nov 18, 2014, 2:00 PM - BSB 361
     [Abstract]

     We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in $o(sqrt{m})$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+epsilon)$ approximation in $O(log n/epsilon^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+epsilon)$ approximation in $O(m^{1/3}/epsilon^2)$ {em amortized} time per update, and a $(4+epsilon)$ approximation in $O(m^{1/3}/epsilon^2)$ {em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld~cite{OnakR10}.
     Joint work with Monika Henzinger and Giuseppe F. Italiano. To appear in SODA 2015.



134. Title : Weighing Schemes and NL vs UL Problem - Part II
     Speaker : Saurabh Sawlani, IIT Madras
     Date, Time & Venue : Mon, Nov 17, 2014, 4:00 PM - CS34
     [Abstract]

     For a graph $G(V,E)$ and a vertex $s in V$, a weighting scheme ($w : E to mathbb{N}$) is called a {em max-unique} weighting scheme, if for any vertex $v$ of the graph $G$, there is a unique path of maximum weight from $s$ to $v$. Instead, if the number of paths of maximum weight is bounded by $n^c$ for some constant $c$, then the weighting scheme is called a {em max-poly} weighting scheme. Weight of a path $p$ is the sum of the weights of the edges appearing in $p$.

     In this work, we propose an unambiguous non-deterministic log-space (UL) algorithm for testing reachability in layered DAGs augmented with {em max-poly} weighting schemes. To achieve this, we first reduce reachability in DAGs to the longest path problem for DAGs with a unique source, such that the reduction also preserves the {em max-poly} property of the graph. Using our techniques, we generalize the double inductive counting method in cite{LMN09} where $ul$ algorithms were given for the longest path problem on DAGs with a unique sink and augmented with a {em max-unique} weighting scheme.

     (This is joint work with Anant Dhayal and Jayalal Sarma and it has been accepted for presentation at FSTTCS 2014).



135. Title : Weighing Schemes and NL vs UL Problem - Part I
     Speaker : Anant Dhayal, IIT Madras
     Date, Time & Venue : Fri, Nov 14, 2014, 4:00 PM - CS34
     [Abstract]

     For a graph $G(V,E)$ and a vertex $s in V$, a weighting scheme ($w : E to mathbb{N}$) is called a {em min-unique} weighting scheme, if for any vertex $v$ of the graph $G$, there is a unique path of minimum weight from $s$ to $v$. Instead, if the number of paths of minimum weight is bounded by $n^c$ for some constant $c$, then the weighting scheme is called a {em min-poly} weighting scheme. Weight of a path $p$ is the sum of the weights of the edges appearing in $p$.

     In this work, we propose an unambiguous non-deterministic log-space (UL) algorithm for the problem of testing reachability in layered directed acyclic graphs (DAGs) augmented with a {em min-poly} weighting scheme. This improves the result due to Allender and Reinhardtcite{AR00} where a $UL$ algorithm was given for the case when the weighting scheme is {em min-unique}.

     Our main technique is a triple inductive counting, which generalizes the techniques of (Immerman, Szelepcinyi 1988) and (Allender, Reinheirt 2000), combined with a hashing technique due to cite{FKS84} (also used in cite{GSTV14}). We combine this with a complementary unambiguous verification method, to give the desired UL algorithm.

     (This is joint work with Jayalal Sarma and Saurabh Sawlani and it has been accepted for presentation at FSTTCS 2014. The work will be presented as two different talks with the second half being presented the next day by Saurabh Sawlani).



136. Title : LP Approaches to Clique Transversal in Perfect Graphs
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Sep 2, 2014, 4:00 PM - CS34
     [Abstract]

     Given an undirected simple graph G, a subset T of vertices is an r-clique transversal if it has at least one vertex from every r-clique in G. In this talk, the approximability of the problem on weighted perfect graphs will be discussed.
     (Joint work with Samuel Fiorini, N.S. Narayanaswamy, and Venkatesh Raman)



137. Title : Allocating Jobs to Machines with Load Demands
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Aug 12, 2014, 4:00 PM - CS34
     [Abstract]

     We study a generalization of the max-min allocation problem also known as the Santa Claus problem. We refer to this problem as the max-min allocation problem with demands (MMAD). Here, unlike original max-min scheduling problem, each machine has its own minimum-load requirement. The Input to this problem consists of a set $M$ of $m$ machines with load demands of $T_1, ldots, T_m$, respectively, a set $J$ of $n$ jobs, and a processing time matrix $P_{m imes n}=[p_{ij}]$, where $p_{ij}$ is the time taken by job-$j$ on machine-$i$. The goal is to find a assignment of jobs to machines such that for each machine $m_i$, the sum total of the processing times of the jobs assigned to it is at least $T_i$. Given, the hardness of problem without the demands itself, our focus will be on extit{restricted version} of this problem- $p_{ij}$ the time taken by any job-$j$ on a machine-$i$ is either $0$ or some fixed $p_j$, that is independent of the machine. Our main result here is to show that a natural generalization of the configuration LP has an integrality gap of at most $frac{1}{4}$. We use the technique used by Asadpour, Feige, and Saberi cite{asadpour}, and mainly we show that it does terminate in a polynomial number of iterations. Thus our analysis shows that a solution to the configuration LP (for MMAD and the Santa Claus problem) can be converted into an integral solution in a polynomial number number of iterations. Further, since in polynomial time we can find a non-zero valued variable in the solution to the configuration LP, we have a polynomial time factor 4 approximation algorithm for the MMAD (and the Santa Claus problem). We also point out that the approach of the Bansal-Sviridenko cite{nikhil} is unlikely to work in the case of MMAD.

     (Joint work with Vishal Pandya)



138. Title : Yao s Protocol for Two-Party Computation
     Speaker : Akshayram S., IIT Madras
     Date, Time & Venue : Tue, Aug 5, 2014, 4:00 PM - CS34
     [Abstract]

     In the two-party computation setting, two parties with private inputs x and y wish to jointly compute a function f(x,y). The security requirements are that the output of the protocol must be same as f(x,y) (correctness) and that the parties must learn only f(x,y) and nothing else (privacy). The first general solution to this problem was presented by Andrew Yao in 1986. The protocol has constant round complexity and is secure in the presence of semi-honest adversaries. This seminal result started the field of secure multiparty computation and has served as the basis of many papers in this area. Recently, Lindell and Pinkas gave a complete description of Yaos protocol along with a rigorous proof of security. https://eprint.iacr.org/2004/175.pdf. This talk will be based on the above paper.



139. Title : Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring
     Speaker : Venkatesan Guruswami, CMU, USA.
     Date, Time & Venue : Thu, Jul 31, 2014, 2:30 PM - CS25
     [Abstract]

     This is also a department seminar, cross-listed here.



140. Title : Trading Orientation for Depth Lower Bounds in Boolean Circuits
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Wed, Jul 30, 2014, 4:00 PM - BSB 361
     [Abstract]

     The best circuit size lower bound against an explicit function is only linear. However, exponential lower bounds are known against monotone circuits (circuits that does not use negation gates) computing the Clique function. These have been extended to circuits that use limited number of negation gates. In this talk we will be looking at a new measure of non-monotonicity called weight of orientation. Weight of orientation of a function is the number of negated variables in any DeMorgan circuits (one where NOT gates appear only at leaves) computing it. We show that orientation is a well defined notion for any Boolean function. We can extend this measure to circuits in the following way. A circuit is said to have weight of orientation at most t, if any internal gate computes a function whose weight of orientation is at most t. We show that even one internal gate of non-zero orientation in a circuit computing a monotone function can reduce the depth exponentially. We show that any depth d, weight of orientation at most w circuit computing Clique has dw = Omega(n) thus establishing a trade-of between circuit depth and weight of orientation. Our main tool is a deep connection between circuit depth and communication complexity found by Karchmer and Wigderson. Using this connection Raz and Wigderson showed that monotone depth of Clique is Omega(n). Like Amano Maruoka generalizes the monotone lower bound of Razborov for Clique to limited negation setting our work generalizes the monotone depth lower bound of Raz and Wigderson for Clique to limited weight of orientation circuits. We also show that if you can improve one of our constructions by even an epsilon, one can get that NP does not have Poly Size, PolyLog Depth circuits computing it.

     (This is joint work with Jayalal Sarma)



141. Title : Building above Read-once Polynomials: Identity Testing
     Speaker : Karteek Sreenivasaiah, IMSc, Chennai
     Date, Time & Venue : Mon, Jul 28, 2014, 4:15 PM - BSB 361
     [Abstract]

     Polynomial identity testing (PIT) is the problem of checking if a given arithmetic circuit computes the identically zero polynomial. PIT is a very natural and fundamental problem. In the talk, we will look at a deterministic polynomial time algorithm for a special case of PIT where the input polynomial looks like f_1 g_1 + f_2 g_2 where f_1,f_2,g_1,g_2 are all read-once polynomials. We first show this result for polynomials over the field of rationals and then extend it to other fields. We will then observe that the ideas developed so far immediately generalize to the case when the input polynomial looks like f_1 f_2 f_3...f_p + g_1 g_2 g_3...g_q.

     (Joint work with Meena Mahajan and Raghavendra Rao B.V.)



142. Title : A Linear Size Approximate Distance Oracle for Chordal Graphs
     Speaker : Gaurav Singh, IIT Madras
     Date, Time & Venue : Mon, Jul 28, 2014, 3:00 PM - BSB 361
     [Abstract]

     A Graph is chordal if every cycle of length greater than three has a chord. Chord is an edge joining two non adjacent vertices. We present a distance oracle for chordal graphs. Distance oracle is a data structure that stores information of the distance between vertices of a graph.

     Given a chordal graph G on n vertices we preprocess it in O(n^2) time and space to build a data structure of size O(n) such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices u,v in V(G), we output a distance value d <= d_G(u,v) + 11, where d_G(u,v) is the distance between u and v in G. In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in O(n^2.376) time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We then design an efficient data structure to additively approximate (error of +3) these minimum hitting sets of cliques for all paths in the clique tree. These are then integrated with an efficient data structure to answer LCA queries in rooted trees to yield our distance oracle for a given chordal graph.

     Chordal graphs are often represented by its Clique Tree in very compact and efficient manner. Clique tree is a structure that contains most of the information of the associated chordal graph. We exploit the structural properties of the clique tree to extract the distance information of the associated chordal graph. We keep this information in a data structure that can answer any query of distance between any pair of vertices of graph in constant time.The most impressive feature of our data structure is its constant query time in spite of the fact that it uses only linear space, i.e., it does not store distance between all the pairs of vertices explicitly.

     (This is the MS Seminar, cross listed here).



143. Title : Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
     Speaker : Mrinal Kumar, Rutgers University
     Date, Time & Venue : Fri, Jul 25, 2014, 2:30 PM - CS34
     [Abstract]

     An efficient indexing algorithm for a finite set S is a bijection from {1,2,3, ..., |S|} to S, which is computable in time polynomial in (log |S|). The notion of indexing is closely related to the notions of counting and enumeration of combinatorial objects.

     In this talk, we will see an efficient algorithm for indexing irreducible polynomials over finite fields. The approach is based on a connection between irreducible polynomials and necklaces (equivalence classes of strings under rotation). This has applications in pseudorandomness, and answers an open question of Alon, Goldreich, Hastad and Peralta.

     Joint work with Swastik Kopparty and Michael Saks.



144. Title : Fully Dynamic Algorithms for All-Pair Shortest Paths
     Speaker : Meghana Nasre, IIT Madras
     Date, Time & Venue : Tue, Jul 22, 2014, 4:00 PM - CS34
     [Abstract]

     In this talk we will present a paper by Demetrescu and Italiano (JACM 2004) which gives a fully dynamic algorithm for maintaining all pairs shortest paths (APSP) in a directed graph with non-negative real valued edge weights. Given a graph G = (V, E) and a sequence of updates (consider edge/vertex additions or deletions) the problem is to maintain all pairs shortest path distances efficiently after every update.

     The above mentioned paper gives an algorithm that maintains APSP in amortized time of O(n^2 polylog{n}) per update. The approach relies on the novel idea of defining and maintaining {em locally shortest paths} which are a superset of shortest paths in a graph. In the talk, we will first focus on decremental updates (edge/vertex deletions) and then sketch the modifications required for the fully-dynamic updates.



145. Title : Complexity through L-reachability Lens
     Speaker : K.S. Sunil, IIT Madras
     Date, Time & Venue : Mon, Jul 21, 2014, 3:00 PM - CS34
     [Abstract]

     The talk will be on the complexity theoretic study of the language based reachability problem (L-reach) : Fix a language L. Given a graph whose edges are labelled with alphabet symbols and two special vertices s and t, test if there is path P from s to t in the graph such that the concatenation of the symbols seen from s to t in the path P forms a string in the language L.

     This problem is studied based on different graph classes and different formal language classes. The complexity of L-reachability increases with the power of the formal language class. The results, when L-reachability is used as a lens to study structural complexity is more interesting. There is a language A in log-space for which A–DagReach is NP-complete. Using this, we show that P vs NP question is equivalent to P vs DagReach−1(P) question. This leads to the intriguing possibility that by proving DagReach−1(P) is contained in some subclass of P, we can prove an upward translation of separation of complexity classes.

     (This is a joint work with Balagopal Komarath and Jayalal Sarma. The paper will be appearing in DCFS 2014)



146. Title : Beyond Worst Case Analysis in Algorithm Design
     Speaker : Aravindan Vijayaraghavan, Northwestern University
     Date, Time & Venue : Fri, Jun 20, 2014, 11:00 AM - BSB 361
     [Abstract]

     For many real world computational tasks there is a significant gap between our theoretical and practical understanding. While the theory of NP-completeness and worst case analysis tells us that many interesting computational problems are NP-hard in the worst case, practitioners in areas like machine learning and computer vision have made significant progress in solving such theoretically hard problems. Bridging this gap is a significant challenge for modern day theoretical computer science. In this talk, I will discuss three paradigms that go beyond traditional worst-case analysis in our search for algorithms with better provable guarantees: (realistic) average-case analysis, smoothed analysis and instance stability. I will use these paradigms to show much better guarantees for two classes of problems in very different domains: (a) graph partitioning, and (b) unsupervised learning of probabilistic models.



147. Title : Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products
     Speaker : Saikrishna B., IIT Madras
     Date, Time & Venue : Tue, May 20, 2014, 4:00 PM - CS34
     [Abstract]

     Predicate encryption is a new paradigm in public key cryptography that generalizes identity based encryption. In predicate encryption, secret keys correspond to predicates and ciphertexts are associated with attributes. A secret key corresponding to a predicate f can be used to decrypt a ciphertext associated with attribute I if and only if f (I ) = 1.
     
     Katz, Sahai and Walters constructed a scheme for predicates corresponding to the evaluation of inner products which in turn, enables constructions in which the predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulas, thresholds,etc. This talk will present their construction. ᐧ



148. Title : A New Faster Algorithm for the Maximum Flow in Undirected Graphs
     Speaker : Karthik Abhinav, IIT Madras
     Date, Time & Venue : Fri, May 16, 2014, 2:00 PM - BSB 361
     [Abstract]

     This talk is on the new algorithm given by Christiano-Kelner-Madry-Spielman-Teng in their paper titled Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in undirected graphs.

     The paper gives a (1-a)-approximation algorithm running in time O(mn^{1/3} poly log (mn) poly log(1/a)) to the maximum flow problem. This gives a significant improvement in the running time compared to all previously known algorithms. A critical backbone to this algorithm is a procedure used to solve laplacian system of equations very efficiently.



149. Title : Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
     Speaker : Nikhil Balaji, CMI
     Date, Time & Venue : Wed, May 14, 2014, 9:00 AM - CS34
     [Abstract]

     Abstract: Division is a basic arithmetic operation. Algorithmically, many efficient algorithms(Euclid, long division) are known since antiquity. However, these algorithms are inherently sequential. What is the parallel complexity of division?

     There has been a long line of research aimed at pinning down the exact complexity of integer division starting with Beame-Cook-Hoover(P-uniform NC^1), Reif and Tate(P-uniform TC^0), Chiu-Davidow-Litow(L-uniform NC^1), and culminating in the work of Hesse-Allender-Barrington(DLOGTIME-uniform TC^0). We revisit this question looking to optimize the algorithm in terms of *majority depth*(initially studied by Maciel and Therien). We present improved uniform TC^0 circuits for division, matrix powering, and related problems, where the improvement is in terms of majority-depth.

     Given an arithmetic circuit representing a number, can you find the i-th bit of the number? This problem (BitSLP) is closely related to the complexity of integer division. We will discuss this connection and show that any improvements to the parallel complexity of division in terms of majority depth yields an improved algorithm for BitSLP. Coupled with our improved division algorithm, this yields an improvement in the complexity of BitSLP.

     Subject to time constraints, we will discuss the complexity of constant-size matrix powering and relate it to the question of whether the classic Sum of Square Roots problem admits a polynomial time algorithm (a long standing open problem) and discuss a (very weak) reduction to a special case of matrix powering.

     No special background on circuit complexity is required.

     Joint work with Eric Allender and Samir Datta.



150. Title : Pseudo-randomness for Regular Branching Programs.
     Speaker : Akshay Degwekar, IIT Madras
     Date, Time & Venue : Thu, May 8, 2014, 4:00 PM - CS34
     [Abstract]

     The talk will present the main result of the paper :
     Pseudorandom Generators for Regular Branching Programs
     Mark Braverman, Anup Rao, Ran Raz and Amir Yehudayoff.
     Weblink.



151. Title : Frobenius Automorphisms and Quantum Cyclic Codes
     Speaker : Piyush P. Kurur, IIT Kanpur
     Date, Time & Venue : Tue, May 6, 2014, 11:00 AM - CS25
     [Abstract]

     This is a department seminar (cross listed as a tMeet talk). Details are announced over email and are available at the cse homepage here.



152. Title : A Disjoint Compression Algorithm for Odd Cycle Transversal
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Apr 29, 2014, 4:00 PM - CS34
     [Abstract]

     Given a graph G and an odd cycle transversal T, the disjoint compression problem is to determine if G has a smaller odd cycle transversal that is disjoint from T. In this talk, we will describe an O*(2|T|) algorithm for the problem based on a reduction to Vertex Cover.
     
     Ref: here.



153. Title : Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Apr 22, 2014, 4:00 PM - CS34
     [Abstract]

     We improve upper bounds for 2COLORING (NC1 to AC0[2]), bipartite perfect matching (NC1 to ACC0) and many variants of disjoint paths (NC1 to AC0) in constant planar cutwidth graphs. We also show NC1 lower bounds for HAMPATH and 3COLORING and "almost" AC0[2] lower bounds for 2COLORING and non-bipartite perfect matching.
     Our main aim in this talk is to show that perfect matching on grid graphs can be solved in ACC0. The proof works by reducing the perfect matching problem to the word problem over a finite monoid and showing that the monoid is solvable. We use a method that we call the "primary cycle" method to show that the monoid is solvable. This proof contains all the essential ideas used for proving the more general result presented in the paper. As a warmup, we first show that this method can be used to show that the reachability problem and edge-disjoint paths problem in upward planar grid graphs can be solved in AC0.
     
     (This is joint work with Kristoffer Arnsfelt Hansen (Aarhus University), Jayalal Sarma (IIT Madras), Sven Skyum (Aarhus University) and Navid Talebanfard (Aarhus University))



154. Title : SNP Systems with Cooperating Rules
     Speaker : Srinivasan Raghuraman, IIT Madras
     Date, Time & Venue : Tue, Apr 15, 2014, 4:00 PM - CS34
     [Abstract]

     This talk will present yet another variant of the SNP Systems (Membrane Computing) inspired by CD Grammars and discuss the universality of the same. Exactly how powerful it is is still to be determined. We will also look at this model from a design perspective - a first timers view on the construct.



155. Title : BSS model for real computation
     Speaker : Siddhartha Sivakumar, IIT Madras
     Date, Time & Venue : Tue, Apr 8, 2014, 4:00 PM - CS34
     [Abstract]

     Blum Shub Smale model of computation is defined over the algebraic numbers and over number fields. This model is non-uniform, more closer to the scientific computation. This model considers a reasonable idealization of the cost in use of computers and brings the theory of computation into the domain of analysis, geometry and topology. Turing computability appears as a particular case (computation over F2 = Z mod 2Z). In this general setting, we obtain universal machines and NP-complete problems.



156. Title : Spiking Neural P-Systems and Petri Nets
     Speaker : Padma Metta, IIT Madras
     Date, Time & Venue : Tue, Apr 1, 2014, 4:00 PM - CS34
     [Abstract]

     Spiking neural P systems (for short SNP systems) are distributed and parallel computational models inspired by the spiking activity of neurons in the brain. On the other hand, Petri nets are graphical and mathematical modelling tools applicable to systems that are characterized as being concurrent, distributed, non-deterministic and parallel. A major strength of Petri nets is their support for analysis of many properties and problems associated with parallel systems. The talk will introduce SNP systems and Petri nets and will explain the structural link between them.



157. Title : Membrane Computing
     Speaker : Kamala Krithivasan, IIT Madras
     Date, Time & Venue : Tue, Mar 25, 2014, 4:00 PM - CS34
     [Abstract]

     Membrane Computing is a new paradigm of computing inspired by the way nature computes in cells. In this talk, a brief introduction to the topic will be given illustrating with examples.



158. Title : Property Testing Lower Bounds via Communication Complexity
     Speaker : Shiv Poojan Singh, IIT Madras
     Date, Time & Venue : Tue, Mar 11, 2014, 4:00 PM - CS34
     [Abstract]

     The talk will introduce communication complexity and property testing frameworks. We will describe a fundamental connection between these two areas by using known lower bounds in communication complexity to establish new lower bounds of Property Testing framework. The talk is an expository one on the paper : http://web.mit.edu/matulef/www/papers/PTviaCC-camera.pdf



159. Title : Automata on Codes
     Speaker : Helmut Jürgensen, University of Western Ontario, Canada
     Date, Time & Venue : Fri, Feb 7, 2014, 3:00 PM - BSB 361
     [Abstract]

     Abstract : We survey the actual and potential rôles of automata in the modelling of information transmission systems and, in particular, in the encoder, channel and decoder components of such systems. Our focus is on applications of codes in such systems and on the relevance of automaton theoretic methods to these applications. We discuss, for example, the issues of error-detection, fault-tolerance and error-correction for variable-length codes. Beyond reviewing known work in a possibly new setting, we also present some recent results on fault-tolerant decoders for systems in which synchronization errors are likely. We conclude with a kind of research programme, a list of rather general open problems requiring solutions.



160. Title : Applications of Regularity Lemma
     Speaker : Raghavendra Rao B V, IIT Madras
     Date, Time & Venue : Tue, Feb 4, 2014, 4:00 PM - CS34
     [Abstract]

     We will discuss applications of regularity lemma to graph property testing.



161. Title : A non-linear lower bound for planar epsilon-nets
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Jan 21, 2014, 4:00 PM - CS34
     [Abstract]

     The talk will present the following result due to Noga Alon - which shows that the minimum possible size of an epsilon-net for point objects and line (or rectangle)- ranges in the plane is (slightly) bigger than linear in 1/epsilon. This settles a problem raised by Matousek, Seidel and Welzl in 1990.

     Ref : A non-linear lower bound for planar epsilon-nets - Noga Alon.
     Weblink : www.tau.ac.il/~nogaa/PDFS/epsnet5.pdf‎



162. Title : On the Approximability of the Maximum Acyclic Subgraph problem
     Speaker : Rajsekar Manokaran, KTH, Stockholm, Sweden
     Date, Time & Venue : Tue, Jan 7, 2014, 11:00 AM - BSB 361
     [Abstract]

     This is a department seminar announced at : http://www.cse.iitm.ac.in/



163. Title : Approximation Algorithms for special instances of Guarding a Set of Segments
     Speaker : Anup Joshi, IIT Madras
     Date, Time & Venue : Tue, Dec 31, 2013, 4:00 PM - CS 34
     [Abstract]

     One of the classical problems in Theoretical Computer Science is Hitting Set. We investigate a problem called Guarding a Set of Segments(GSS) which is a hitting set problem on a set of line segments. The problem is, given a set of line segments, how can one select a minimum number of points so that every segment passes through at least one of the selected points. We investigate this problem in the context of a 2-dimensional euclidean space. The problem falls in the category of Art Gallery Problems, an example would be to consider a road network approximated by a set of line segments on the 2-d plane, and the task is to observe all the roads by placing minimum security cameras. We present constant-factor approximation algorithms for special instances of GSS by exploiting the structure of the underlying planar graph of a GSS instance. In the underlying graph the vertex set consists of the intersection points as well as the endpoints of the line segments, and the edge set is the set of all pairs of vertices which are adjacent to each other on a segment. We present a 3-factor approximation algorithm for the special instances of GSS in which the underlying graph has girth at least 4. This also gives a 3-factor approximation for Hitting Set on GSS instances satisfying the Helly Property. We also obtain a 2-factor approximation algorithm for GSS instances whose underlying graph is outerplanar.



164. Title : Consecutive Ones Property: Characterization and Algorithms
     Speaker : Subashini R., IIT Madras
     Date, Time & Venue : Tue, Nov 26, 2013, 4:00 PM - CS34
     [Abstract]

     (This is the second PhD seminar)

     Consecutive Ones Property (COP) is a well studied combinatorial property of binary matrices. A binary matrix has the COP, if there exists a permutation of columns that arrange the ones consecutively in all the rows. In the first part of the talk, we will focus on testing the COP of a binary matrix. We will see that this problem is equivalent to finding a feasible interval assignment to the set system associated with the binary matrix. We then present the intersection cardinality preserving interval assignment (ICPIA) characterization of matrices with the COP. Also, we describe the details of finding a feasible interval assignment to the set system, if one exists. In the second part, we pose an optimization problem (Min-ICPIA) related to the ICPIA characterization and show that this problem is equivalent to the classical Vertex Cover problem. Finally, we consider the Consecutive Ones Submatrix (COS) problem to deal with matrices that do not have the COP. Given a binary matrix M and a positive integer d, COS problem is to decide whether there exists a set of at most d-rows of M whose deletion results in a matrix with the COP. We show that COS problem is fixed-parameter tractable (FPT) with d as the parameter. We establish this via the FPT algorithm for Interval Deletion problem.



165. Title : Trees Cycles Spanners
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Nov 12, 2013, 4:00 PM - CS34
     [Abstract]

     This talk begins with an introduction to the following three problems, followed by a quick survey of the existing results. Tree spanner problem. Give an unweigted graph G and a positive integer t, find a spanning tree T of G with the property that, for every edge (u, v) in G, there is a path of length at most t between u and v in T (if exists). Minimum total-stretch spanning tree problem. Given an unweighted graph G, find a spanning tree T that minimizes the sum of the distances between u and v in T over all the edges (u, v) in G. Minimum cycle basis problem. Given a weighted graph G, find a minimal set B of cycles, such that every cycle in G can be generated by performing ex-or sum on a set of cycles from B and the sum-total weight over all the cycles in B is minimum. We then present our linear-time algorithms for tree t-spanner problem in outerplanar graphs and minimum cycle basis problem in weighted partial 2-trees. Further, we present an algorithm for minimum total stretch spanning tree problem that runs in O(n log n) time. Finally, we look at the connections across these problems.



166. Title : Price of Anarchy, Auctions, and Approximations
     Speaker : Sayan Bhattacharya, Max-Planck-Institut für Informatik, Saarbrücken
     Date, Time & Venue : Tue, Nov 5, 2013, 3:00 PM - BSB 361
     [Abstract]

     This is a department seminar.



167. Title : A tau-Conjecture for Newton Polygons
     Speaker : Raghavendra Rao B V, IIT Madras
     Date, Time & Venue : Tue, Oct 29, 2013, 4:00 PM - CS34
     [Abstract]

     The real tau conjecture states that the number of real roots of a depth four univariate arithmetic circuit is at polynomial in the size of the circuit. If true, real tau-conjecture separates the algebraic complexity classes VP and VNP. In this talk, we will do a brief survey of real tau-conjecture and present a special case of real tau-conjecture bounding the number of edges in the Newtn polygon corresponding to a bivariate polynomial. The tau-conjecture for Newton polygons also implies a superpolynomial lowerbound for permanent. The talk will be based on the paper: A tau-conjecture for Newton polygons Pascal Koiran, Natacha Portier, Sébastien Tavenas and Stéphan Thomassé :arXiv:1308.2286



168. Title : Depth Reduction in Arithmetic Circuits
     Speaker : K.S. Sunil, IIT Madras
     Date, Time & Venue : Tue, Oct 22, 2013, 4:00 PM - CS34
     [Abstract]

     Arithmetic circuits of polynomial size and polynomial degree can be reduced to O(log^2 n) depth (and even to O(log n) depth if unbounded-fanin gates are allowed).

     We discuss a uniform depth reduction algorithm for the general case of polynomial-degree polynomial-size arithmetic circuits over any commutative semiring.

     Reference:
     Non-Commutative Arithmetic Circuits: Depth reduction and Size Lower Bounds. [Eric Allender, Jia Jiao, Meena Mahajan, V Vinay]



169. Title : Power of Two Choices
     Speaker : William Kumar Moses Jr., IIT Madras
     Date, Time & Venue : Tue, Oct 15, 2013, 4:00 PM - CS34
     [Abstract]

     The problem of load balancing is both a common problem as well as an interesting one. The problem itself is simple: given a graph G(V,E), where each node is also assigned an attribute called load, how can we redistribute this load in as few rounds as possible so that each nodes load is as close to the average of the loads in the system as possible. A variant of load balancing deals with assignment of load to nodes as the load enters the system. An application that immediately comes to mind would be cloud storage. Here, the problem would be the distribution of files in a server farm so that each server has to process more or less the same number of requests.

     In order to study this problem, several models have been proposed, including the balls and bins model. In this model, we consider n balls to represent n pieces of load and we also consider that there are n bins which we want to fill with balls. We sequentially throw one ball at a time into the bins. Our goal is to ensure that there is a good bound on the maximum number of balls in each bin after throwing in all n balls. A simple strategy is, for each ball, choose a bin at random and throw the ball in. This yields an upper bound of $O(frac{log n}{log log n})$ with high probability. Now we see a simple, yet highly effective modification to this strategy. Instead of choosing a bin at random, choose 2 bins (sample with replacement) at random and toss the ball into the lesser loaded of the 2 bins. By utilizing this simple twist, we achieve much better results, i.e. our upper bound on maximum load of any bin is now $O(log log n)$ with high probability. In fact, instead of choosing 2 bins, if we choose d bins, then the new bound becomes $O(frac{log log n}{log d})$. The twist is simple, but the analysis is complex. This talk aims to give some insight into the proof of this result.



170. Title : Approximation Algorithm for Minimum Chain Vertex deletion Problem
     Speaker : Safina Devi, Dept of Math, IIT Madras
     Date, Time & Venue : Tue, Oct 8, 2013, 4:00 PM - CS34
     [Abstract]

     A bipartite graph $G=(A cup B, E)$ is called a chain graph if there exists an ordering $ ho=$ of the vertices in $A$ such that $N(v_1) subseteq N(v_2) ldots subseteq N(v_n)$. We consider the complexity of a node deletion problem associated with this graph property, which is defined as: Given a bipartite graph $G=(V, E)$ ($V=A cup B$) and a weight function $w: V ightarrow mathbb{Q}^+$, find a set $S subseteq V$ of minimum weight $w(S) = sum_{v in S}w(v)$ such that $G[Vsetminus S]$ is a chain graph. We present a polynomial time factor 2 approximation algorithm for this problem which is known to be NP-complete. We generalize this algorithm to design approximation algorithms for some other node deletion problems related to graph properties having finite forbidden subgraph characterization when restricted to bipartite graphs.



171. Title : On k-chordal graphs
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Oct 1, 2013, 4:00 PM - CS34
     [Abstract]

     k-chordal graphs are graphs that forbid induced cycles of length more than k. The well-known chordal graphs are 3-chordal. In this talk, we will discuss some structural/algorithmic properties of k-chordal graphs and compare them with the ones known for chordal graphs.



172. Title : Size Lower Bounds Against Non-multilinear Arithmetic Circuits
     Speaker : Jayalal Sarma, IIT Madras
     Date, Time & Venue : Tue, Sep 24, 2013, 4:00 PM - CS34
     [Abstract]



173. Title : On Minimum Average Stretch Spanning Trees in Polygonal 2-trees
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Sep 17, 2013, 4:00 PM - CS36
     [Abstract]

     A spanning tree of an unweighted graph is a minimum average stretch spanning tree (MAST) if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. We consider the problem of computing an MAST in polygonal 2-trees, a super class of 2-connected outerplanar graphs and 2-trees. For a polygonal 2-tree on n vertices, we present an algorithm to compute an MAST in O(n log n) time.



174. Title : Robust Leader Election in Fast Changing World
     Speaker : Tejas Kulkarni, IIT Madras
     Date, Time & Venue : Tue, Sep 10, 2013, 4:00 PM - CS36
     [Abstract]

     Abstract: We consider the problem of electing a leader among nodes in a highly dynamic network where adversary has unbounded capacity to insert and remove nodes (including the leader) from the network and change topology at will. We present a randomized algorithm that elects & re-elects a leader in $O(D log n)$ rounds W.H.P. where D is a bound on dynamic diameter of the network and n is a number of nodes in the network in any round. We assume a model of broadcast-based communication where a node can send only one message of $O(log n)$ bits per round per edge and is not aware of recipients in advance(i.e. before the start of the round). Our solution improves the deterministic solution of $O(D.n)$ rounds for termination time, presented at FOMC 2011. We also show that any randomized algorithm solving leader election in our settings, takes $Omega(D. log n)$ rounds to elect a leader which shows that our algorithm yields the most optimal termination time.
     
     This is joint work with John Augustine, Paresh Nakhe, and Peter Robinson and got accepted in The Ninth ACM International Workshop on Foundation of Mobile Computing (FOMC-2013) , Jerusalem, Israel.



175. Title : Lower Bounds for Depth 4 Formulas Computing Iterated Matrix Multiplication
     Speaker : Meena Mahajan, IMSc Chennai
     Date, Time & Venue : Tue, Sep 3, 2013, 4:00 PM - CS36
     [Abstract]

     The talk will present the recent paper :
     Lower bounds for depth 4 formulas computing iterated matrix multiplication. Herve Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan.
     Weblink : http://eccc.hpi-web.de/report/2013/100/



176. Title : FPT algorithms for Consecutive Ones Submatrix problems
     Speaker : Subashini R., IIT Madras
     Date, Time & Venue : Tue, Aug 27, 2013, 4:00 PM - CS36
     [Abstract]

     A binary matrix M has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of d-COS-R (Consecutive Ones Submatrix by Row deletions) problem: Given a matrix M and a positive integer d, decide whether there exists a set of at most d rows of M whose deletion results in a matrix with COP. The closely related Interval Deletion problem has recently been shown to be FPT. In this work, we describe a recursive depth-bounded search tree algorithm in which the problems at the leaf-level of the recursion tree are solved as instances of Interval Deletion. Therefore, we show that d-COS-R is fixed-parameter tractable and has the current best run-time of O^∗(10^d ), which is associated with the Interval Deletion problem. We then consider a closely related optimization problem, called Min-ICPIA, and prove that it is computationally equivalent to the Vertex Cover problem.
     
     This is joint work with Narayanaswamy N.S. and is accepted for publication at IPEC 2013.



177. Title : Reasoning about repeating values: how precisely should we count?
     Speaker : Praveen Manjunatha, Laboratoire Bordelais de Recherche en Informatique (LaBRI)
     Date, Time & Venue : Tue, Aug 27, 2013, 2:00 PM - BSB 361
     [Abstract]

     Formal verification is the process of checking whether a design satisfies a specified requirement, using mathematical reasoning. In a system running a process with a fixed number of resources, we may for example wish to check that requests for access to a resource are always granted in due course. This specification may be written in a language designed to deal with the fixed number of resources and there are classical formalisms for modelling and designing algorithms. This may not be sufficient for systems where processes and resources are dynamically created and destroyed. We may want to check that whenever some process with id P requests access to a resource with id R, some time in the future access to resource R is granted to process P. The number of processes and resources is finite at any time, but there may not be a bound a-priori. For this kind of systems, the possibility of infinitely many values for P and R has to be taken into account.
     
     We begin by outlining a recent work by Demri et al., which builds on traditional logics by adding the power to reason about repetitions of values from an infinite domain. Designing algorithms for this extension leads to models of computation that can count. These can be thought of as finite state automata augmented with counters, similar to push down automata obtained by augmenting finite state automata with a stack. Less precise rules for controlling the counters make the resulting algorithms more efficient. After outlining these, we describe our work:
     1) Rules like increment the counter by 1 can be replaced by less precise ones like increment the counter by 1 or more, without changing the end results.
     2) Other related results, like the number of counters necessary.
     3) Consequences for the efficiency of the verification algorithms. Collectively, these results show a correspondence between the power of specification languages and the power of counting models needed.
     This is joint work with Stéphane Demri and Diego Figueira.



178. Title : Approximability of Connected Factors
     Speaker : Rahul C.S., IIT Madras
     Date, Time & Venue : Tue, Aug 20, 2013, 4:00 PM - CS36
     [Abstract]

     Given a graph G the problem is to determine whether it contains a connected k-regular spanning subgraph. The problem of checking whether the graph contains a k-factor(k-regular subgraph) or not is polynomial time solvable. But with connectivity constraint, the problem is NP-complete for constant values of k. If n is the number of vertices in the input graph, the problem is polynomial time solvable when k ≥ ⌈n/2⌉−1. We discuss a 3-approximation algorithm for the problem of finding a minimum-weight connected k-factor in a weighted graph where the weight function is a metric. Further, we give several approximation algorithms for some restricted versions of the problem. We also give an approximation algorithm for the maximization version of the same. In addition we discuss the same problem in directed graphs.



179. Title : Discharging method
     Speaker : Narayanan N., Dept. of Maths, IIT Madras
     Date, Time & Venue : Tue, Aug 13, 2013, 4:00 PM - CS36
     [Abstract]

     The famous four colour theorem for planar graphs was proved by a technique called the Discharging Method. This technique had since been used on numerous problems on classes of graphs where we can find a nice relation between cardinalities of different graph entities (edges, vertices, faces, corners, cycles etc). We present a number of examples to illustrate the idea behind this method and its usage.



180. Title : Tight Time-Space Tradeoff for Mutual Exclusion
     Speaker : Prasad Jayanti, University of Dartmouth
     Date, Time & Venue : Tue, Aug 6, 2013, 4:00 PM - CS36
     [Abstract]

     Mutual Exclusion is a fundamental problem in distributed computing. In the last two decades, there has been a great deal of research on designing algorithms with small Remote Memory Reference (RMR) complexity (the -RMR complexity measure- captures how well concurrent algorithms perform on shared memory multiprocessors). In this talk, I will show how RMR complexity trades off with space complexity. Specifically I will show that, on cache coherent multiprocessors, constant RMR complexity is impossible with subpolynomial space and subpolynomial RMR complexity is impossible with constant space. The proofs are fascinating and are done via a purely combinatorial game that corresponds closely to mutual exclusion. (These results were presented at STOC 2012 and are joint work with Nikhil Bansal, Vibhor Bhatt, and Ranganath Kondapally.)



181. Title : Depth Lower Bounds Against Circuits of Sparse Orientation
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Tue, Jul 30, 2013, 4:00 PM - CS36
     [Abstract]

     This talk will present depth lower bounds against non-monotone circuits, parameterized by a new measure of non-monotonicity : the orientation of a function f is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing f. We prove trade off results between the depth and the weight/structure of the orientation vectors in any circuit C computing Clique function on an n vertex graph G(V,E).
     
     As our main tool, we generalize Karchmer-Wigderson game for monotone functions to work for non-monotone circuits parameterized by the weight/structure of the orientation.
     
     This is joint work with Jayalal Sarma.



182. Title : LP Approach to Odd Cycle Transversal in Perfect Graphs
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Jul 23, 2013, 4:00 PM - CS36
     [Abstract]

     Given an undirected graph G, a subset S of vertices is said to be an odd cycle transversal (OCT) if it has at least one vertex from every odd cycle in G. That is, S is an OCT if G-S is bipartite (2-colorable). The problem of finding an optimum OCT generalizes the classical VERTEX COVER problem as a vertex cover is a set of vertices whose deletion results in a 1-colorable graph. Both these problems belong to the important class of vertex deletion problems and are known to be NP-hard in general. One of the largest classes of graphs on which VERTEX COVER is known to be polynomial-time solvable is the class of perfect graphs. This classical polynomial-time algorithm, due to Grotschel, Lovasz and Schrijver, is based on semi-definite programming and polyhedral combinatorics. Similar polyhedral structure and complexity results do not extend to OCT, which remains NP-hard on perfect graphs. We introduce a linear programming formulation for OCT that generalizes the formulation known for VERTEX COVER based on clique constraints. Using this, the polynomial time algorithm for VERTEX COVER and a deterministic rounding procedure we give a 2-approximation algorithm for OCT in perfect graphs.



183. Title : A Fourier Analytic Framework for Circuit Lower Bounds - Part II
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Apr 23, 2013, 4:00 PM - BSB 361
     [Abstract]

     We look at a line of work [1] [2] that uses Fourier analysis for obtaining size lower bounds on monotone switching networks. We will first take a look at the general framework for obtaining lower bounds and then specialize the framework to problems such as the k-clique problem, directed graph s-t reachability etc.
     [1] Aaron Potechin: Bounds on Monotone Switching Networks for Directed Connectivity. FOCS 2010: 553-562
     [2] Siu Man Chan, Aaron Potechin: Tight bounds for monotone switching networks via fourier analysis. STOC 2012: 495-504



184. Title : Degree Sets : Realizability and Extension Problem
     Speaker : Prasun Kumar, IIT Madras
     Date, Time & Venue : Tue, Apr 23, 2013, 3:00 PM - BSB 361
     [Abstract]

     TBA



185. Title : A Fourier Analytic Framework for Circuit Lower Bounds - Part I
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Apr 16, 2013, 4:00 PM - BSB 361
     [Abstract]

     We look at a line of work [1] [2] that uses Fourier analysis for obtaining size lower bounds on monotone switching networks. We will first take a look at the general framework for obtaining lower bounds and then specialize the framework to problems such as the k-clique problem, directed graph s-t reachability etc.
     [1] Aaron Potechin: Bounds on Monotone Switching Networks for Directed Connectivity. FOCS 2010: 553-562
     [2] Siu Man Chan, Aaron Potechin: Tight bounds for monotone switching networks via fourier analysis. STOC 2012: 495-504



186. Title : Barriers in Quantum Hamilltonian Complexity
     Speaker : Vamsi Krishna Devabathini, IIT Madras
     Date, Time & Venue : Tue, Apr 9, 2013, 4:00 PM - BSB 361
     [Abstract]

     Quantum Hamiltonian complexity is an exciting area combining deep questions and techniques from both quantum complexity theory and condensed matter physics. The connection between these fields arises from the close relationship between their defining questions: the complexity of constraint satisfaction problems in complexity theory and the properties of ground states of local Hamiltonians in condensed matter theory. Some of the most intriguing questions to ask here are:
     Can ground states of natural quantum systems be described succinctly ( polynomial in the number of particles) ? Does the exponential complexity of general quantum systems persist at high temperature?
     This question translates to a beautiful conjecture in condensed matter theory called the area law, which states that the ground state of any local Hamiltonian satisfies the property that the entanglement entropy across any cut is bounded by the edge expansion of the cut.
     The second question can be formalized as asking whether the quantum analog of the PCP theorem is true. In this talk, I will be introducing physical implications of area law and the ideas used in proving the area law in 1D case and possible ideas for extending to higher dimensions. Also I will give a brief overview of the QPCP Theorem. A detailed report on the same can be found here.



187. Title : Fiat-Shamir Zero Knowledge Protocol with its formal proof
     Speaker : C. Pandu Rangan, IIT Madras
     Date, Time & Venue : Tue, Apr 2, 2013, 4:00 PM - BSB 361
     [Abstract]

     This talk will present complete math details of a formal proof of a zero knowledge protocol in a simple, direct and tutorial fashion.



188. Title : Why Goldwasser and Micali received the TURING award? An expository account of (some of) their great ideas.....
     Speaker : C. Pandu Rangan, IIT Madras
     Date, Time & Venue : Tue, Mar 19, 2013, 4:00 PM - CS 25
     [Abstract]

     Title says it all!!!!!.. All computer literates are welcome..



189. Title : Popular Matchings -- Structure and Cheating Strategies.
     Speaker : Meghana Nasre, University of Texas, Austin
     Date, Time & Venue : Tue, Mar 12, 2013, 3:00 PM - BSB 361
     [Abstract]

     We consider the problem of matching a set of agents A to a set of posts P where agents rank posts according to their preferences, possibly involving ties. This problem occurs in several real world scenarios like assigning jobs to applicants, houses to trainees and DVDs to customers. Several notions of optimality have been considered in the literature and we focus on the notion of popularity. A matching M is popular if there exists no matching M_1 such that the number of agents that prefer M_1 to M exceeds the number of agents that prefer M to M_1.

     In this talk, we consider a centralized market where agents submit their preferences and a central authority matches agents to posts according to the notion of popularity. Since a popular matching need not be unique, we assume that the central authority chooses an arbitrary popular matching. Let a1 be the sole manipulative agent who is aware of the true preference lists of all other agents. The goal of a1 is to falsify her preference list to get better always, that is, to improve the set of posts that she gets matched to as opposed to what she got when she was truthful. We show that the optimal cheating strategy for a single agent to get better always can be computed in O(sqrt{n}m) time when preference lists are allowed to contain ties and in O(m+n) time when preference lists are all strict. Here n = |A| + |P| and m denotes the combined size of all the preference lists. We also characterize the equilibrium of a non-cooperative game where all agents are manipulative.

     To compute the cheating strategies, we develop a switching graph characterization of the popular matchings problem involving ties. The switching graph characterization for the case of ties is of independent interest and answers a part of the open questions posed by McDermid and Irving (J. Comb. Optim. 2011).

     These results have been accepted for publication at STACS 2013.



190. Title : Controlled P Systems
     Speaker : Ajeesh Ramanujan, IIT Madras
     Date, Time & Venue : Tue, Mar 12, 2013, 2:00 PM - BSB 361
     [Abstract]

     In the last two decades, there has been tremendous interest in defining and studying new computing paradigms which are inspired by nature. Natural computing has emerged as an area which is followed with a lot of interest. P systems introduced by Gh. Pu{a}un, are computing models inspired from the structure and functioning of the living cells. A P system consists of a finite number of membranes, each of which contains a multiset of objects from a finite alphabet. The membranes are organized as a Venn diagram or a tree structure where membranes may contain other membranes. The dynamics of the system is governed by a set of rules associated with each membrane. Each rule specifies how objects evolve and move into neighboring membranes. It has been introduced as a computing model which abstracts from the way live cells process chemical compounds in their compartmental (membrane) structure. Various models of P systems have been shown to be equivalent to Turing machines in computing power.

     We consider a way of controlling the computation of a P system. A label is assigned to every rule, where the labels are chosen from a finite alphabet. P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, $lambda$), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky hierarchies (characterizations of the length sets of recursively enumerable languages are obtained in this framework).

     This is the second PhD seminar.



191. Title : Consecutive Ones Submatrix (COS) by row deletion is Fixed Parameter Tractable
     Speaker : Subashini R., IIT Madras
     Date, Time & Venue : Tue, Mar 5, 2013, 4:00 PM - BSB 361
     [Abstract]

     A binary matrix has the Consecutive Ones Property (COP), if there exists a permutation of columns that arranges the ones consecutively in all the rows. MIN-COS-R is the problem of finding the minimum number of rows whose deletion results in a matrix with the COP. We consider the decision version of MIN-COS-R with the number of rows to delete as the parameter and show that it is FPT by employing the recent result of the closely related Interval Deletion problem.



192. Title : On 2-matchings and 2-covers
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Feb 26, 2013, 4:00 PM - BSB 361
     [Abstract]

     We will discuss relaxations of matching and vertex cover and relate them to their classical counterparts.



193. Title : Linear time algorithm for finding Minimum Cycle Basis in Weighted Partial 2-trees.
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Feb 19, 2013, 4:00 PM - BSB 361
     [Abstract]

     A cycle basis of a graph is a minimal set of cycles that generates all the cycles of the graph. The cost of a cycle basis is defined as the sum of the weights of the cycles in the cycle basis. A cycle basis whose cost is minimum is referred to as a minimum cycle basis. We present a linear time algorithm to find a minimum cycle basis in weighted partial 2-trees. (Joint work with Carola Doerr and Jens Schmidt)



194. Title : Smoothed Analysis of the Successive Shortest Path Algorithm for Min-Cost Flow.
     Speaker : Bodo Manthey, University of Twente, The Netherlands
     Date, Time & Venue : Tue, Feb 12, 2013, 4:00 PM - BSB 361
     [Abstract]

     TBA



195. Title : Control Languages associated with Spiking Neural P Systems
     Speaker : Ajeesh Ramanujan, IIT Madras
     Date, Time & Venue : Tue, Feb 5, 2013, 2:00 PM - BSB 361
     [Abstract]

     Spiking neural P systems (shortly called SN P systems) are distributed parallel computing devices, a class of membrane systems (also known as P systems), inspired by the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons. In SN P systems, the neurons are placed in the nodes of a directed graph, called the synapse graph. Every neuron may contain a number of copies of a single object called the spike (denoted with a), and also a number of firing and forgetting rules. Firing rules allow a neuron to send information to other neurons in the form of electrical impulses which are accumulated at the target neurons. The application of each rule is determined by checking the contents of the neuron against a regular expression associated with the rule. In each step, if a neuron can use more than one rule, then one of them is non-deterministically chosen and applied. Thus, the rules are used in a sequential manner in each neuron, but neurons function in a parallel manner.

     This is the first (formal) PhD seminar.



196. Title : Directed Tree Realizations of Degree Sets
     Speaker : Prasun Kumar, IIT Madras
     Date, Time & Venue : Tue, Jan 29, 2013, 4:00 PM - BSB 361
     [Abstract]

     Degree set of a graph is the set formed from the degree of vertices in the graph. It provides an another way of representing the graph but at the cost of loosing uniqueness. We will talk about multiplicity constrained degree set, an intermediate case between degree sequence and set, to get the bounds on multiplicity of vertices in any realization and also explore the different notions of realizability in case of directed graphs, especially directed trees.
     The work reported was jointly done with Jayalal Sarma and Saurabh Sawlani, and will be presented at WALCOM 2013.



197. Title : Entropy, Pebbling and Branching Program Size Lower Bounds
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Jan 22, 2013, 4:00 PM - BSB 361
     [Abstract]

     The tree-evaluation problem was introduced by Cook et. al. as a candidate for separating LogSpace from P. We prove tight exponential size lower bounds for non-deterministic, bitwise-independent, thrifty branching programs solving the tree-evaluation problem. This lower bound corresponds to super-logarithmic space lower bounds for natural algorithms solving the problem. All the best known upper-bounds can be implemented using this model. The lower bound will be proved using the Entropy method by Jukna and Zaks. We will use pebbling lower bounds in a black-box fashion to prove these lower bounds.

     Ref:- Balagopal Komarath and Jayalal Sarma, Pebbling, Entropy and Branching Program Size Lower Bounds (Accepted to STACS 2013)



198. Title : Packing rectangles into a rectangle
     Speaker : Petru Valicov, LRI Paris
     Date, Time & Venue : Mon, Jan 7, 2013, 3:00 PM - BSB 361
     [Abstract]

     We address the problem of packing rectangles into a bigger rectangle, also called the two-dimensional Orthogonal Packing Problem (OPP-2). The goal is to decide whether a set V of rectangles can be packed in a rectangular container C without overlapping and without exceeding the borders of C. In the classical version the rotation of items is not allowed. If the set V can be packed in C then V is called a feasible set. This problem is NP-complete and can be seen as a sub-problem of the well known two-dimensional Orthogonal Knapsack Problem (where each item has an associated profit and the goal is to choose a subset of items which maximizes the total profit). In 1997 Fekete and Schepers introduced an interesting characterization of feasible solutions based on interval graphs. Using this characterization they designed an efficient algorithm to solve OPP by enumerating the interval graphs with a certain number of constraints. In this work, we present a new algorithm for solving OPP-2 based on a more compact representation of interval graphs using the so-called MPQ-trees. One of the main advantages is having a reduced number of symmetrical solutions. Similar to Fekete and Schepers approach, our algorithm can be generalized to a multidimensional case. I will finish the talk by showing the comparison with other algorithms from the literature using classical benchmarks. This is a joint work with C. Joncour and A. Pecher.



199. Title : Density Functions subject to a Co-Matroid Constraint
     Speaker : Sivaramakrishnan N.R., IIT Madras
     Date, Time & Venue : Tue, Dec 11, 2012, 4:00 PM - BSB 361
     [Abstract]

     In this paper we consider the problem of finding the {em densest} subset subject to {em co-matroid constraints}. We are given a {em monotone supermodular} set function $f$ defined over a universe $U$, and the density of a subset $S$ is defined to be $f(S)/crd{S}$. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid $calM$ a set $S$ is feasible, iff the complement of $S$ is {em independent} in the matroid. Under such constraints, the problem becomes $ p$-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thus, for instance, we improve the approximation guarantees for the result for partition matroids in the literature.
     
     Weblink : http://arxiv.org/abs/1207.5215 This is a joint work with work with Venkatesan T. Chakaravarthy, Natwar Modani, Sambuddha Roy, Yogish Sabharwal, at IBM IRL and will be presented at FSTTCS 2012 in Hyderabad next week.



200. Title : A Parameterized Approach to the Consecutive-ones Submatrix Problem
     Speaker : Subashini R., IIT Madras
     Date, Time & Venue : Tue, Dec 4, 2012, 3:00 PM - BSB 361
     [Abstract]

     A binary matrix is said to have the consecutive ones property (COP) for rows if there exists an ordering of the columns such that, in each row all the ones occur as a single block. Deciding whether a binary matrix has COP or not is polynomial-time solvable. On matrices that do not have COP, a natural task is to find a minimum cardinality set of rows whose deletion results in a matrix with COP. This problem referred to as Consecutive Ones Submatrix (COS) is known to be NP-complete. We present the parameterized results known for the COS problem on matrices that have a bound on the number of ones in either rows or columns. We then present our approach to the problem on general matrices where there is no restriction on the number of ones in rows and columns



201. Title : Counting Polynomially Bounded Perfect Matchings.
     Speaker : Nilkamal Adak, IIT Madras
     Date, Time & Venue : Tue, Nov 27, 2012, 4:00 PM - BSB 361
     [Abstract]

     Counting number of perfect matchings in a graph is an important problem from both the practical and theoretical point of views. But for general graphs, this problem is known to be #P complete. In this talk we will discuss a promise version of the problem. We will see, we can count as wee as enumerate all the perfect matchings in a graph in NC^2 if number of perfect matching in the graph is bounded by some given polynomial.

     Reference : www.cse.iitk.ac.in/users/manindra/other/Poly-Machings.pdf



202. Title : Random Shortest Path Metrics with Applications
     Speaker : Raghavendra Rao B V, IIT Madras
     Date, Time & Venue : Thu, Nov 15, 2012, 4:00 PM - BSB 361
     [Abstract]

     Tentative abstract: We consider random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The length of an edge is then the length of a shortest path with respect to the weights drawn that connects its two endpoints. We prove structural properties of the random metric spaces generated in this way. Then we apply these findings to analyze the approximation ratios of heuristics for matching and the traveling salesman problem (TSP). The bounds that we obtain are considerably better than the respective worst-case bounds.



203. Title : Introduction and Applications of Szemeredis Regularity Lemma
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Nov 6, 2012, 4:00 PM - BSB 361
     [Abstract]

     In this talk we introduce the Regularity lemma and show one application conditions under which r-partite subgraphs can be guaranteed in a given graph.



204. Title : Can GI be NP-complete?
     Speaker : Balagopal Komarath, IIT Madras
     Date, Time & Venue : Tue, Oct 30, 2012, 4:00 PM - BSB 361
     [Abstract]

     Graph Isomorphism (GI) is one of those problems in class NP for which we do not know a polynomial time algorithm or a proof of NP-hardness. In this talk we look at a theorem which gives evidence that it is highly unlikely that GI is NP-complete.



205. Title : Primes is in P - The AKS algorithm
     Speaker : Dinesh K., IIT Madras
     Date, Time & Venue : Tue, Oct 23, 2012, 4:00 PM - BSB 361
     [Abstract]

     We will be seeing the deterministic polynomial time algorithm for primality testing by Manindra Agarwal, Neeraj Kayal and Nitin Saxena. We shall be arguing its correctness using elementary techniques and will also show a runtime of O((log n)^{16.5}).



206. Title : Approximate sampling and counting using Markov chains
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Tue, Oct 16, 2012, 4:00 PM - BSB 361
     [Abstract]

     Abstract : In this talk we will be presenting Markov chains as a tool to efficiently sample almost uniformly at random from and to estimate the approximate count of non-trivial sets like perfect matchings of a given graph, which are hard to count or sample using other algorithmic techniques. We will describe the general framework of Markov chain based sampling and demonstrate application of the framework to sample almost uniformly at random from matchings of a given graph. We will then detail the Markov chain theory needed to bound the running time of such algorithms based on the mixing time of the underlying Markov chain. We will also hint on the connection between approximate sampling and approximate counting and if time permits present the proof that they are equivalent.

     Reference : Lecture notes from a course offered by Sanjeev Arora at Princeton University titled - Theorists Toolkit.



207. Title : Tree Cycles Spanners
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Oct 9, 2012, 4:00 PM - BSB 361
     [Abstract]

     Abstract : A spanning tree of an unweighted graph is a tree t-spanner if the distance between every pair of vertices in the spanning tree is at most t times their distance in the graph. Given an unweighted graph G and a positive integer t, the tree t-spanner problem decides the existence of a tree t-spanner in G. A minimum set of cycles of a graph is a cycle basis if every cycle in the graph can be generated by combining the cycles in the cycle basis. The weight of a cycle basis is the sum of the weights of the cycles in the cycle basis. We present a linear time algorithm for tree t-spanner in outerplanar graphs. Also, we present a structural characterization of a minimum weight cycle basis in weighted partial 2-trees



208. Title : Dr. Jekyll and Mr. Hyde: The Two Personalities of an Algorithm Designer
     Speaker : John Augustine, IIT Madras
     Date, Time & Venue : Tue, Sep 25, 2012, 4:00 PM - BSB 361
     [Abstract]

     Given a problem, our quest is an algorithm that solves that problem as optimally as we can. This requires that we wear two thinking hats. On the one hand, we need to approach the problem with an intent to solve it optimally --- an optimistic frame of mind. On the other, we also need to gain a perspective on the limits of any algorithm that we design, which is a more pessimistic frame of mind. In this talk, we will bring out the interplay between these two frames of mind using the paging problem as an example.

     More concretely speaking, we will introduce the paging problem (which is a quintessential online problem) and provide some algorithms. Along the way, we will introduce the various adversaries against which these algorithms compete. Time permitting, we will present Yao's Minimax principle and apply it to prove a negative result on randomized algorithms for the paging problem.



209. Title : An Algorithm for Finding k-edge disjoint Spanning Trees
     Speaker : Rahul C.S., IIT Madras
     Date, Time & Venue : Tue, Sep 11, 2012, 4:00 PM - BSB 361
     [Abstract]

     The discussion covers a short proof of Tutte and Nash Williams characterization of undirected graphs with k-edge disjoint trees explained in [1]. The idea is based on the observation that, if we partition the vertices in a tree, the partitions will be atleast 1- connected as the tree is 1-connected. Clearly, if the graph has k-edge disjoint spanning trees, any partitioning of vertex set of the graph will have the partitions 1-connected in each of those k spanning trees. To begin with, we discuss the procedure that decompose the graph in to two edge disjoint connected spanning subgraphs (if exists), and extend the idea, to make it applicable for higher values of k.
     
     Prerequisites: Listeners are expected to be familiar with the terms partitioning of vertices, k-connectivity and spanning trees.
     
     References :
     Tom Kaiser. A short proof of the tree-packing theorem. Discrete Mathematics, 312(10):1689–1691, 2012



210. Title : What if the adversary gets a GLASS BOX decryption oracle access?
     Speaker : Sree Vivek S., IIT Madras
     Date, Time & Venue : Tue, Sep 4, 2012, 4:00 PM - BSB 361
     [Abstract]

     Abstract: Security of an encryption system is formally established through the properties of an abstract game played between a challenger and an adversary. During the game, the adversary will be provided with all information that he could obtain in an attack model so that the adversary is fully empowered to carry out the break. This information will be provided to the adversary through the answers of appropriately defined oracle queries. The indistinguishability of ciphertext under adaptively chosen ciphertext (IND-CCA2) model is considered to offer strongest security for confidentiality. In the recent past, an adversary could obtain several additional information than what he could normally obtain in the IND-CCA2 model, thanks to the availability of powerful malwares such as RAM scrapers. In order to realistically model the threats posed by such malwares, we need to empower the adversary with answers to a glass box decryption oracle instead of a black box decryption oracle. In this talk we will see formally what if the adversary gets a GLASS BOX decryption oracle access.



211. Title : k-simplicial paths for k-chordal graphs
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Aug 28, 2012, 4:00 PM - BSB 361
     [Abstract]

     A characterization of k-chordal graphs based on k-simplicial paths will be presented.



212. Title : Regularity Lemma - I
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Aug 21, 2012, 4:00 PM - BSB 361
     [Abstract]

     A proof and an application of the Szemeredi regularity lemma.



213. Title : Isomorphism Testing of Polynomials
     Speaker : Jayalal Sarma, IIT Madras
     Date, Time & Venue : Tue, Aug 14, 2012, 4:00 PM - BSB 361
     [Abstract]

     We present deterministic polynomial time algorithms for restricted cases of Isomorphism Testing of polynomials. We will also show matching hardness results to show the limits of these restrictions.



214. Title : Security of Encryption Schemes - Cryptography without tears
     Speaker : C. Pandu Rangan, IIT Madras
     Date, Time & Venue : Tue, Aug 7, 2012, 4:00 PM - BSB 361
     [Abstract]

     Same as the title !



215. Title : Probabilistic and Smoothed Analysis of Approximation Algorithms
     Speaker : Raghavendra Rao B.V., University of Saarland
     Date, Time & Venue : Mon, Jun 11, 2012, 2:00 PM - BSB 361
     [Abstract]

     Analysis of Algorithms involves systematic explanation of behaviours of algorithms under various input distributions. We focus on the Probabilistic and Smoothed analysis of algorithms. Of particular interest is the performance of approximation algorithms.

     We study the well known Christofides algorithm for the Euclidean Travelling Salesman Problem. We show that the tour cost computed by Christofides algorithm on uniform inputs from the unit square stabilizes to a smooth function.

     Smoothed analysis is a relatively new technique introduced by Spielman and Teng in 2001. This generalizes the paradigm of probabilistic analysis of algorithms. We provide a general framework for doing smoothed analysis of a class of partitioning algorithms for various Euclidean optimization problems.

     Towards the end of the talk, I will also give a brief overview of my research interests in Complexity Theory, particularly arithmetic circuits.



216. Title : Rigid Matrices and Linear Codes
     Speaker : Gaurav Maheshwari, IIT Madras
     Date, Time & Venue : Thu, Apr 12, 2012, 2:00 PM - CS36
     [Abstract]

     We describe a new approach for the problem of finding rigid matrices (posed by Valiant), by connecting it to the, seemingly unrelated, problem of proving lower bounds for linear locally self-correctable codes. The results are based on a lemma saying that, if the generating matrix of a locally decodable code is not rigid, then it defines a locally self-correctable code with rate close to one. Thus, showing that such codes cannot exist will prove that the generating matrix of any locally decodable code (and in particular Reed Muller codes) is rigid. The presentation is based on a paper by Zeev Dvir available here : www.cs.princeton.edu/~zdvir/papers/Dvir10.pdf



217. Title : Lower Bounds for Boxicity
     Speaker : L. Sunilchandran, IISc Bangalore
     Date, Time & Venue : Thu, Mar 22, 2012, 2:00 PM - CS34
     [Abstract]

     Boxicity of a graph is the minimum integer d, such that the graph can be represented as the intersection graph of axis parallel boxes in d-dimensional space. We give some methods to derive lower bounds for the boxicity of graphs. Using these methods, we show several interesting results, including lower bounds for random graphs.



218. Title : DAGic degree sequences
     Speaker : Prasun Kumar, IIT Madras
     Date, Time & Venue : Thu, Mar 15, 2012, 2:00 PM - CS36
     [Abstract]

     Abstract : Representation of graphs is a fundamental problem in algorithmic graph theory. One way of representing them is via their adjacency matrix /list, similarly degree sequence is another way of representing them at the cost of loosing uniqueness. Degree sequence of a graph is a sequence whose elements are the degrees of the vertices in the graph. This is a well studied topic and characterization of different graphs in terms of degree sequence has been given. In this talk we concentrate on DAGs and degree sequences of DAGs: where the fundamental question is about realizability of degree sequences with DAGs (checking whether the sequence is DAGic). For long time this was open, and recently a combinatorial characterization was given for an interesting subclass of sequences called - opposed sequences -. More recently, recognizing DAGic degree sequences has been shown to be NP-hard. We will present the sequence of ideas in these results.



219. Title : Characterization of matrices having Consecutive Ones Property
     Speaker : Subashini R., IIT Madras
     Date, Time & Venue : Thu, Mar 1, 2012, 2:00 PM - CS36
     [Abstract]

     Abstract: Consecutive Ones Property (COP) is a well studied combinatorial property of binary matrices. A binary matrix is said to have COP for rows, if there exists a permutation of columns such that in the resultant matrix ones in each row occur together as a single block. Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,...,n} to each of the subsets, does there exist a bijection f: S -> {1,...,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to the set system is feasible if there exists such a bijection. We characterize feasible interval assignments to a given set system and in turn use this characterization to characterize binary matrices having COP. Further, we will describe an algorithm that given a set system, assigns such an interval family (if one exists) and show how this can be used as a simple test for checking COP in binary matrices.



220. Title : A Recent Approach to Log-rank Conjecture.
     Speaker : Jayalal Sarma, IIT Madras
     Date, Time & Venue : Thu, Feb 23, 2012, 2:00 PM - BSB 361
     [Abstract]

     The talk will outline an approach (due to Ben-Sasson, Lovett and Zewi, Nov 2011) to prove a weaker form of log-rank conjecture. This line of attack is based on an older approach to the conjecture by Nisan and Widgerson (1995), but uses techniques and conjectures from additive combinatorics such as - approximate duality. We will introduce the basics needed, and will stick to a high-level view of the proofs. Here is the relevant paper : http://eccc.hpi-web.de/report/2011/157/



221. Title : An Introduction to Log-rank Conjecture
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Thu, Feb 16, 2012, 2:00 PM - CS36
     [Abstract]

     Abstract : In this talk we will discuss Log-rank conjecture which is one of the biggest open problems in Communication Complexity. First we will introduce the setting of communication complexity where the central question is about the minimum amount of communication needed by two players Alice and Bob to compute a function f, f: X x Y -> Z on a pair of inputs such that one input (x) known only to Alice and the other (y) known only to Bob. We will discuss an algebraic lower-bound method based on the rank of the communication matrix of a function which states that deterministic communication complexity of f is at least the log of the rank of the associated communication matrix. For some functions the above lowerbound can be significantly smaller than the actual communication cost, but how smaller is an interesting question. The log-rank conjecture introduced by Lovaz and Sakz [FOCS 1988] states that deterministic communication complexity of f is upperbounded by a poly-logarithmic function of its rank, (log rank(f))^c for an absolute constant c. Even though weaker versions of the above conjecture are known, no one has been able to settle the conjecture.



222. Title : Generalized Above Guarantee Vertex Cover and r-Partization
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Mon, Feb 13, 2012, 2:00 PM - BSB 361
     [Abstract]

     Abstract: Vertex cover and odd cycle transversal are minimum cardinality sets of vertices of a graph whose deletion makes the resultant graph 1-colorable and 2-colorable, respectively. As a natural generalization of these well-studied problems, we consider the Graph r-Partization problem of finding a minimum cardinality set of vertices whose deletion makes the graph r-colorable. We explore further connections to Vertex Cover by introducing Generalized Above Guarantee Vertex Cover, a variant of Vertex Cover. We study the parameterized complexity hardness of this problem by a reduction from r-Partization. We then describe sequacious fixed-parameter tractability results for r-Partization, parameterized by the solution size k and the required chromaticity r, in perfect graphs and split graphs. For Odd Cycle Transversal, we describe an O(2^k) algorithm for perfect graphs and a polynomial-time algorithm for co-chordal graphs.



223. Title : On Minimum Routing Cost Spanning Tree (MRCT)
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Thu, Feb 2, 2012, 2:00 PM - BSB 361
     [Abstract]

     Abstract : Given an undirected graph with nonnegative delays on the edges, the goal is to find a spanning tree such that the average delay of communicating between any pair using the tree is minimized. The dealy between any pair of vertices is the sum of the delays of the edges in the path between them in the tree. Two 2-approximation algorithms for MRCT will be discussed in this talk.



224. Title : On the Parameterized Approximability of Partial Vertex Cover
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Jan 17, 2012, 3:30 PM - BSB 361
     [Abstract]

     Abstract: Parameterized algorithmics and approximation algorithms are two popular ways to handle intractable problems. There are many problems for which neither of these approaches guarantee positive results. In such situations, it is interesting to investigate if a combination of these paradigms can achieve better algorithms than what any of the two theories could individually offer. In this talk, we study the parameterized approximability of the Partial Vertex Cover problem which is to maximize the number of edges covered by a set of k vertices in a graph. A generalization of the EPTAS (Efficient Polynomial-time Approx Scheme), referred to as FPT-AS (Fixed-parameter Tractable Approximation Scheme) will be discussed for this problem.



225. Title : Approximation algorithms for Unique Games
     Speaker : Mrinal Kumar, IIT Madras
     Date, Time & Venue : Tue, Jan 10, 2012, 3:30 PM - BSB 361
     [Abstract]

     Abstract: The paper discusses one of the first approximation algorithms for solving unique games after Subhash Khots original paper in 2002. The algorithm is based upon a semidefinite programming formulation of the problem and manages to satisfy a constant fraction of constraints when given an instance with value 1- O(frac{1}{log n}). Some of these ideas have been heavily used in the subsequent work on algorithms for unique games. Reference : http://theory.stanford.edu/~trevisan/pubs/unique.pdf



226. Title : Online and Off-line Algorithms for Self-Organizing Linear Search
     Speaker : Rakesh Mohanty, IIT Madras
     Date, Time & Venue : Tue, Nov 15, 2011, 3:00 PM - BSB 361
     [Abstract]

     Self-Organizing Linear Search, also known as List Accessing Problem(LAP) is a problem of signficant theoretical and practical interest since the pioneering work of McCabe in 1965. In this problem, we are given an input linear list of unsorted distinct items and a request sequence consisting of an arbitrary set of items(may be with repetitions) from the list. Each requested item in the request sequence is accessed one by one linearly in order by traversing the list from the beginning towards the end till the item is found, with some access cost based on the position of the item in the list. After each access, the list can be reorganized by incurring some reorganization cost. Our objective is to design efficient List accessing algorithms which process request sequences on lists to minimize the total access and reorganization cost. The important applications of LAP include data compression, resolving collisions in hash tables, maintaining identifiers in symbol table, computing point maxima in Computational Geometry. Design and Analysis of algorithms under the limitations of accessibility of input data, popularly known as, Online Algorithms, is a real challenging research area in Computer Science. In many real life problems and applications, the inputs are only partially available and some relevent input data arrives in future being not accesible at present. Online algorithms take decisions on the fly and generate output without knowledge of the entire input. In our work, we have made a comprehensive survey of Online and Offline Algorithms for LAP in a chronological way. The offline version of the LAP has already been proved to be NP-Hard. We have proposed an improved optimal offline algorithm for special class of request sequences which runs in polynomial time. Move-To-Front(MTF) algorithm has been proved to be the best deterministic online algorithm in the literature till date. We have proposed a new model of look ahead for LAP and an improved deterministic online variant of MTF Algorithm whose performance is found to be better than MTF for all request sequences from our experiemental and analytical results.



227. Title : Structural Characterization of Stable Vertex Separator Graphs
     Speaker : Sadagopan Narasimhan, IIT Madras
     Date, Time & Venue : Tue, Nov 8, 2011, 4:00 PM - BSB 361
     [Abstract]

     In this talk, we discuss the structural characterization of graphs in which every minimal vertex separator is an independent set (stable set). This problem is well motivated from the theory of contractible edges and constrained vertex separators.



228. Title : Distributed Tree Automata
     Speaker : Ajeesh Ramanujan, IIT Madras
     Date, Time & Venue : Tue, Nov 1, 2011, 3:30 PM - BSB 361
     [Abstract]

     In this talk I will give an introduction to tree automata, limitations of tree automata and how to overcome the limitation by introducing distribution.



229. Title : Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks
     Speaker : John Augustine, IIT Madras
     Date, Time & Venue : Thu, Oct 27, 2011, 3:30 PM - CS36
     [Abstract]

     Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds.



230. Title : Automorphisms on some Graph Classes
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Oct 4, 2011, 4:00 PM - BSB 361
     [Abstract]



231. Title : Treewidth of MDS and Reed-Muller Codes
     Speaker : Andrew Thangaraj, EE Dept, IIT Madras
     Date, Time & Venue : Tue, Sep 20, 2011, 4:00 PM - CS34
     [Abstract]

       The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parametrization of the maximum-likelihood decoding complexity for linear codes. In this talk, we present the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes. A basic background in finite-dimensional vector spaces and graph theory/algorithms will be assumed in the talk.



232. Title : Faster Vertex Covers via variants of Nemhauser-Trotter
     Speaker : Narayanaswamy N S, IIT Madras
     Date, Time & Venue : Tue, Sep 13, 2011, 4:15 PM - BSB 361
     [Abstract]

      The Nemhauser-Trotter theorem gives a LP relaxation based preprocessing step for the Vertex Cover problem.   A preprocessed instance has the property that All-Halves is the only optimum solution to the LP relaxation. We discover cutting planes which still retain the Nemhauser-Trotter properties in a certain sense and design branching algorithms for the vertex cover problem which beat the current best FPT algorithms for vertex cover



233. Title : On the Probablistic Method
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Tue, Aug 30, 2011, 3:30 PM - BSB 355
     [Abstract]

     Probabilistic method is a tool that is often used in proving the existence of a combinatorial object satisfying certain properties. In this talk, we will discuss the fundamental tools used in this technique and the breakthrough result by Erdos on graphs with high girth and high chromatic number.



234. Title : NEXP is not in non-uniform ACC^0 - An exposition
     Speaker : Sajin Koroth, IIT Madras
     Date, Time & Venue : Tue, Aug 16, 2011, 3:30 PM - BSB 361
     [Abstract]

     Todays theory seminar we are going to present a breakthrough paper in circuit complexity, by Ryan Williams. Published in November 2010 this paper proves lower bounds for non-uniform ACC circuits. Circuit complexity deals with complexity of computational problems where the underlying computational model is a circuit solving the problem. The class ACC, for which we are going to prove lowerbounds consists of circuit families with constant depth and having unbounded fan-in AND, OR, NOT and MOD_m gates(MOD_m gate outputs if the number of inputs which are 1 is divisible by m). A circuit family is called non-uniform if we know that for each input length "n" there exists a circuit solving the problem. But we need not know how to construct that cirucit, moreover it could be that the circuit might be "impossible" to compute also. We give the outline of the proof that NEXP requires superpolynomial size non-uniform ACC circuits. The details are omitted for the brevity of the talk. We assume no knowledge of circuit complexity, or advanced complexity theory from the audience. We will be giving a short introduction to all the concepts needed for the presentation of the paper. All are welcome



235. Title : On Constraint Tree Partition
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Aug 9, 2011, 3:30 PM - BSB 361
     [Abstract]

     Given a Tree T with a weight function w : V (T) → N and a capacity function c : V (T ) → N ∪ {0}, the tree c-partition problem decides whether there exists a partition of V (T) into V_1 , . . . , V_k for some 1 ≤ k ≤ |V (T)|, such that for 1 ≤ i ≤ k, T[V_i] is connected, V_i contains exactly one vertex u with c(u) ≥ w(u) and cost of V_i which is the sum of weights of vertices in V_i is at most c(u). I will present an O(n^2) algorithm for tree c-partition and its proof of correctness. Finally I will give a quick overview of connection between tree c-partition and minimum approximate distance preserving spanning trees in outerplanar graphs.



236. Title : On Classification of Ideal Secret Sharing Schemes
     Speaker : Chaya Ganesh, IIT Madras
     Date, Time & Venue : Tue, Jul 26, 2011, 4:00 PM - BSB 361
     [Abstract]

      The result by Brickell and Davenport almost completely characterize ideal secret sharing schemes. The paper gives a description of ideal secret sharing schemes in terms of classical combinatorial objects by showing an interesting connection between ideal secret sharing schemes and matroids. 

         In a secret sharing scheme, a dealer has a secret. There is a finite set of participants, P and a set T of subsets of P. A secret sharing scheme with T as the access structure is a method which the dealer can use to distribute shares to each participant so that a subset of participants can determine the secret if and only if that subset is in T. The share of a participant is the information sent by the dealer in private to the participant. A secret sharing scheme is ideal if the set of all possible shares is the same as the set of all possible secrets.


237. Title : Tree Path Labeling of Set Systems
     Speaker : Anju Srinivasan, IIT Madras
     Date, Time & Venue : Tue, Jul 12, 2011, 4:00 PM - BSB 361
     [Abstract]

     We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set U of cardinality n, a tree T on n vertices, and an assignment of paths from T to each of the subsets, does there exist a bijection f:U ightarrow {v_1,ldots,v_n} such that for each element of F, its image under f is same as the path assigned to it? A path assignment to a given set of subsets is called {em feasible} if there exists such a bijection. In this paper, we characterize feasible path assignments to a given set of subsets and a tree. This result is a natural generalization of results on matrices with the Consecutive Ones Property(COP) which can be viewed as a special instance of the problem in which the given tree is a path on n vertices. We also present a characterization of set systems and trees which have a feasible path assignment.



238. Title : Minimum Stretch Spanning Trees in Outer Planar Graphs
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Jul 5, 2011, 3:30 PM - BSB 361
     [Abstract]

     Given an unweighted graph G, a spanning tree T of G, for every pair of vertices if the distance in T is at most t times the distance in G, then T is called as tree t-spanner. The tree spanner with minimum t is called minimum stretch tree spanner (MSTS) or minimum stretch spanning tree (MSST). The problem of finding an MSTS in planar graphs is known to be NP-hard. A graph is outerplanar if it is planar and it can be drawn in a plane such that all the vertices lie on the unbounded face (exterior face). This talk mainly presents a polynomial time algorithm to find an MSTS in outerplanar graphs.



239. Title : Cubicity, Degeneracy and Crossing Number
     Speaker : Rogers Mathew, IISc Bangalore
     Date, Time & Venue : Tue, Jun 21, 2011, 3:30 PM - BSB 361
     [Abstract]

     A k-box B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 x R_2 x ... x R_k. If each R_i is a unit length interval, we call B a k-cube. The Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. It was shown by Chandran et al. that, for a graph G with maximum degree D, cub(G) <= lceil 4(D +1) log n ceil. In this talk, we show that, for a k-degenerate graph G, cub(G) <= (k+2) lceil 2e log n ceil. Since k is at most D and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(lceil 2.42 log n ceil + 1) dimensional cube representation for G. The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4} {lceillog t ceil}^{3/4}). This bound is tight upto a factor of O((log t)^{frac{3}{4}}).



240. Title : On a Conjecture related to Geometric Routing
     Speaker : Esha Ghosh, IIT Madras
     Date, Time & Venue : Tue, May 31, 2011, 2:00 PM - BSB 361
     [Abstract]

     The notion of greedy embedding was defined by Papadimitriou and Ratajczak (Theoretical Computer Science 2005), where the authors conjectured that every 3-connected planar graph has a greedy embedding (possibly planar and convex) in the Euclidean plane. A consequence of this conjecture is that in any ad-hoc network, containing such a graph as subgraph, 2-dimensional virtual coordinates can be found for which, the method of purely greedy geometric routing is guaranteed to work. We will discuss this conjecture and its equivalent forms, show that this hypothesis is as weak as possible. This conjecture has been proved by Leighton and Moitra recently (FOCS 2008). We will give a brief overview of the proof technique used and mention some related results.



241. Title : Polyhedral Combinatorics and the Maximum Independent Set
     Speaker : Krithika Ramaswamy, IIT Madras
     Date, Time & Venue : Wed, May 18, 2011, 3:30 PM - BSB 361
     [Abstract]

     Combinatorial Optimization searches for an optimal object in a finite collection of objects. Often, the collection has a concise representation (eg: graphs) but the number of objects in that collection is huge (eg: number of independent sets), probably exponential in the size of the representation. Such an optimization problem is polynomially solvable if it has an combinatorial structure that can be exploited by an "efficient" algorithm. In situations where identifying or exploiting this structure is difficult, a possible approach is to embed the instance of the problem in the Euclidean space and analyze its geometric structure to apply algebraic tools to ease the design of efficient algorithms. Such an approach is referred to as Polyhedral Combinatorics. Perfect graphs are an interesting class of graphs in which for every induced subgraph, the clique number and the chromatic number are same. There is no purely combinatorial polynomial algorithm known to solve the MIS problem on perfect graphs. The only efficient algorithm known uses polyhedral combinatorics and semidefinite programming. In this talk, we will discuss the polynomial solvability of the maximum independent set(MIS) problem on perfect graphs and other special graph classes using this approach.



242. Title : A Signature Scheme as Secure as the Diffie-Hellman Problem
     Speaker : Subhashini Venugopalan, IIT Madras
     Date, Time & Venue : Tue, May 10, 2011, 3:30 PM - BSB 361
     [Abstract]

     In this talk, we will be presenting the analysis, given by Goh and Jarecki, of a signature scheme which has tight security reduction to the computational Diffie-Hellman (CDH) problem. As a precursor to the talk, we will discuss briefly, the notions of tight-reduction, and hardness of problems, with specific attention to the CDH assumption. We will then look into the security setting and model. After that, we will describe the (EDL) signature scheme and see the intuition used in achieving tight-reduction. Finally, we will show the proof of security of the scheme by reducing it to the CDH problem. Update : The slides of the talk are shared here :
     http://www.slideshare.net/vsubhashini/goh-jarecki



243. Title : Symmetry Breaking via Oriented Graphs
     Speaker : Kishore Kothapalli, IIIT Hyderabad
     Date, Time & Venue : Tue, Apr 19, 2011, 4:00 PM - BSB 361
     [Abstract]

     Symmetry breaking is an important problem in distributed computing and arises in several fundamental problems such as graph coloring, MIS, and the like. In this talk, we describe a novel approach to symmetry breaking in distributed graph algorithms where the edges of the graph are equipped with an orientation. Orientation on the edges allows the end points of the edges to break symmetry between them. The talk describes the following results from recent works in IPDPS 2006, AINA 2010, and PODC 2011. Firstly, we show that the vertices of an oriented graph can be colored with O(D) colors in O(sqrt{log n}) rounds with high probability. Further, such a coloring can be obtained by exchanging essentially O(log Delta + sqrt{log n}) bits. We show that indeed O(sqrt{log n})-bits need to be exchanged by any randomized graph coloring algorithm. In the second part of the talk, we extend the above result in two directions. In one direction, we consider the case when the coloring algorithm has at its disposal only a certain k number of rounds. We show that when k is at least 2log log n, the vertices of G can be colored with O(Delta_o) colors in O(k) rounds. Our result requires extending the Brooks-Vizing type coloring algorithm of Grable and Panconesi (SODA 1998) to oriented graphs. In the above, Delta_o refers to the maximum outdegree of any vertex according to the given orientation. Combining our result above with the recent result of Barenboim and Elkin (PODC 2010), one can get that a graph of arboricity a can be colored with O(an1/k) colors in k rounds for k = Omega(log log n). ---------------------------------------------------------- Speaker Bio: Kishore Kothapalli is presently an Assistant Professor at the International Institute of Information Technology, Hyderabad, where he is working since 2006. His research interests lie in distributed and parallel algorithms, multicore computing, and graph algorithms. Prior to that, he completed his Ph. D. in Computer Science from the Johns Hopkins University, Baltimore, USA. His doctoral work included novel topological designs and routing algorithms for peer-to-peer networks and wireless ad hoc networks. He has published in leading conferences such as SPAA, PODC, ICS, and in journals such as Discrete Mathematics, Parallel Processing Letters, and IPL. Homepage: http://cstar.iiit.ac.in/~kkishore/



244. Title : A framework for connectivity augmentation in graphs
     Speaker : Sadagopan Narasimhan, IIT Madras
     Date, Time & Venue : Tue, Apr 12, 2011, 4:00 PM - BSB 361
     [Abstract]

     For a connected graph, a subset of vertices of least size whose deletion increases the number of connected components is the vertex connectivity of the graph. A graph with vertex connectivity k is said to be k-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k+1)-vertex connected. In this talk, we report our study on connectivity augmentation in 1-connected graphs, 2-connected graphs, and k-connected chordal graphs. We first represent the graph under consideration using a tree-like graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear time algorithm for optimum connectivity augmentation. Our novelty is in the data structure which is a unified framework for all three augmentations. As far as the run time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time.



245. Title : Representation of Coalitional Games with Algebraic Decision Diagrams
     Speaker : Karthik V. Aaditya, UC Berkeley
     Date, Time & Venue : Thu, Apr 7, 2011, 2:00 PM - BSB 361
     [Abstract]

     Many real-world situations are characterised by co-operation amongst multiple individuals. Players in a cricket team, co-workers in an office, lions in a pride - all have to work together in order to achieve common ends, realize collective payoffs or share common goods/costs. Such situations give rise to a very natural and interesting question: Given that a set of individuals have chosen to strategically cooperate with one another, and given the abilities and limitations of each individual, how should the benefits gained by strategic co-operation be divided amongst the cooperating agents? Historically, this question of "payoff division" has fallen under the realm of coalitional game theory (also known as cooperative game theory), where such situations are modelled through the mathematical framework of a coalitional game. Many solution concepts such as the core, the Banzhaf Index and the Shapley Value have been proposed for payoff division in coalitional games. More recently, computer scientists have offered a fresh perspective on the payoff division question, by considering it from a computational complexity standpoint. Indeed, computer scientists have created an entirely new field of algorithmic coalitional game theory, where the emphasis for the payoff division problem has shifted from "developing solution concepts" to "computing solution concepts". With the new emphasis on solution concept computation, the key question is: ``How should coalitional games be represented so that solution concepts can be computed as efficiently as possible?'. The traditional, mathematical representation for coalitional games is no longer adequate because, irrespective of the game, it is always of length exponential in the number of agents. Thus, compactness and computational efficiency are the two key requirements of a representation scheme for coalitional games. In this talk, I will first describe the fundamentals of cooperative game theory, focusing particularly on solution concepts associated with the payoff division problem (including the core, the $epsilon$-core, the Banzhaf Index, Shapley Value, Cost of Stability, etc.). I will then proceed to describe a new method for representing coalitional games, based on the Algebraic Decision Diagram data structure. I will show that this representation (a) is fully expressive (i.e., can be used to represent any coalitional game), (b) is compact (i.e., has size polynomial in the number of agents) for many games of practical interest, (c) enables polynomial time Banzhaf Index and Shapley Value computation, (d) enables polynomial time algorithms for several core-related questions, such as testing membership in the core, checking if the core is empty and computing the smallest $epsilon$ such that the strong-$epsilon$ core is non-empty, and (e) enables polynomial time Cost of Stability computation.



246. Title : Regulated Rewriting
     Speaker : Kamala Krithivasan, IIT Madras
     Date, Time & Venue : Tue, Mar 29, 2011, 4:00 PM - BSB 361
     [Abstract]

     We consider some grammars by putting restrictions on the manner of applying the rules. We consider Matrix grammars, Programmed grammars, Time varying grammars, and grammars with Regular control. We introduce the concept of appearance checking also. It is seen that with type 2 rules, the powers of these grammars with appearance checking equals the power of type 0 grammars., i.e., any recursively enumerable language could be generated. The notion of Indian Parallel Grammar will also be introduced.



247. Title : Characterization matrices of having Consecutive Ones Property
     Speaker : Subashini R., IIT Madras
     Date, Time & Venue : Tue, Mar 22, 2011, 4:00 PM - BSB 361
     [Abstract]

     Abstract: Consecutive Ones Property (COP) is a well studied combinatorial property of Binary matrices. A binary matrix is said to have COP for rows, if there exists a permutation of columns such that in the resultant matrix ones in each row occur together as one block. Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,...,n} to each of the subsets, does there exist a bijection f: S -> {1,...,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to the set system is feasible if there exists such a bijection. We characterize feasible interval assignments to a given set system. We use this characterization to characterize binary matrices having COP. This talk will discuss about checking the feasibility of interval assignments and its application in characterizing matrices having COP.



248. Title : Multiplicative Additive error Spanning trees in distance
     Speaker : Ramakrishna G., IIT Madras
     Date, Time & Venue : Tue, Mar 15, 2011, 3:30 PM - BSB 361
     [Abstract]

     The multiplicative tree t-spanner is a spanning tree of a graph such that for every pair of vertices distance in the tree is at most t times their actual distance in the graph. The additive tree t-spanner is a spanning tree of a graph such that for every pair of vertices distance in the tree and their actual distance in the graph differs by at most t. A graph is distance hereditary when every induced path is a shortest path. An independent set of three vertices is called an asteroid triple if between each pair in the triple there exists a path that avoids the neighborhood of the third. A graph is asteroidal triple free (AT-free) if it contains no asteroid triple. This talk presents the construction of multiplicative tree 3-spanners in distance hereditary graphs, construction of additive tree 3-spanner in AT-free graphs, and their correctness.



249. Title : Rigidity and Complexity of Linear Transformations.
     Speaker : Jayalal Sarma, IIT Madras
     Date, Time & Venue : Tue, Mar 8, 2011, 3:30 PM - BSB 361
     [Abstract]

     This talk will discuss the complexity of computing linear transformations. We will outline the known complexity bounds briefly and then introduce some nice graph theoretic arguments related to this problem leading to the connection to the notion of rigidity of a matrix. Proving super-linear bounds for the rigidity of an explicit family of matrices will imply break-the-barrier type lower bounds in the complexity of linear transformations, and hence this remains an important open problem in the area. We will present the arguments leading to the current frontier results on this problem.