Theory Seminar @ IITH

• 28 February 2024: Flexible list colorings
  
  Speaker: Rogers Mathew, IITH.
  
  Venue and Time: C-LH2, 1400-1500 hrs.
  
  Abstract:In classical vertex coloring we wish to color the vertices of a graph G with up to m colors from [m] so that adjacent vertices receive different colors, a so-called 'proper m-coloring'. List coloring is a well-known variation of classical vertex coloring that was introduced independently by Vizing and Erdos, Rubin, and Taylor in the 1970s. For list coloring, we associate a 'list assignment' L with a graph G such that each vertex v in G is assigned a list of colors L(v) (we say L is a list assignment for G). An 'L-coloring' of G is a function f with domain V(G) such that f(v) is a member of L(v) for every vertex v in G. We say that G is 'L-colorable' if there exists a proper L-coloring of G: an L-coloring where adjacent vertices receive different colors. A list assignment L for G is called a 'k-assignment' if |L(v)|=k for each vertex v in G. We say G is 'k-choosable' or 'k-list colorable' if G is L-colorable whenever L is a k-assignment for G. The 'list chromatic number' of G is the smallest k such that G is k-choosable.
  
  Flexible list coloring was introduced in [Dvorak, Norin, and Postle. "List coloring with requests", J.Graph Theory (2019)] in order to address a situation in list coloring where we still seek a proper list coloring, but a preferred color is given for some subset of vertices and we wish to color as many vertices in this subset with its preferred colored as possible, a flexible version of the classical precoloring extension problem. In this talk, we explore the notion of Flexible list colorings. This talk is based on the paper [Kaul, Mathew, Mudrock, and Pelsmajer. "Flexible list colorings: Maximizing the number of requests satisfied", to appear in J. Graph Theory].



• 24 January 2024: Chess is hard, even for a single player
  
  Speaker: N R Aravind, IITH.
  
  Venue and Time: C-LH3, 1200-1300 hrs.
  
  Abstract: Can we design efficient algorithms to find a winning strategy in chess? Go? Solitaire? Such questions have been of interest for a long time in computer science. In 1981, a generalization of chess was shown to be EXP-complete. Popular games like Checkers, Go, Othello, and various combinatorial games have been studied from the computational perspective.
  
  In this talk, we will discuss some results on the complexity of a single-player version of chess, introduced in 2021 by the platform chess.com. Try it here: https://www.chess.com/solo-chess
  
  This is a joint work with Neeldhara Misra and Harshil Mittal, and was presented in FUN 2022.



• 17 January 2024: An Introduction to Approximate Degree
  
  Speaker: Nitin Saurabh, IITH.
  
  Venue and Time: C-LH3, 1200-1300 hrs.
  
  Abstract: I will talk about the notion of approximate degree of Boolean functions. This notion originated roughly 30 years back in the seminal work of Nisan and Szegedy (Computational Complexity 1994). Since then it has become a powerful and versatile tool in theoretical computer science finding spectacular applications in circuit complexity, quantum query complexity, communication complexity, computational learning, and differential privacy, to name a few.
  
  This talk will introduce an important problem about approximate degree -- Does it compose? More formally, is it true that adeg( f o g) = \Omega( adeg(f) x adeg(g) ), where adeg(f) represents the approximate degree of f and f o g represents the composition of two functions f and g on disjoint sets of variables?
  
  We plan to cover a particular case of the composition question. No prior knowledge will be assumed. This talk is based on the works of Nisan and Szegedy (Computational Complexity 1994), Sherstov (Theory of Computing 2013), and Bun and Thaler (Information and Computation 2015).

• 19 April 2023: Rabbits Approximate, Cows Compute Exactly!
  
  Speaker: Nitin Saurabh, IITH.
  
  Venue and Time: C-LH6, 1200-1300 hrs.
  
  Abstract: Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants, showing that VF, the class of polynomial families computable by polynomial-sized algebraic formulas, is contained in VDet, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing open problem. It is thus natural to ask what is the simplest class of matrices whose determinants exactly capture algebraic formulas?
  
  In this talk I will give an answer to the above question and, of course, explain the title!
  
  This is based on a joint work with Balagopal Komarath (IIT Gandhinagar) and Anurag Pandey (IIT Madras).



• 15 March 2023: From Sum-of-Squares Proofs to Approximation Algorithms
  
  Speaker: Rakesh Venkat, IITH.
  
  Venue and Time: C-LH4, 1200-1300 hrs.
  
  Abstract: One possible certificate for demonstrating the non-negativity of a boolean function on n variables is to express it as a sum of squares of polynomials. Of particular interest are functions that are the sums-of-squares of polynomials of low degree, as one can hope to efficiently find these succinct certificates. Over the last decade, a close connection has emerged between this class of functions and the design of approximation algorithms: the natural Linear and Semidefinite programming relaxations for many problems turn out to be *dual* to the problem of finding certain low degree sum-of-squares certificates.
  
  In this talk, we will introduce this connection and view well-known problems such as Min-Cut, Max-Cut and Sparsest-Cut via the lens of Sum-of-Squares Proof systems. We will also highlight some of the important open questions in this context.



