Theory Seminar @ IITH

• 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).