• 23 February 2023: Depth-3 Circuit Lower Bounds for k-OV
  
  Speaker: Tameem Choudhury, IITH.
  
  Venue and Time: C-LH6, 1200-1300 hrs.
  
  Abstract: The 2-Orthogonal Vectors problem(2-OV) is defined as follows: given two tuples A and B of n vectors each of dimension d, decide if there exists a vector u in A and v in B such that u and v are orthogonal. The problem 2-OV and its generalisation k-OV, defined analogously for k tuples are important problems as they reduce to a number of seemingly unrelated problems such as Longest Common Subsequence, Edit Distance, Regular Matching etc with very little resource overhead. So, a lower bound for k-OV will also imply lower bounds for these problems.
  
  In this talk, we will show that any OR-AND-OR circuit with bottom fan-in t computing 2-OV requires size at least (n/t)^2. We also show that any OR-AND-OR circuit with bottom fan-in t computing k-OV requires size at least (n/t)^k. When k is constant, the bound is tight for k=t.
  
  This talk is based on a joint work with Dr. Karteek Sreenivasaiah (IITH).



• 8 February 2023: A Discrete and Bounded Locally Envy-Free Cake Cutting Protocol on Trees
  
  Speaker: Ganesh Ghalme, IITH.
  
  Venue and Time: C-LH9, 1200-1300 hrs.
  
  Abstract: We consider the classic problem of fairly allocating a divisible resource--- referred to as a cake. An important question in the area of cake-cutting is to find a tractable algorithm to compute envy-free cake divisions. In a landmark result, Aziz and Mackenzie(2016) gave an algorithm for computing such a division with query complexity having towers of exponent (in the number of agents, n). On the other hand, the best-known lower bound for the same is $\Omega(n^2)$, leaving a huge gap in our understanding of the query complexity of the problem.
  
  In this talk, I will consider a variant of the problem where agents are embedded in a graph and each agent evaluates her share relative to those of her neighbours. Given a graph, the goal is to find a locally envy-free allocation where every agent values her share of the cake to be at least as much as that of any of her neighbours' share. We believe that the machinery developed in this work provides new insights for understanding the computational bottleneck for finding envy-free cake divisions.
  
  This is based on joint work with Xin Huang (Technion, Israel), Yuka Machino (MIT, USA) and Nidhi Rathi (Aarhus University, Denmark).



• 1 February 2023: Algorithms for some constrained geometric dispersion problems
  
  Speaker: Manjanna B, BITS Pilani, Hyderabad Campus.
  
  Venue and Time: C-LH6, 1200-1300 hrs.
  
  Abstract: Obnoxious facility dispersion problems involve maximizing the separation between facilities, which will, in turn, minimize the negative impact they have on each other. This will also minimize the negative impacts that facilities have with demand points, which, in turn, minimizes risk issues at the demand sites. In the literature, the dispersive quality of these facilities is generally captured through basic objectives: MaxMin, MaxSum, or MinSum. While the generalized dispersion problems, even in the Euclidean plane, are NP-hard, many restricted variants can be solved exactly in polynomial time. The focus of my talk will be mainly on exact algorithms for solving some of these dispersion problems constrained to a line segment and convex polygon.



• 18 January 2023: About the recent progress in the Union-Closed Sets conjecture
  
  Speaker: Rogers Mathew, IITH.
  
  Venue and Time: C-LH10, 1200-1300 hrs.
  
  Abstract: A family of subsets of {1, 2, ..., n} is union-closed if for every two sets in the family their union is also present in the family. A famous conjecture related to union-closed families is Frankl's Union-Closed Sets Conjecture (UCS Conjecture). It states that for every union-closed family F of subsets of {1,2,...,n}, there exists an element e in {1,2,...,n} such that e is present in at least half the number of sets in F. In other words, the UCS conjecture states that there exists an e in {1,2, ...,n} such that |F_e| >= |F|/2, where F_e denotes the collection of sets in F that contain the element e. The best known general result so far on the conjecture is due to [Knill] (Wojcik made a minor improvement to this later) which says that there is an element e which is present in at least 1/log(|F|) fraction of the sets in F.
  
  This talk is based on a very recent paper (see [Gilmer]) that appeared in arxiv which makes significant progress towards resolving the conjecture. The paper proves that there is an element e which is present in at least 1/100 fraction of the sets in F. The emphasis of this talk will be to show an outline of the proof of this result.



• 11 January 2023: Karchmer-Wigderson games for Hazard-free Computation
  
  Speaker: Nitin Saurabh, IITH.
  
  Venue and Time: C-LH-6, 1545-1700 hrs.
  
  Abstract: Hazards are spurious pulses or electronic glitches that may occur on the output of circuits during an input transition. It occurs due to physical delays at wires or gates in a specific hardware implementation of the circuit. A hazard-free circuit guarantees that no glitches will occur in any hardware implementation of this circuit, regardless of the physical delays.
  
  In this talk I will present a game between the two quintessential protagonists in computer science, namely, Alice and Bob. We will show that this game captures the complexity of hazard-free computations exactly! As an application, we will give exact bounds for computing the Multiplexer function in a hazard-free way.
  
  This talk is based on a joint work with Christian Ikenmeyer (University of Warwick) and Balagopal Komarath (IIT Gandhinagar).