Theoretical Computer Science @ IIT Bombay
Theory Seminar
The talks are announced in the theory-seminar mailing-list.- Advancing the frontiers in Propositional Proof Complexity
[Feb 28 2023 +]
Date: Feb 28, 2023 Time: 10:30-11:30 Venue: online
Abstract: Abstract: Proof theory is a foundational field of modern mathematics, dealing with study of the structure of mathematical proofs. It has a rich history starting with Aristotle's intuitive notions of a rigorous proof, Euclid's semi-formal system of logic underlying geometry, Frege's notions of a formal system of logic with a complete set of inference rules, Hilbert's attempted program to formalize the whole of mathematics, Gödel's incompleteness results that put an end to this program, and finally Turing's seminal paper building on Gödel's work defining a formal notion of a computer and laying the foundations of most of theoretical computer science as we know it today.
In modern computer science, we are interested in computational aspects of these classical notions. Proof complexity is an area that studies lengths of proofs in formal systems of logic. In this talk, we will go over state of the art lower bounds on proofs in well studied systems of propositional logic proved over the past few decades. We will then touch upon our recent work that proves new connections between known proof systems, and new boundary-pushing lower bounds building on recent developments. We will conclude with some of the most interesting open problems in this area.
- Exploring Algebraic Methods: Applications and Key Challenges in Polynomials [Feb 21 2023 +]
Date: Feb 21, 2023 Time: 10:00-11:00 Venue: online
Abstract: Polynomials are widely used throughout computer science, ranging from heavily applied algorithms in signal processing to purely theoretical endeavors in complexity theory. So, what makes polynomials so applicable across domains? And what are the fundamental problems linked with polynomials? In this talk, we will address these questions.
For this, the talk will focus on the following two very different problems, striking a balance between purely structural questions about polynomials and applications in other domains.
Decomposing Low-Rank Tensors: Tensor decomposition is a basic computational primitive underlying many algorithms for various data analysis tasks. Due to known NP hardness results, most known algorithms for this task are either average-case or heuristic. We will present a *worst-case* algorithm for decomposing low-rank tensors. This algorithm is grounded in the intriguing connection between tensor decomposition and the learning of special depth-3 arithmetic circuits.
Factoring Sparse Polynomials: Shifting towards more structural inquiries: Are factors of sparse polynomials themselves sparse? In other words, can multiplying polynomials lead to massive cancellation? To establish bounds, we will employ tools from convex geometry, including the theory of Newton polytopes and an approximate version of Carathéodory's Theorem.
We will conclude by giving a bird's-eye view of some of the exciting research directions and questions pertaining to this theme.
- Walker-Breaker hamiltonicity game on Random board [Feb 13 2024 +]
Date: Feb 13, 2024 Time: 14:00-15:00 Venue: online
Abstract: The Maker-Breaker connectivity game and Hamilton cycle game belong to the best studied games in positional games theory, including results on biased games, games on random graphs and fast winning strategies. Recently, the Connector-Breaker game variant, in which Connector has to claim edges such that her graph stays connected throughout the game, as well as the Walker-Breaker game variant, in which Walker has to claim her edges according to a walk, have received growing attention. For instance, London and Pluhár studied the threshold bias for the Connector-Breaker connectivity game on a complete graph and showed that there is a big difference between the cases when the Maker’s bias equals 1 or 2. Moreover, a recent result of Clemens, Mogge, and Kirsch shows that the threshold probability p for the (2 : 2) Connector-Breaker connectivity game on a random graph G ~ G(n,p) is of order \(n ^{-2/3 + o(1)}\). We extend this result further to Walker-Breaker games and prove that this probability is also enough for Walker to create a Hamilton cycle.
- Parallel Repetition of k-Player Projection Games [Jan 24 2024 +]
Date: Jan 24, 2024 Time: 11:00-12:00 Venue: CC109
Abstract: In a k-player game, \(k \geq 2\), a verifier sends k questions according to a fixed distribution to k provers. The provers, without communicating with each other, respond with their answers. The verifier then decides, based on the question-tuple and the received answer tuple, whether to accept or reject. The value of the game is the maximum, over the provers' strategies, the accepting probability of the verifier.
In a n-fold parallel repetition of the game, the verifier samples n independent question tuples and sends the respective questions to the provers. The provers again respond with answers to every question they receive. The verifier accepts if all the n question-tuples and answer-tuples are accepted by the verifier in a single round game.
Certainly, if the value of a game is 1, then the value of the n-fold parallel repetition of the game is also 1. One important question is: How does the value of the n-fold parallel repetition of a game decay, if the value of the game is <1 to begin with?
While we know the answer to this question for 2-player games, the situation in the k player games is far from being resolved. In this talk, I will discuss k-player projection games, which is a generalization of 2-player projection games. We show that if the value of a k player projection game is <1, then the n-fold parallel repetition of the game has value at most \(exp(-\Omega(n))\).
Based on a joint work with Mark Braverman, Subhash Khot, Yang P. Liu, and Dor Minzer.
- Fast Numerical Multivariate Multipoint Evaluation [Jan 10 2024 +]
Date: Jan 10, 2024 Time: 15:00-16:00 Venue: CC109
Abstract: Abstract: Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of evaluation 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 basic question in computational algebra.
The classical FFT algorithm gives such an algorithm for the special case of univariate polynomials and a well-structured set of evaluation points (say roots of unity). Only as recently as last year, was the multivariate version of this problem for all sets of evaluation points resolved for finite fields due to the works of Bhargava, Ghosh, Guo, Kumar & Umans.
The case of infinite fields (eg, reals, rationals) is complicated due to subtleties arising from the bit-complexity of the output compelling one to work with either an approximate version of the problem or an exact version where the algorithm is allowed to run in time nearly-linear in the output size. Only as recently as 2021, was the univariate version of this problem over infinite fields resolved by Moroz.
In this talk, we will show how to extend these results to obtain similar nearly-linear time results for the multivariate version of the problem over infinite fields such as rationals, reals both in the approximate and exact setting.
[Joint work with Sumanta Ghosh, Simao Herdade, Mrinal Kumar and Ramprasad Saptharishi]
- List Decoding of Tanner and Expander Amplified Codes from Distance Certificates [Jan 10 2024 +]
Date: Jan 10, 2024 Time: 11:00-12:00 Venue: CC109
Abstract: In the theory of error-correcting codes, list decoding is a relaxation of unique decoding useful for tolerating higher levels of noise. Design of list decoding algorithms for algebraic codes, such as Reed-Solomon, has found numerous applications in error correction, as well as in complexity theory and pseudorandomnness. However, we know of very few techniques for list decoding algorithms when the code may not have such algebraic structure, such as Tanner codes which are defined using sparse expander graphs.
In this talk, I will describe how continuous relaxations based on the Sum-of-Squares hierarchy can be used to design the first list decoding algorithm for Tanner codes of Sipser-Spielman [IEEE Trans. Inf. Theory 1996]. The techniques include a novel proof of the Johnson bound for arbitrary codes, distance proofs for pseudocodewords, and correlation rounding for convex hierarchies. I will also discuss extensions to a distance amplification scheme of Alon-Edmonds-Luby [FOCS 1995].
Based on joint work with Fernando Granha Jeronimo and Madhur Tulsiani.
- On various notions of negative dependence [Jan 4 2024 +]
Date: Jan 4, 2024 Time: 16:00-17:00 Venue: CC109
Abstract: "Negative dependence" captures the intuitive notion of random variables being negatively correlated and comes in various forms, from the relatively-weak "cylinder negative correlation" (even which suffices to get Chernoff-style large-deviation bounds) all the way to the much-stronger "Strongly Rayleigh" distributions. I will survey some aspects of this vast area.
- Linear Independence, Alternants, and Applications [Dec 15 2023 +]
Date: Dec 15, 2023 Time: 15:00-16:00 Venue: CC109
Abstract: In this talk, we will discuss a new technique for analyzing the linear independence of multivariate polynomials. At the core is a Small Witness for Linear Independence lemma, which states the following. If the polynomials \(f_1, f_2, ..., f_k \in \mathbb{F}[X]\) over \(X=\{x_1, ..., x_n\}\) are \(\mathbb{F}\)-linearly independent then there exists a subset \(S \subseteq X\) of size at most \(k-1\) such that \(f_1, f_2, ..., f_k\) are also \(\mathbb{F}(X \setminus S)\)-linearly independent. An amalgamation of this structural result along with the alternant matrix gives us a criterion for testing linear independence. Moreover, we'll explore how this technique can be applied to address inquiries concerning polynomial identity testing and the learning of arithmetic circuits. The talk is based on joint work with Shubhangi Saraf and Ilya Volkovich.
- Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time [Dec 11 2023 +]
Date: Dec 11, 2023 Time: 15:00-16:00 Venue: CC109
Abstract: Rational Identity Testing (RIT) is the decision problem of determining whether or not a noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg, Gurvits, Oliveira, and Wigderson (2016); Ivanyos, Qiao, Subrahmanyam (2018); Hamada and Hirai (2021)], and a randomized polynomial-time algorithm [Derksen and Makam (2017)] in the black-box setting, via singularity testing of linear matrices over the free skew field. Indeed, a randomized NC algorithm for RIT in the white-box setting follows from the result of Derksen and Makam (2017). Designing an efficient deterministic black-box algorithm for RIT and understanding the parallel complexity of RIT are major open problems in this area. Despite being open since the work of Garg, Gurvits, Oliveira, and Wigderson (2016), these questions have seen limited progress. In fact, the only known result in this direction is the construction of a quasipolynomial-size hitting set for rational formulas of only inversion height two [Arvind, Chatterjee, Mukhopadhyay (2022)]. In this paper, we significantly improve the black-box complexity of this problem and obtain the first quasipolynomial-size hitting set for all rational formulas of polynomial size. Our construction also yields the first deterministic quasi-NC upper bound for RIT in the white-box setting. Joint work with V. Arvind (IMSc) and Partha Mukhopadhyay (CMI).
- Lower bounds for Polynomial Calculus with extension variables over finite fields [Dec 7 2023 +]
Date: Dec 7, 2023 Time: 11:00-12:00 Venue: Online
Abstract: Propositional proof complexity aims to prove lower bounds against tautological Boolean formulae for increasingly strong proof systems, with the ultimate goal of separating NP and coNP. A major open problem in this area is lower bounds for \(AC^0[p]\)-Frege proofs. Since lower bounds for the corresponding circuit class \(AC^0[p]\) were proved by Razborov and Smolensky through algebraic means, algebraic proof systems such as Nullstellensatz (Beame et. al.) and Polynomial Calculus (Clegg et. al.) were introduced with the intention of better understanding \(AC^0[p]\)-Frege. Lower bounds for the former systems have been obtained but it has not led to much progress for the latter. In this talk we will show how to obtain lower bounds for a weak version of Polynomial Calculus with extension variables, a proof system which with strong enough extension variables can simulate \(AC^0[p]\)-Frege. In particular we show that for every prime \(p\) and \(n > 0\), there exist tautologies over \(O(n \log n)\) variables of degree \(O(\log n)\) such that any Polynomial Calculus proof with \(o(n^2)\) extension variables, each depending on \(O(\log n)\) original variables requires exponential size. This builds on a recent work of Sokolov (STOC 2020) and is joint work with Russell Impagliazzo and Toniann Pitassi, appearing in CCC 2023. We will also discuss recent improvements on this lower bound in joint work with Yogesh Dahiya and Meena Mahajan, where we show how to handle the same number of extension variables, each of which is of polynomial size and can depend on \(O(n^(1-epsilon))\) original variables.
- Half-Guarding Weakly-Visible Polygons and Terrains [Dec 6 2023 +]
Date: Dec 6, 2023 Time: 11:00-12:00 Venue: Online
Abstract: In this talk, we will discuss a variant of the art gallery problem. The art gallery problem asks for the minimum number of guards required to guard an art gallery represented as a simple polygon. We consider a variant of the problem where the polygon is weakly-visible and the guards are restricted to see only to its right side with respect to the given coordinate axes. In other words, all guards are limited to seeing 180°. Guards that can only see in one direction are called half-guards. We will discuss a polynomial-time approximation scheme (based on local search) for vertex guarding the vertices of a weakly visible polygon with half-guards. We extend this to vertex guarding the boundary of a weakly-visible polygon with half-guards.
- Ramsey simplicity of Random graphs [Nov 27 2023 +]
Date: Nov 27, 2023 Time: 14:30-15:30 Venue: Online
Abstract: A graph G is q-Ramsey for another graph H if in any q-edge-colouring of G there is a monochromatic copy of H, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, Erdős, and Lovász to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree.
It is not hard to see that if G is minimally \(q\)-Ramsey for \(H\) we must have \(δ(G) ≥ q(δ(H) - 1) + 1\), and we say that a graph H is q-Ramsey simple if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph G(n,p) is almost surely 2-Ramsey simple when \(\log (n)/n ≪ p ≪ n^{-2/3}\). In this work, we explore this question further, asking for which pairs \(p = p(n)\) and \(q = q(n,p)\) we can expect \(G(n,p)\) to be \(q\)-Ramsey simple. We resolve the problem for a wide range of values of p and q; in particular, we uncover some interesting behaviour when \(n^{-2/3} ≪ p ≪ n^{-1/2}\). This is a joint work with Simona Boyadzhiyska, Dennis Clemens, and Shagnik Das.- Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth and Vertex Cover [Nov 21 2023 +]
Date: Nov 21, 2023 Time: 11:00-12:00 Venue: Online
Abstract: Treewidth serves as an important parameter that, when bounded, yields tractability for a wide class of problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and Quantified SAT or, more generally, Quantified CSP, are Fixed-Parameter Tractable parameterized by the treewidth of the input’s (primal) graph plus the length of the MSO-formula. The algorithms generated by this (meta-)result have running times whose dependence on treewidth is a tower of exponents. A conditional lower bound by Fichte, Hecher, and Pfandler [LICS 2020] shows that, for Quantified SAT, the height of this tower is equal to the number of quantifier alternations. These types of lower bounds, which show that at least double-exponential factors in the running time are necessary, exhibit an extraordinary level of computational hardness for such problems, and are rare in the current literature: there are only a handful of such lower bounds (for treewidth and vertex cover parameterizations), and all of them are for problems that are #NP-complete, \(\Sigma_p^2\)-complete, \(\Pi_p^2\)-complete, or \(\#P\)-complete for even higher levels of the polynomial hierarchy.
Our results demonstrate, for the first time, that it is not necessary to go higher up in the polynomial hierarchy to achieve double-exponential lower bounds: we derive double-exponential lower bounds in the treewidth (tw) and the vertex cover number (vc), for natural, important, and well-studied NP-complete graph problems. Specifically, we design a technique to obtain such lower bounds and show its versatility by applying it to three different problems: Metric Dimension, Strong Metric Dimension, and Geodetic Set. For the lower bounds, we design and use a novel yet simple technique based on the Sperner families of sets.
- Algorithms Approaching the Threshold for Semirandom Planted Clique [Oct 23 2023 +]
Date: Oct 23, 2023 Time: 11:30-12:30 Venue: CC109
Abstract: This talk is about a polynomial time algorithm to recover planted cliques in the semirandom model introduced by Feige and Kilian in 1998. The previous best algorithms for this model succeed if the planted clique is of size at least \(n^{2/3}\) in a graph with n vertices. Our algorithms work for planted cliques of a size approaching \(n^{1/2}\) -- the information-theoretic threshold in the semirandom model and the conjectured computational threshold even in the easier fully-random model. The result nearly resolves open questions of Feige and Steinhardt.
Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite Erdős–Rényi random graphs into algorithms for semi-random planted cliques. The previous best guarantees for semi-random planted cliques (similar to the fully random version) correspond to basic SDP relaxations of biclique numbers. We construct an SDP lower bound that shows that the \(n^{2/3}\) threshold in prior works is an inherent limitation of these spectral relaxations.
Our key innovation is a new geometric certificate for biclique numbers that can be formalized in a higher constant degree sum-of-squares proof system.
Joint work with Rares Buhai (ETH Zurich) and David Steurer (ETH Zurich).
- Many Nodal Domains in Random Regular Graphs [Oct 11 2023 +]
Date: Oct 11, 2023 Time: 10:00 - 11:30 Venue: Online
Abstract: A nodal domain of a Laplacian eigenvector of a graph is a maximal connected component where it does not change sign. Sparse random regular graphs have been proposed as discrete toy models of "quantum chaos", and it has accordingly been conjectured by Y. Elon and experimentally observed by Dekel, Lee, and Linial that the high energy eigenvectors of such graphs have many nodal domains.
We prove superconstant (in fact, nearly linear in the number of vertices) lower bounds on the number of nodal domains of sparse random regular graphs, for sufficiently large Laplacian eigenvalues. The proof combines two different notions of eigenvector delocalization in random matrix theory as well as tools from graph limits and combinatorics. This is in contrast to what is known for dense Erdos-Renyi graphs, which have been shown to have only two nodal domains with high probability.
Joint work with Shirshendu Ganguly, Theo McKenzie, and Sidhanth Mohanty.
- Quantum Pseudoentanglement [Sep 22 2023 +]
Date: Sep 22, 2023 Time: 11:30 - 12:30 Venue: SIC201
Abstract: Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. Inspired by recent work of Gheorghiu and Hoban, we define the notion of "pseudoentanglement'', a property exhibited by ensembles of efficiently constructible quantum states which are indistinguishable from quantum states with maximal entanglement. Our construction relies on the notion of quantum pseudorandom states -- first defined by Ji, Liu and Song which are efficiently constructible states indistinguishable from (maximally entangled) Haar-random states. Specifically, we give a construction of pseudoentangled states with entanglement entropy arbitrarily close to logn across every cut, a tight bound providing an exponential separation between computational vs information theoretic quantum pseudorandomness. We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence.
- Efficient solution of the K-partitioning problem [Sep 08 2023 +]
Date: Sep 08, 2023 Time: 11:30 - 12:30 Venue: SIC201
Abstract: Motivated by an application in psychology, we consider the NP-hard K-clustering problem which consists in partitioning the nodes of a graph in exactly K-clusters. Four Mixed Integer Linear Formulations (MILP) of the problem are defined in order to solve it to optimality. Polyhedral results enable to theoretically compare these formulations and identify conditions under which various family of valid inequalities are facet-defining of their polytopes. An efficient branch-and-cut algorithm is obtained from these results that outperforms the direct resolution of all the formulations through the commercial solver CPLEX.
- Communication-aware scheduling of precedence-constrained jobs [Aug 09 2023 +]
Date: August 09, 2023 Time: 16:00 - 17:00 Venue: CC 109, 1st floor new CSE/CC building
Abstract: The problem of scheduling precedence-constrained jobs has a rich history, dating back to the classic list scheduling algorithm of Graham from the 1960s. The problem has applications in diverse scenarios and has been studied extensively in both the theory and systems communities. One such setting is where the underlying machines are heterogeneous and distributed, with communication among them incurring delays, which impact the completion times of the jobs. This setting arises in the scheduling of neural network training jobs over a network of GPUs, CPUs, and TPUs, where it has been referred to as the device placement problem.
A survey by Bansal in 2017 lists communication-aware scheduling of precedence-constrained jobs as one of the top ten open problems in scheduling theory. In this talk, we will present a framework for designing approximation algorithms for the problem, which addresses machine speeds, job sizes, and general models of machine and job delays. Our framework yields the first polylogarithmic-approximation algorithms for the problem.
The talk will be self-contained. We will motivate and present the problem, explore examples, review a simple combinatorial algorithm for a special case, present the linear programming framework with an overview of the results, and close with the many open problems remaining in the space.
(Based on a FOCS 2020 paper with Biswaroop Maiti, David Stalfa, Zoya Svitkina, and Aravindan Vijayaraghavan, and an ICALP 2023 paper with David Stalfa and Sheng Yang.)
- Hardness of Approximation for Metric Clustering [Aug 08 2023 +]
Date: August 08, 2023 Time: 11:00 - 12:00 Venue: CC 109, 1st floor new CSE/CC building
Abstract: A lot of attention has been invested over the last four decades by the theory community to understand the efficiency of (even approximately) computing optimal clusters. Despite this focus, our understanding of the approximability of these clustering tasks remains poor, and our understanding of the hardness of approximation of these tasks was even worse. In this talk, I survey the recently established conceptual framework to tackle the latter issue of hardness of approximation of clustering in L_p metrics (and in particular Euclidean metric), through which we are now able to significantly improve on the inapproximability bounds established more than twenty years ago.
- Inapproximability of Geometric Optimization Problem [Aug 07 2023 +]
Date: August 07, 2023 Time: 14:00 - 15:00 Venue: CC 109, 1st floor new CSE/CC building
Abstract: Many important optimization problems are not tractable. A typical way to cope with the intractability of optimization problems is to design algorithms that find solutions whose cost or value is close to the optimum. In several interesting cases, it is possible to prove that even finding good approximate solutions is as hard as finding optimal solutions. The area which studies such inapproximability results is called hardness of approximation. The celebrated PCP theorem lies at the heart of essentially all NP-hardness of approximation results and provides a framework (along with other ingredients such as the parallel repetition theorem and dictatorship tests) through which we can obtain most of the known inapproximability results for NP-hard problems. However, such an inapproximability framework, even equipped with the powerful Unique Games Conjecture, is currently insufficient to obtain optimal hardness of approximation results for important geometric optimization problems. In this talk, I will elaborate on some major results in the area of hardness of approximation and the challenges of the subarea of inapproximability of geometric optimization, which lies at the confluence of hardness of approximation and geometric optimization.
- Foundations of Lattice-based Cryptography [Apr 19 2023 +]
Date: April 19, 2023 Time: 15:00 - 16:00 Venue: CC 109, 1st floor new CSE/CC building
Abstract: Public key cryptography is essential for internet security, and 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's 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.
- Geometry of Secure Computation [Apr 14 2023 +]
Date: April 14, 2023 Time: 17:30 - 18:30 Venue: Online
Abstract: Reducing the overhead of security solutions increases their adoption. Motivated by such efficiency considerations, characterizing secure computation’s round and communication complexity is natural.
The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) determine these complexities for deterministic computations. Determining randomized-output functions’ round and communication complexity remained open for over three decades. This talk will present how we settled this long-standing open problem.
Our technical innovation is a geometric framework for this research — opening a wormhole connecting it to geometry research. This framework encodes all candidate secure protocols as points. Studying mathematical properties of novel generalizations of their convex hull implies round and communication complexity results.
- The Cut World from the Parameterized Complexity Lens [Apr 5 2023 +]
Date: April 5, 2023 Time: 16:30 - 17:30 Venue: CC 109, 1st floor new CSE/CC building
Abstract: Cut and separation problems arguably constitute a fundamental subclass of graph problems, that not only have received vast attention from the researchers, but also model a vast array of real-life scenarios ranging from transport network design to image segmentation. We focus on NP-hard cut problems and study them from the viewpoint of parameterized complexity.
We begin by presenting a recent powerful tool by Kim, Krastch, Pilipczuk, Wahlström [STOC 2022], called the directed flow augmentation, which led to fixed-parameter tractability results of several cut-based open problems.
We then show that one we can use the technique of flow augmentation together with a recently introduced notion of a new graph parameter called twinwidth by Bonnet, Giocanti, Ossona de Mendez, Simon, Thomassé, Toruńczyk [STOC 2022], to resolve the parameterized complexity of Directed Multicut with 3 terminal pairs [SODA 2023], which had been a long standing open question. With this work and another follow-up work of ours, we show further applications of flow augmentation, and give a complete picture of the classical parameterized complexity of arguably the most fundamental NP-hard cut problems.
We then briefly move on to MinCSP over Allen algebra, that for example, model problems from Natural Language Processing and comment how the tools of the cut-world from parameterized complexity can be used to track problems in this world.
This exploration leads to the problem of Symmetric Multicut in graphs that so far resists all the attacks using the current tools. We end by posing this as an open problem, whose study should generate/reveal more tools that help us grow our understanding of the cut world even further.
- Optimal FPT Approximations for Clustering with Outliers [Mar 17 2023 +]
Date: March 17, 2023 Time: 11:00 am - 12:00 noon Venue: CC 109, 1st floor new CSE/CC building
Abstract: Clustering is a widely used unsupervised learning technique that groups “similar” objects together. It has been shown that even a small number of outliers can influence the results of clustering algorithms, obscuring the natural underlying clusters. Thus, the study of clustering in the presence of outliers is vital for practical applications. In a “clustering with outliers” problem, we are given a set of points P and two parameters k and m, and the clustering should partition P into k clusters, excluding up to m outlier points.
In this talk, I will present a general framework to reduce a “clustering with outliers” problem to its outlier-free analogue, at the expense of a small loss in the approximation guarantee (our recent result [1], AAAI’23). This reduction allows us to obtain optimal FPT-approximation algorithms for a number of clustering problems, such as k-median/k-means with outliers.
[1] Clustering What Matters: Optimal Approximations for Clustering with Outliers. Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue. AAAI 2023 (Distinguished Paper) https://arxiv.org/abs/2212.00696
- Errors and Correction in Cumulative Knowledge [Mar 15 2023 +]
Date: March 15, 2023 Time: 2:15 pm - 3:15pm Venue: CC 109, 1st floor new CSE/CC building
Abstract: Societal accumulation of knowledge is a complex, and arguably error-prone, process. The correctness of new units of knowledge depends not only on the correctness of the new reasoning, but also on the correctness of old units that the new one builds on. Left unchecked errors could completely ruin the validity of most of this knowledge – so there must some error-correcting going on. What are the error-corrections processes and how effective are they? In this talk, we present a simple probabilistic process that aims to model such accumulation of knowledge and study the persistence (or lack thereof) of errors.
Our model for the generation of new units of knowledge is based on the preferential attachment growth model, to which we additionally allow for injection of errors. Furthermore, the process includes checks aimed at catching these errors. We investigate when effects of errors persist forever in the system (with positive probability) and when they get rooted out completely by the checking process.
The two basic parameters associated with the checking process are the {\em probability} of conducting a check and the {\em depth} of the check. We show that errors are rooted out if checks are sufficiently frequent and sufficiently deep. In contrast, shallow or infrequent checks are insufficient to root out errors.
Based on the paper: "Is This Correct? Let’s Check!" with Omri Ben-Eliezer, Dan Mikulincer and Elchanan Mossel (all at MIT).
- On the Approximability of Satisfiable CSPs, and Applications [March 2, 2023 +]
Date: March 2, 2023 Time: 10:30 am - 11:30 am Venue: CC109
Abstract: Constraint satisfaction problems (CSPs) are some of the most fundamental problems in computer science. An instance of a CSP consists of a set of variables and a set of local constraints on them. The goal is to assign values to the variables that satisfy many constraints. In this talk, I will discuss the complexity of approximately solving CSPs. While we completely understand this question assuming the Unique Games Conjecture, these results are not applicable to satisfiable CSPs -- in other words if the given CSP instance is fully satisfiable.
Motivated by this, we study the following analytical question. Suppose \mu is a distribution over \(\Sigma^k\). Let \(f_i: \Sigma^n \to [-1,1]\) be bounded functions, such that at least one of the functions \(f_i\) essentially has degree at least \(d\), meaning that the Fourier mass of \(f_i\) on terms of degree less than \(d\) is negligible. Then under what conditions we have the following expectation small.
\(\mathbb{E}_{(x_1, x_2, ..., x_k) \sim \mu^{\otimes n} } [f(x_1) f(x_2) \cdots f(x_k)].\)
I will discuss the case when \(k=3\), while for larger \(k\) this question is wide open. I will also discuss the applications of this result (for \(k=3\)) to a p-biased linearity testing and counting certain progressions in additive combinatorics.
Based on joint work with Subhash Khot and Dor Minzer.
- Radical Sylvester-Gallai theorem for cubics - and beyond [February 24, 2023 +]
Date: February 24, 2023 Time: 3:30 pm - 4:30 pm Venue: CC105
Abstract: In 1893, Sylvester asked a basic question in combinatorial geometry: given a finite set of distinct points \(v_1, \ldots, v_m \in \mathbb{R}^N\) such that the line defined by any pair of distinct points \(v_i, v_j\) contains a third point \(v_k\) in the set, must all points in the set be collinear?
Generalizations of Sylvester's problem, which are known as Sylvester-Gallai type problems, have found applications in algebraic complexity theory (in Polynomial Identity Testing---PIT) and coding theory (Locally Correctable Codes). The underlying theme in all these types of questions is the following:
Are Sylvester-Gallai type configurations always low-dimensional?
In 2014, Gupta, motivated by such applications in algebraic complexity theory, proposed wide-ranging non-linear generalizations of Sylvester's question, with applications on the PIT problem.
In this talk, we will discuss these non-linear generalizations of Sylvester's conjecture, their intrinsic relation to algebraic computation, and a recent theorem proving that radical Sylvester-Gallai configurations for cubic polynomials must have small dimension. And time permitting a little bit more.
Joint work with Akash Kumar Sengupta
- On Helly numbers of exponential lattices [February 03, 2023 +]
Date: February 03, 2023 Time: 5:00 pm - 6:00 pm Venue: Online
Abstract: For every set \(S \subseteq \mathbb{R}^2\), the Helly number of \(S\) is the smallest positive integer \(N\), if it exists, such that, for every finite family \(\mathcal{F}\) of convex sets in \(\mathbb{R}^2\) the following statement is true: if the intersection of any \(N\) or fewer members of \( \mathcal{F}\) contains at least one point of \(S\), then \(\bigcap \mathcal{F}\) contains at least one point of \(S\).
We prove that the Helly numbers of exponential lattices \(\{\alpha^n\colon n \in \mathbb{N}_0\}^2\) are finite for every \(\alpha>1\) and we determine their exact values in some instances, which in particular solves a problem posed by Dillon. We also fully characterize nondiagonal exponential lattices \(\{ \alpha^n \colon n \in \mathbb{N}_0\} \times \{\beta^n \colon n \in \mathbb{N}_0\}\) with \(\alpha, \beta>1\) with finite Helly numbers using results from number theory.
This is joint work with Gergely Ambrus, Nóra Frankl, Attila Jung, and Márton Naszódi.
- On Parameterized Analysis and the Disjoint Paths Problem [January 20, 2023 +]
Date: Janurary 20, 2023 Time: 5:00 pm - 6:00 pm Venue: Online
Abstract: Parameterized Analysis leads both to a deeper understanding of intractability results and to practical solutions for many NP-hard problems. Informally speaking, Parameterized Analysis is a mathematical paradigm to answer the following fundamental question: What makes an NP-hard problem hard? Specifically, how do different parameters (being formal quantifications of structure) of an NP-hard problem relate to its inherent difficulty? Can we exploit these relations algorithmically, and to what extent? Over the past three decades, Parameterized Analysis has grown to be a mature field of outstandingly broad scope with significant impact from both theoretical and practical perspectives on computation.
In this talk, I will first give a brief introduction to the field of Parameterized Analysis. Additionally, I will zoom in to a specific result, namely, the first single-exponential time parameterized algorithm for the Disjoint Paths problem on planar graphs. An efficient algorithm for the Disjoint Paths problem in general, and on "almost planar" graphs in particular, is a critical part in the quest for the establishment of an Efficient Graph Minors Theory. As the Graph Minors Theory is the origin of Parameterized Analysis and is ubiquitous in the design of parameterized algorithms, making this theory efficient is a holy grail in the field.
- Scaling limits of stochastic optimization algorithms over large graphs [January 20, 2023 +]
Date: Janurary 20, 2023 Time: 12:00 pm - 13:00 pm Venue: CC109
Abstract: Wasserstein gradient flows often arise from mean-field interactions among exchangeable particles. In many interesting applications however, the "particles" are edge weights in a graph whose vertex labels are exchangeable but not the edges themselves. Motivated by such graph optimization problems we investigate the question of optimization of functions over this different class of symmetries. Popular applications include training of large computational graphs like (Deep) Neural Networks. This body of work shows that discrete stochastic optimization algorithms over finite graphs have a well-defined analytical scaling limit as the size of the network grows to infinity. The limiting space is that of graphons, a notion introduced by Lovász and Szegedy to describe limits of dense graph sequences. The limiting curves are given by a novel notion of McKean-Vlasov equation on graphons and a corresponding notion of propagation of chaos holds. In the asymptotically zero-noise case, the limit is a gradient flow on the metric space of graphons. This is an attempt to generalize the Wasserstein calculus to higher-order exchangeable structures.
ArXiv links - [2111.09459]
- Polynomial Calculus with extension variables: Upper and Lower bounds [January 19, 2023 +]
Date: Janurary 19, 2023 Time: 10:00 am - 11:00 am Venue: online
Abstract: A major open problem in proof complexity is to prove superpolynomial lower bounds for AC0[p]-Frege proofs. This system is the analog of AC0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years ([Razborov87, Smolensky87]), there are no significant lower bounds for AC0[p]-Frege. Significant and extensive degree and size lower bounds have been obtained for a variety of subsystems of AC0[p]-Frege, including Nullstellensatz ([Beame et.al. 94]), Polynomial Calculus ([Clegg et. al. 96]), and SOS ([Grigoriev01]). However to date there has been no progress on AC0[p]-Frege lower bounds, highlighting the need to study systems stronger that those mentioned above, but possibly below AC0[p]-Frege.
In the first part of this talk, I will discuss one such system: constant-depth extensions of the Polynomial Calculus, introduced by [GrigorievHirsch03], where it was also shown that these systems can simulate AC0[p]-Frege at a proportional depth. Well known hard tautologies like the Pigeonhole principle and Tseitin Tautologies were shown to be easy for these systems at a low constant depth, which makes them a good candidate in the quest for stronger lower bounds. I will describe joint work with Russell Impagliazzo and Toniann Pitassi (which appeared in LICS20) where we show that these extensions are much more powerful than was previously known. Our main result is that small depth (≤ 43) Polynomial Calculus (over a sufficiently large field) can polynomially effectively simulate all of the well-studied semialgebraic proof systems: Cutting Planes, Sherali-Adams, Sum-of-Squares (SOS), and Positivstellensatz Calculus (Dynamic SOS). Additionally, they can also quasi-polynomially effectively simulate AC0[q]-Frege for any prime q independent of the characteristic of the underlying field. They can also effectively simulate TC0-Frege if the depth is allowed to grow proportionally. Thus, proving strong lower bounds for constant-depth extensions of Polynomial Calculus would not only give lower bounds for AC0[p]-Frege, but also for systems as strong as TC0-Frege.
In the second part of this talk, I will describe ongoing work with the same co-authors which deals with the flip side of proving new lower bounds for these systems. In response to an open problem we stated in our above work, Sokolov [Sok20] introduced new techniques to show lower bounds for Polynomial Calculus over {±1} variables, a necessary step to prove AC0[2]-Frege lower bounds. We extend his results to show for every prime p > 0 and every n > 0 the existence of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over F_p with a sub-quadratic number of extension variables, each depending on at most O(log n) original variables requires exponential size.
- Selection in the Presence of Biases [January 6, 2023 +]
Date: Janurary 6, 2023 Time: 11:30 am - 12:30 am Venue: CC109
Abstract: In selection processes such as hiring, promotion, and college admissions, biases toward socially-salient attributes of candidates are known to produce persistent inequality and reduce aggregate utility for the decision-maker. Interventions such as the Rooney Rule and its generalizations, which require the decision maker to select at least a specified number of individuals from each affected group, have been proposed to mitigate the adverse effects of such biases in selection.
In this talk, I will discuss recent works which have established that such lower-bound constraints can be effective in improving aggregate utility.
Papers: https://arxiv.org/abs/2001.08767 https://arxiv.org/abs/2010.10992 https://arxiv.org/abs/2202.01661
- Hypergraph expansion, CSPs, and Codes [January 3, 2023 +]
Date: Janurary 3, 2022 Time: 5:00 pm - 6:00pm Venue: CC109
Abstract: We will discuss some new notions of hypergraph expansion, which can be exploited by spectral algorithms, as well as ones based on semidefinite programming hierarchies. These properties lead to new structural characterizations and algorithmic regularity lemmas for hypergraphs, as well as new decoding algorithms for codes based on bias-reduction via direct-sum, such as the breakthrough construction of epsilon-balanced codes by Ta-Shma.
(Based on joint work with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, and Shashank Srivastava)
- Topological Data Analysis, Basics, Computation and Applications [December 7 2022 +]
Date: December 7, 2022 Time: 3:00 pm - 4:00pm Venue: Online
Abstract: In this talk, we will discuss the basic theory of Topological data analysis (TDA), in particular, Persistent Homology (PH). Then we will look into its computational aspects including the challenges and the recent advancements. We will also discuss our recent work (SoCG'22) with Marc Glisse.
- On the approximation hardness of geodetic set and its variants [November 30 2022 +]
Date: November 30, 2022 Time: 4:00 pm - 5:00pm Venue: Online
Abstract: Given a graph, a geodetic set (resp. edge geodetic set) is a subset of vertices such that every vertex (resp. edge) of the graph is on a shortest path between two vertices of the subset. A strong geodetic set is a subset S of vertices and a choice of a shortest path for every pair of vertices of S such that every vertex is on one of these shortest paths. The geodetic number (resp. edge geodetic number) of a graph is the minimum size of a geodetic set (resp. edge geodetic set) and the strong geodetic number is the minimum size of a strong geodetic set. We first prove that, given a subset of vertices, it is NP-hard to determine whether it is a strong geodesic set. Therefore, it seems natural to study the problem of maximizing the number of covered vertices by a choice of a shortest path for every pair of a provided subset of vertices. We provide a tight 2-approximation algorithm to solve this problem. Then, we show that there is no 781/780 polynomial-time approximation algorithm for edge geodetic number and strong geodetic number on subcubic bipartite graphs with arbitrarily high girth. We also prove that geodetic number and edge geodetic number are both LOG-APX-hard, even on subcubic bipartite graphs with arbitrarily high girth. Finally, we disprove a conjecture of Iršič and Konvalinka by proving that the strong geodetic number can be computed in polynomial time in complete multipartite graphs.
- On the border complexity of binomials (& more) [November 11 2022 +]
Date: November 11, 2022 Time: 2:00 pm - 3:00pm Venue: CC109
Abstract: In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this talk, we will prove the converse of Kumar’s result, which ramifies in a surprising new formulation of Waring rank and border Waring rank. We will also talk about the orbit closure of the product-plus-power polynomial, determine its stabilizer, and determine the properties of its boundary points. Then, we will show several exponential separations between related polynomials contained in the affine closure of product-plus-product polynomials (binomials).
From binomials, we will go the to k-monomial and determine its orbit closure. We will also discuss a strong exponential separation between the affine closure of two consecutive monomials, the k-monomial and the (k+1)-th. Depending on the time, I will go into the proofs of the latter results.
This talk is mostly based on the recent unpublished work with Fulvio Gesmundo (Saarland University), Christian Ikenmeyer ( University of Warwick), Gorav Jindal (Max Planck Institute for Software Systems, Saarbrücken), and Vladimir Lysikov (Centre for the Mathematics of Quantum Theory, University of Copenhagen).
- A brief introduction to program obfuscation [October 20 2022 +]
Date: October 20, 2022 Time: 4:00 pm - 5:00pm Venue: CC109
Abstract: Program obfuscation is a very major cryptographic primitive. While the notion was formally defined in a paper by Barak et al. in 2001, its most intuitve variant called VBB (Virtual Black-Box) obfuscation was shown to be impossible in that same paper. A weaker version called iO (indistinguishability Obfuscation) was not really considered initially by the community feeling that it would not be too relevant for achieving major cryptographic goals. In a work in 2007 by Goldwasser and Rothblum, it was shown that iO is the "best-possible" notion of obfuscation that one could hope to achieve. In the last decade, most of these doubts were put to bed when iO was shown to be an all-encompassing primitive, that could imply most other objects in the world of cryptography, in a series of works. In this talk, I will talk about the first two papers and briefly mention some of these results.
- Polynomial time partition oracles for bounded degree planar graphs [October 13 2022 +]
Date: October 13, 2022 Time: 5:30 pm - 6:30pm Venue: CC109
Abstract: Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small \epsilon > 0, one removes \epsilon dn edges to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle. A partition oracle is a local procedure that gives "consistent" access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. In this talk, I will describe a partition oracle that runs in time poly(d/\epsilon). I will also describe how this machinery strikes a fortune and helps in obtaining a tester for all planar properties which runs in time exp(d/epsilon^2). This is easily obtained by a better error analysis on the seminal result of Newman and Sohler [SICOMP 2013].
Based on Joint works with Sabyasachi Basu, C. Seshadhri and Andrew Stolman.
- Karchmer-Wigderson games for hazard-free computation [September 21 2022 +]
Date: September 21, 2022 Time: 3:30 pm - 4:30pm Venue: Online
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 Karchmer-Wigderson game that captures the complexity of hazard-free computations exactly. As an application, we will see exact bounds for computing the Multiplexer function by formulas in a hazard-free way.
This talk is based on a joint work with Christian Ikenmeyer and Balagopal Komarath.
- Testing equality of compressed strings in Randomised NC [September 2 2022 +]
Date: September 2, 2022 Time: 2:30 pm - 3:30pm Venue: CC105
Abstract: There has been extensive work on the problem of testing equality of compressed strings represented via straight-line programs. Efficient algorithms for the problem have been known since the work of Hirschfield et al., Plandowski, Melhorn et al. (1994), Jez (2012). There are also randomized algorithms known (Gasieniec et al., Schmidt-Schauß and Schnitger); however none of these algorithms are known to be parallelizable and it is open whether the question of testing compressed string equality is P-complete.
König and Lohrey showed that the problem admits a RNC algorithm by reduction to the polynomial identity testing problem. We present a different RNC algorithm for this problem that is arguably simpler. Our algorithm is based on the cyclotomic identity testing (CIT) problem: given a polynomial \(f(x_1,\ldots,x_k)\), decide whether \( f(\zeta_n^{e_1},\ldots,\zeta_n^{e_k})\) is zero, where \(\zeta_n = e^{2\pi i/n}\) is a primitive complex \(n\)-th root of unity and \(e_1,\ldots, e_k\) are integers, represented in binary.
- Power and limitation of border depth-3 algebraic circuits [August 16 2022 +]
Date: August 16, 2022 Time: 2:00 pm - 3:00pm Venue: Online
Abstract: Border complexity of polynomials plays an integral role in the GCT (Geometric complexity theory) approach to prove P != NP. GCT was proposed by Mulmuley and Sohoni in 2001 where the idea is to prove the P!=NP (and its algebraic versions) using algebraic geometry and representation theory. Even the restricted setting of algebraic circuits in the border is not well-understood. Surprisingly, (Kumar ToCT’20) proved the universality of the border of top-fanin 2 depth-3 circuits (Σ^[2]ΠΣ-bar), which is in contrast with its classical model.
In this talk, we will discuss some advancements in this area. We will discuss an upper bound result which states that the bounded top-fanin border depth-3 circuits (Σ^[k]ΠΣ-bar for constant k) can be computed by a polynomial-size algebraic branching program (ABP). We will also discuss a strong exponential separation between any two consecutive border classes, Σ^[k]ΠΣ-bar and Σ^[k+1]ΠΣ-bar, establishing an optimal hierarchy of constant top-fanin border depth-3 circuits.
This is based on two works -- (i) the upper bound result is a joint work with Prateek Dwivedi and Nitin Saxena, FOCS'21 and (ii) the lower bound result is a joint work with Nitin Saxena, FOCS'22.
- Ideals, Determinants, and Straightening [August 10 2022 +]
Date: August 10, 2022 Time: 7:30 pm - 8:30pm Venue: Online
Abstract: Polynomial ideals are key objects that appear behind the scenes of multiple problems in algebraic complexity, including polynomial factorization, polynomial identity testing, and the study of algebraic proof systems. From the viewpoint of complexity theory, ideals generated by a single polynomial are generally well-understood, but our knowledge of ideals with multiple generators is lacking. In this talk, I will describe some recent work that takes a first step towards understanding ideals with multiple generators, focusing on ideals generated by the r-by-r minors of an n-by-n matrix.
This talk is based on joint work with Michael A. Forbes.
- Why we couldn't prove SETH hardness of CVP for even norms! [July 27 2022 +]
Date: July 27, 2022 Time: 2:00 pm - 3:00pm Venue: CC109
Abstract: Lattice-based cryptographic schemes have generated much interest in recent years. Their security relies on the computational hardness of problems over geometric objects called lattices. These problems have been used to build advanced cryptographic primitives such as fully homomorphic encryption, and they are believed to be resistant to quantum attacks. Given the recent advancement in quantum technologies, many institutes such as the National Institute of Standards and Technology (NIST) and European Telecommunications Standards Institute (ETSI) have initiated a process for standardization and deployment of lattice-based schemes widely over the next few years. Recently, NIST has announced lattice-based candidates (Kyber and Dilithium) as the primary algorithms for implementation.
The security of the lattice-based cryptosystem schemes crucially relies on the assumption that the best-known algorithms for the corresponding lattice problems cannot be significantly improved. Understanding the fine-grained hardness of these problems is one way of getting more confidence in these assumptions.
In this talk, I will discuss the fine-grained hardness of the lattice problems in different p-norms. Mainly, I will focus on the recent joint work with Divesh Aggarwal. Under a complexity-theoretic assumption, we show that getting any SETH-hardness for the lattice problems in the even norm is impossible by a poly-time reduction from k-SAT to CVP. We also show similar impossibility results for SubSet-SUM and many other problems.
- Parallel Algorithms for Depth First Search in planar graphs [July 12 2022 +]
Date: July 12, 2022 Time: 2:30 pm - 3:30pm Venue: CC109
Abstract: The question of whether Depth First Search trees have an parallel algorithm of logarithmic running time (or in class NC) gained attention in 1980s. It was shown in [Reif85] that finding the lexicographically least DFS tree is P-complete for both directed and undirected graphs in general. However the problem of finding any depth first search tree (not necessarily lex-first), in both undirected and directed graphs was shown to be in RNC by [Aggarwal- Anderson87] and [Aggarwal-Anderson-Kao90] respectively, and the recent result on matching by [Fenner-Gurjar-Thierauf16] puts them in quasiNC. For planar graphs, deterministic NC algorithms are known in both directed and undirected settings. [Hagerup90] gave an O(log n) algorithm in undirected planar graphs and [Kao88], [Kao-Klein90] and [Kao95] gave deterministic parallel algorithms upto NC7 in directed planar graphs. We will talk about ideas in [Hagerup90] for DFS in undirected planar graphs, our work (joint work with Eric Allender, Samir Datta) in which we give an algorithm for DFS in planar directed graphs in AC1(UL int co-UL) (a class contained in AC2), and [Kao-Klein90] which with some tweaks give the same bound we achieve in our work.
- Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product [June 27 2022 +]
Date: June 27, 2022 Time: 2:00 pm - 3:00pm Venue: Online
Abstract: We establish an \(\epsilon\)-sensitive hierarchy separation for monotone arithmetic computations. The notion of \(\epsilon\)-sensitive monotone lower bounds was recently introduced by Hrubeš. We show the following.
- There exists a monotone polynomial over \(n\) variables in VNP that cannot be computed by \(2^{o(n)}\) size monotone circuits in an \(\epsilon\)-sensitive way as long as \(\epsilon \ge 2^{-\Omega(n)}\).
- There exists a polynomial over \(n\) variables that can be computed by polynomial size monotone circuits but cannot be computed by any monotone arithmetic branching program (ABP) of \(n^{o(\log n)}\) size, even in an \(\epsilon\)-sensitive fashion as long as \(\epsilon \ge n^{-\Omega(\log n)}\).
- There exists a polynomial over \(n\) variables that can be computed by polynomial size monotone ABP but cannot be computed in \(n^{o(\log n)}\) size by monotone formulas even in an \(\epsilon\)-sensitive way, when \(\epsilon \ge n^{-\Omega(\log n)}\).
- There exists a polynomial over \(n\) variables that can be computed by width-\(4\) polynomial size monotone arithmetic branching programs (ABPs) but cannot be computed in \(2^{o(n^{1/d})}\) size by monotone, unbounded fan-in formulas of product depth \(d\) even in an \(\epsilon\)-sensitive way, when \(\epsilon \ge 2^{-\Omega(n^{1/d})}\).
An interesting feature of our separations is that in each case the polynomial exhibited is obtained from a 'graph inner-product' polynomial by choosing an appropriate graph topology. The closely related graph inner-product Boolean function for expander graphs was invented by Hayes, also independently by Pitassi, in the context of 'best-partition' multiparty communication complexity.
This is based on a joint work with Arkadev Chattopadhyay (TIFR Mumbai), and Partha Mukhopadhyay (CMI Chennai).
- Vanishing spaces of random sets and Reed-Muller codes [June 3 2022 +]
Date: June 3, 2022 Time: 2:00 pm - 3:00pm Venue: CC 109, 1st floor new CSE/CC building
Abstract: We try to address the following question. Suppose you were to choose \(k\) random points from \(F_2^m\), what is the dimension of the space of m-variate degree at most r multilinear polynomials that vanish on these randomly chosen points? We know that each point "adds one constraint" so the dimension of this space is at least \(\binom{m}{\leq r} - k\). If \(k < 0.99 \binom{m}{\leq r}\), is the dimension exactly \(\binom{m}{\leq r} - k\), with high probability?
In this talk, we will show that the answer to the above question is Yes, when \(r < \gamma . m\) for a suitably small constant \(\gamma > 0\), and also see why the above natural question directly relates to Reed-Muller codes and its resilience under erasures.
This is joint work with Siddharth Bhandari, Prahladh Harsha and Srikanth Srinivasan.
- Radial projections in vector spaces over finite fields [May 18 2022 +]
Date: May 18, 2022 Time: 2:00 pm - 3:00pm Venue: CC 109, 1st floor new CSE/CC building
Abstract: Several recent papers by authors including Matilla, Orponen, Liu, Shmerikin, and Wang give upper bounds on the Hausdorff dimension of the set of points for which the radial projection of some set \(E\in \mathbb{R}^d\) is much smaller than expected. In recent work, joint with Thang Pham and Vu Thi Huong Thu, we prove analogs of several of these theorems for point sets in vector spaces over finite fields. In several cases, we are able to prove stronger bounds than the most natural analogs to the known theorems in the continuous case. I will discuss these results, and if time permits I'll mention a connection to the Erdos and Falconer problems on distinct distances.
- Improved Quantum Query Upper Bounds Based on Classical Decision Trees [May 04 2022 +]
Date: May 04, 2022 Time: 2:00 pm - 3:00pm Venue: CC 109, 1st floor new CSE/CC building
Abstract: In the first part of this talk we will discuss the notion of rank of decision trees, which is essentially the largest depth of a complete subtree embedded in the initial tree. We observe the equivalence of rank and "guessing complexity," a measure of decision trees used by Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] to give upper bounds on quantum query complexity of functions based on classical query algorithms for them.
In the second part of the talk we will first note that the best speed-up obtainable using the approach of Beigi and Taghavi is captured by a polynomial optimization program on assignments of real weights to edges of the underlying classical decision tree. We then give a recursive expression for the optimal solution to this program and bound the optimum from above in terms of natural measures of the decision tree.
Based on joint work with Arjan Cornelissen and Subhasree Patro.
- Sketching and Streaming Complexity of Constraint Satisfaction Problems [Apr 04 2022 +]
Date: April 04, 2022 Time: 2:30 pm - 3:30pm Venue: CC 109, 1st floor new CSE/CC building
Abstract: In this talk we will describe some of our recent work giving new upper and lower bounds on the approximability of constraint satisfaction problems (CSPs) in the streaming and sketching settings. (Streaming algorithms process the input with small space, while sketching algorithms are restricted streaming algorithms that have additional composability requirements.) When the sketching algorithms are constrained to sub-polynomial space in the input length we get a fine dichotomy: CSPs on n variables are either solvable in polylogarithmic space or require at least sqrt(n) space. Our positive results show the broad applicability of what we call “bias-based sketching algorithms”, and our negative results work by abstracting and significantly generalizing previous bounds for the Maximum Cut problem. We will also mention some partial extensions to streaming algorithms, linear space lower bounds, ordering CSPs. Based on joint work with Chi-Ning Chou, Sasha Golovnev and Santhoshini Velusamy.
- Heroes Zeros in computational complexity [Aug 05 2021 +]
Date: August 05, 2021 Time: 2:30 pm - 3:30 pm Venue: Google Meet
Abstract: Polynomials, which are finite combinations of additions and multiplications, have been extensively studied for millennia, owing to their simplicity and pervasiveness. One of the most successful approaches to understand them is through the study of their zeros. In this talk, we will see some of the connections between the study of zeros of polynomials and the fundamental problems in computational complexity theory, from the perspective of the speaker's research journey so far.
- Approximating Profile Maximum Likelihood Efficiently: New Bounds on the Bethe Permanent [Jan 08 2020 +]
Date: Jan 08, 2020 Time: 2:00 pm - 3:00 pm Venue: CC109, 1st Floor, New CSE Building
Abstract: Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single estimator that maximizes profile maximum likelihood (PML) is sample competitive for all symmetric properties. Further, they showed that even a 2^{n^{1-delta}}-approximate maximizer of the PML objective can serve as such a universal plug-in estimator. (Here n is the size of the sample). Unfortunately, no polynomial time computable PML estimator with such an approximation guarantee was known. We provide the first such estimator and show how to compute it in time nearly linear in n. The PML objective is related to the permanent of a certain Vandermonde matrix. A surprising connection between the convex relaxation we introduce and the Bethe free energy approximation originating in statistical physics leads to new bounds on the Bethe permanent of non-negative matrices. This is in joint work with Moses Charikar and Aaron Sidford
- Junta Correlation is Testable [Jan 08 2020 +]
Date: Jan 08, 2020 Time: 11:00 am - 12:00 pm Venue: CC109, 1st Floor, New CSE Building
Abstract: A Boolean function f on the n-dimensional hypercube is said to be a k-junta if it is dependent only on some k coordinates of the input. These functions have been widely studied in the context of PCPs, learning theory and property testing. In particular, a flagship result in property testing is that k-juntas can be tested with \tilde{O}(k) queries -- i.e., there is an algorithm which when given a black box to f, makes only \tilde{O}(k) queries and decides between the following two cases: 1. f is a k-junta. 2. f is at least 0.01 far from every k-junta g in Hamming distance. Surprisingly, the query complexity is completely independent of the ambient dimension n. In this work, we achieve the same qualitative guarantee for the noise tolerant version of this problem. In particular, we give a 2^k query algorithm to distinguish between the following two cases. 1. f is 0.48-close to some k-junta. 2. f is at least 0.49 far from every k-junta. The algorithm and its proof of correctness are simple and modular employing some classical tools like “random restrictions” with elementary properties of the noise operator on the cube. Joint work with Elchanan Mossel and Joe Neeman.
- Overview of Quantum Algorithms and Complexity [Jan 02 2020 +]
Date: Jan 02, 2020 Time: 2:15 pm - 3:15 pm Venue: CC109, 1st Floor, New CSE Building
Abstract: In this informal talk, I\'ll give a brief overview of quantum computing and its intersection with theoretical computer science. I\'m happy to talk in more depth about whatever the audience is interested in. Please come with your questions about quantum computing (about the future of quantum computing, its impact on society, recent breakthroughs, research themes, the job market, or whatever you want to know more about).
- Can we learn algorithms? [Dec 30 2019 +]
Date: Dec 30, 2019 Time: 10:30 am - 11:30 am Venue: CC109, 1st Floor, New CSE Building
Abstract: Deep Learning has been applied successfully to many basic human tasks such as object recognition and speech recognition, and increasingly to the more complex task of language understanding. In addition, deep learning has been extremely successful in the context of planning tasks in constrained environments (e.g., game playing). We ask: Can deep learning be applied to design algorithms? We formulate this question precisely, and show how to apply deep reinforcement learning to design, from scratch, online algorithms for a number of classic optimization problems such as the AdWords problem (choosing which advertisers to include in a keyword auction), the online knapsack problem, and optimal stopping problems. Our results indicate that the models have learned behaviours that are consistent with the traditional optimal algorithms for these problems. Based on joint work with William Kong, Chris Liaw, and D. Sivakumar (ICLR 2019), and with D. Sivakumar, Di Wang, and Goran Zuzic (ongoing work).
- Non-malleable Encodings [Oct 24 2019 +]
Date: Oct 24, 2019 Time: 11:00 am - 12:00 pm Venue: CC109, 1st Floor, New CSE Building
Abstract: Non-malleable Encodings provide the following protection against tampering: a decoded message is either the same or completely independent of the underlying message. They have many applications to cryptography with connections to pseudo-random objects such as extractors, expanders and so on. In this talk, I will survey some of our recent results in this area.
- Two new results about quantum exact learning [Sep 26 2019 +]
Date: Sep 26, 2019 Time: 2:00 pm - 3:00 pm Venue: CC109, 1st Floor, New CSE Building
Abstract: We present two new results about exact learning by quantum computers. First, we show how to exactly learn a \(k\)-Fourier-sparse \(n\)-bit Boolean function from \(O(k^{1.5}(\log k)^2)\) uniform quantum examples for that function. This improves over the bound of \(\widetilde{\Theta}(kn)\) uniformly random \emph{classical} examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang's lemma for the special case of sparse functions. Second, we show that if a concept class \(\Cc\) can be exactly learned using \(Q\) quantum membership queries, then it can also be learned using \(O\left(\frac{Q^2}{\log Q}\log|\Cc|\right)\) \emph{classical} membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a \(\log Q\)-factor.
- Low variate polynomials: hitting-sets and bootstrapping [Aug 12 2019 +]
Date: Aug 12, 2019 Time: 10:35 am - 11:30 am Venue: CC109, 1st Floor, New CSE Building
One central concept in complexity theory is Derandomization. Polynomial Identity Testing (PIT) problem is a good test case for that purpose. PIT problem asks to decide whether a given arithmetic circuit computes a zero polynomial. It has a polynomial time randomized algorithm. However, designing a *deterministic* polynomial time algorithm for PIT is a long-standing open question in complexity theory. In our work, we study PIT problem in the blackbox setting, where we are not allowed to see the internal structure of the circuit and only evaluation at points is allowed. Designing blackbox PIT algorithm is equivalent to finding a set of points, called hitting set, such that for every non-zero circuit the set contains a point where it evaluates a non-zero value. In a joint work with Manindra Agrawal and Nitin Saxena, we study the phenomenon of bootstrapping in PIT: converting a hitting set of size-s degree-s n(s)-variate circuits to hitting set of a size s degree s s-variate circuits, where n(s) < < s. We study the bootstrapping phenomenon in the following cases:
Perfect Bootstrapping: when n(s)=log ^{\circ c} s, for example log^{\circ 2} s=loglog s.
Constant Bootstrapping: when n(s)=constant.
Shallow Bootstrapping: when n(s)=constant with depth-4 circuits.
Our previous work inspires us to study PIT for circuits with few variables, eg. logarithmic in the size s. In a joint work with Michael Forbes and Nitin Saxena, we give a poly(s)-time blackbox identity test for n=O(log s)-variate size s circuits that have poly(s) dimensional partial derivative space; eg. depth-3 diagonal circuits, which compute sum of power of linear polynomials. The former model is well-studied but no poly(s2^n)-time identity test was known before us.
- Derandomization from Algebraic Hardness: Treading the borders [July 01 2019 +]
Date: July 01, 2019 Time: 2:15 pm - 3:15 pm Venue: CC109, 1st Floor, New CSE Building
Abstract: A common phenomenon in complexity theory is that "hardness" and "derandomization" have very close connections between each other. Often, the existence of one implies the other. In algebraic complexity, this phenomenon manifests itself via construction of "pseudorandom/hitting set generators" given a "hard function". [Kabanets and Impagliazzo] gave such a construction using "combinatorial designs", and more result results have shown that this construction can also be `bootstrapped'. In these results, the "harder" the function is, the better the derandomization is. However, from these results, no matter how hard the function is, they do not yield a complete derandomization. In this work, we primarily address the following question: Q: Is there any algebraic hardness assumption that yields a generator achieving complete derandomization? We answer this question in the affirmative by constructing a suitable generator from a suitably hard polynomial. With some additional help from the "border", we also obtain application to improve the recent `bootstrapping' results. This is joint work with Zeyu Guo, Mrinal Kumar and Noam Solomon.
- Unique Games with Value Half and its Applications [Apr 01 2019 +]
Date: Apr 01, 2019 Time: 10:35 am - 11:35 am Venue: CC109, 1st Floor, New CSE Building
Abstract: PCP Theorem characterizes the class NP and gives hardness of approximation for many optimization problems. Despite this, several tight hardness of approximation results remain elusive via the PCP theorem. In 2002, Khot proposed the Unique Games Conjecture. Since the formulation of the conjecture, it has found interesting connections to the tight hardness of approximation results for many optimization problems. In this talk, I will discuss recent developments on the Unique Games Conjecture. The 2-to-2 Games Theorem implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least 1/2 fraction of the constraints vs. no assignment satisfying more than \eps fraction of the constraints, for every constant \eps>0. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee on the Unique Games instance and use this guarantee to convert the known Unique Games-hardness results to NP-hardness for several opt imization problems.
- Conditional Disclosure of Secrets: Lower Bounds and Perspectives [Mar 22 2019 +]
Date: March 22, 2019 Time: 11:00 pm - 12:00 pm Venue: CC109, 1st Floor, New CSE Building
Conditional Disclosure of Secrets (CDS), introduced by Gertner et al in 2000, is a minimal model of secure multi-party computation. Alice and Bob, who hold n-bit inputs x and y respectively, wish to release a common secret z to Carol (who knows both x and y) if and only if the input (x, y) satisfies some predefined predicate f . Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security.
CDS protocols have applications to numerous cryptographic tasks, such as Private Information Retrieval and constructing Attribute-Based Encryption schemes, and are behind recent breakthrough constructions of secret sharing schemes with sub-exponential-sized shares for general access structures.
In this talk, I will present what we have learnt so far about the complexity of CDS protocols, focusing on lower bounds and connections to communication complexity and the study of statistical zero-knowledge proofs.
Based on joint work with Benny Applebaum, Barak Arkis, and Pavel Raykov.
- Algebraic independence testing, approximate polynomials satisfiability, and the GCT chasm [Mar 06 2019 +]
Date: March 06, 2019 Time: 4:00 pm - 5:00 pm Venue: CC109, 1st Floor, New CSE Building
Algebraic independence testing of polynomials over a field F is a basic problem with several applications in theoretical computer science. When char(F) = 0, this problem has an efficient randomized algorithm thanks to the classical Jacobian criterion. Over finite fields, however, no general subexponential-time algorithm is known due to the failure of the Jacobian criterion in positive characteristic. In this talk, I will show that algebraic independence testing over finite fields are in the intersection of AM and coAM. In particular, it is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, e.g. graph isomorphism & integer factoring. Our proof is based on a novel "point counting" approach that avoids the use of the Jacobian criterion.
Next, I will talk about another problem called approximate polynomials satisfiability, which asks if a given system of polynomial equations has an approximate solution over an algebraically closed field. I will show that this problem can be solved in PSPACE using properties of projective spaces. As an unexpected application to approximative complexity theory, we prove that hitting-sets for the class "border VP" can be designed in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017), greatly mitigating the GCT Chasm (exponentially in terms of space complexity).
This is joint work with Nitin Saxena and Amit Sinhababu.
- Two Unsolved Problems: Birkhoff-von Neumann Graphs and PM-compact Graphs [Jan 30 2019 +]
Date: January 30, 2019 Time: 2:30 pm - 3:30 pm Venue: SIC 201, 2nd Floor, KReSIT Building
A geometric object of great interest in combinatorial optimization is the perfect matching polytope of a graph \(G\). In any investigation concerning the perfect matching polytope, one may assume that \(G\) is matching covered --- that is, it is a connected graph (of order at least two) and each edge lies in some perfect matching.
A graph \(G\) is Birkhoff-von Neumann if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that \(G\) is Birkhoff-von Neumann if and only if \(G\) does not contain a pair of vertex-disjoint odd cycles \((C_1,C_2)\) such that \(G-V(C_1)-V(C_2)\) has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP. The problem is in P if the input graph is planar --- due to a result of Carvalho, Lucchesi and Murty (2004). More recently, in a joint work with these three authors, we have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is \(\overline{C_6}\)-free.
The combinatorial diameter of a polytope is the diameter of its \(1\)-skeleton graph. A graph \(G\) is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. A result of Chvátal (1975) implies that \(G\) is PM-compact if and only if \(G\) does not contain a pair of vertex-disjoint even cycles \((C_1,C_2)\) such that \(G-V(C_1)-V(C_2)\) has a perfect matching. Once again the corresponding decision problem is in co-NP, but it is not known to be in NP. The problem is in P if the input graph is bipartite or is near-bipartite --- due to a result of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little (2013).
Recently, in a joint work with Marcelo H. de Carvalho, Xiumei Wang and Yixun Lin, we considered the "intersection" of the aforementioned problems. We give a complete characterization of matching covered graphs that are Birkhoff-von Neumann as well as PM-compact. (Thus the corresponding decision problem is in P.)
- Some Closure Results for Polynomial Factorization and Applications [Jan 09 2019 +]
Date: January 9, 2019 Time: 11:00 am - 12:00 noon Venue: CC 109, New CSE Building
In a sequence of seminal results in the 80's, Kaltofen showed that if an n-variate polynomial of degree poly(n) can be computed by an arithmetic circuit of size poly(n), then each of its factors can also be computed an arithmetic circuit of size poly(n). In other words, the complexity class VP (the algebraic analog of P) of polynomials, is closed under taking factors.
A fundamental question in this line of research, which has largely remained open is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, constant depth arithmetic circuits or the complexity class VNP (the algebraic analog of NP) of polynomials, are closed under taking factors. In addition to being fundamental questions on their own, such 'closure results' for polynomial factorization play a crucial role in the understanding of hardness randomness tradeoffs for algebraic computation.
I will talk about the following two results, whose study was motivated by these questions.
- The class VNP is closed under taking factors. This proves a conjecture of B{\"u}rgisser.
- All factors of degree at most poly(log n) of polynomials with constant depth circuits of size poly(n) have constant (a slightly larger constant) depth arithmetic circuits of size poly(n). This partially answers a question of Shpilka and Yehudayoff and has applications to hardness-randomness tradeoffs for constant depth arithmetic circuits.
Based on joint work with Chi-Ning Chou and Noam Solomon.
- Enabling Secure Computation with Minimal Interaction [Nov 26 2018 +]
Date: November 26, 2018 Time: 11:00 am - 12:00 noon Venue: CC 109, New CSE Building
Cryptography, originally the art of facilitating secret communication, has now evolved to enable a variety of secure tasks. Some fundamental challenges that modern cryptography addresses are: Can we prevent adversaries from tampering with encrypted communication? Can we verify that computation is performed correctly while preserving the privacy of data on which computation occurs? Can we enable mutually distrusting participants to jointly compute on distributed private data?
In this talk, I will discuss new research that builds minimally-interactive secure protocols to accomplish these tasks, based on widely believed cryptographic hardness assumptions. I will also present new techniques that overcome known barriers and enable new kinds of secure protocols. These techniques have made it possible to achieve non-malleability, strong variants of zero-knowledge, and other security properties while requiring only a single message from each participant.
This is based on joint works with Abhishek Jain, Yael Kalai, Ron Rothblum and Amit Sahai.
- Algorithms from Physics [Oct 25 2018 +]
Date: October 25, 2018 Time: 11:30 am - 12:30 pm Venue: CC 109, New CSE Building
In understanding physical systems over hundreds of years, Physicists have developed a wealth of dynamics and viewpoints. Some of these methods, when abstracted appropriately, could lead to new algorithmic techniques with applications to machine learning and TCS. I will present a couple of recent examples from my own research on such interactions between Physics and Algorithms – a Hamiltonian Dynamics inspired algorithm for sampling from continuous distributions and a Boltzmann's equation based algorithm for estimating the partition function for discrete distributions.
- Fairness and Diversity in Online Social Systems [Oct 25 2018 +]
Date: October 25, 2018 Time: 10:30 am - 11:30 am Venue: CC 109, New CSE Building
Social systems are now fueled by algorithms that facilitate and control connections and information. Simultaneously, computational systems are now fueled by people - their interactions, data, and behavior. Consequently, there is a pressing need to design new algorithms that are socially responsible in how they learn, and socially optimal in the manner in which they use information. Recently, we have made initial progress in addressing such problems at this interface of social and computational systems. In this talk, we will first understand the emergence of bias in data and algorithmic decision making and present first steps towards developing a systematic framework to control biases in classical problems such as data summarization and personalization. This work leads to new algorithms that have the ability to alleviate bias and increase diversity while often simultaneously maintaining their theoretical or empirical performance with respect to the original metrics.
- A Short List of Equalities Induces Large Sign Rank [Sept 18 2018 +]
Date: September 18, 2018 Time: 2:00 pm - 4:00 pm Venue: CC 105, New CSE Building
We exibit a natural function \(F_n\) on \(n\) variables, computable by a linear sized decision list of "Equalities", but whose sign rank is \(\exp(\Omega(n^{1/4}))\). The simplicity of \(F_n\) yields the following two consequences.
1) \(F_n\) can be computed by linear sized depth-2 threshold formulas when the weights of the threshold gates are unrestricted (THR o THR), but any THR o MAJ circuit computing it requires size \(\exp(\Omega(n^{1/4}))\). This provides the first exponential separation between the boolean circuit complexity classes THR o MAJ and THR o THR, answering a question of Amano and Maruoka [MFCS'05] and Hansen and Podolskii [CCC'10]. In contrast, Goldmann, Hastad and Razborov [Computational Complexity'92] had shown more than 25 years ago that functions efficiently computable by MAJ o THR circuits can also be efficiently computed by MAJ o MAJ circuits. Thus, while weights at the bottom layer do not matter when the top is light, we discover that they do when the top is heavy.
2) The function \(F_n\) lies in the communication complexity class PMA under the natural partition of the inputs. Since \(F_n\) has large sign rank, this implies PMA is not a subset of UPP, strongly resolving a conjecture of Goos, Pitassi and Watson [ICALP'16].
In order to prove our main result, we view \(F_n\) as an XOR function, and develop a technique to lower bound the sign rank of such functions. This requires novel arguments that allow us to conclude that polynomials of low Fourier weight cannot approximate certain functions, even if they are allowed unrestricted degree.
Based on joint work with Arkadev Chattopadhyay (TIFR), to appear in FOCS 2018.
- Bootstrapping Identity Tests for Algebraic Circuits [Aug 1 2018 +]
Date: August 1, 2018 Time: 2:00 pm - 3:00 pm Venue: CC 109, New CSE Building
The classical Ore-DeMillo-Lipton-Schwartz-Zippel lemma [O22,DL78,Z79,S80] states that any nonzero polynomial of degree at most \(s\) over \(n\) variables will evaluate to a nonzero value at some point on a grid \(S^n\) with \(|S| > s\). This leads to a deterministic polynomial identity test (PIT) for all degree-\(s\) size-\(s\) algebraic circuits over \(n\) variables that runs in time \(poly(s) \cdot (s+1)^n\).
Agrawal, Ghosh and Saxena recently introduced the technique of bootstrapping that can be used to asymptotically improve the running time of blackbox identity tests. They showed that a running time of as bad as \((s+1)^{n^{0.5 - \delta}} H(n)\) for any \(\delta > 0\) and arbitrary \(H\) can be improved to a running time of \(s^{\exp \circ \exp(\log^{\ast} s)}\), which is slightly super-polynomial. Building on their work we show that the hypothesis can be weakened further to a running time of \((s+1)^{o(n)} H(n)\) (slightly better than the trivial \(s^{O(n)}\)) to get essentially the same conclusion.
This is a joint work with Mrinal Kumar (Harvard, Cambridge, MA) and Ramprasad Saptharishi (TIFR, Mumbai).
- A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas [Jul 4 2018 +]
Date: July 4, 2018 Time: 12:05 pm - 1:00 pm Venue: CC 109, New CSE Building
Arithmetic formulas are directed trees where the leaves are labelled by variables and elements of the field, and internal vertices are labelled by + or x. Every internal vertex computes a polynomial by operating on its inputs. It is easy to see that they are a natural model of computation of polynomials, syntactically (symbolically). The size of the arithmetic formulas refers to the number of + and x operations needed to compute the polynomial.
It is an important question in the study of algebraic computational complexity to understand the amount of computational resources (refers to size of the formulas in this case) needed to compute a given polynomial.
In this talk, we will restrict ourselves to arithmetic formulas where computation at every vertex is a multilinear polynomial and in this scenario we show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. The multilinear restriction is a reasonable one since most polynomials of interest are indeed multilinear, Determinant, Permanent, Iterated Matrix Multiplication, Elementary Symmetric Polynomial. etc.
Formally, we will show that for any \(s = \mathrm{poly}(n)\) and \(\delta > 0\), we show that there are explicit polynomial families that have multilinear formulas of size at most s but no ‘small’-depth multilinear formulas of size less than \(s^{0.5 - \delta}\).
Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using \(\epsilon\)-biased spaces.
(Joint work with Nutan Limaye and Srikanth Srinivasan)
- Lower Bound Techniques for QBF Proof Systems [Apr 17 2018 +]
Date: April 17, 2018 Time: 11:30 am - 12:30 pm Venue: CC 109, New CSE Building
How do we prove that a false QBF is indeed false? How big a proof is needed? The special case when all quantifiers are existential is the well-studied setting of propositional proof complexity. Expectedly, universal quantifiers change the game significantly. Several proof systems have been designed in the last couple of decades to handle QBFs. Lower bound paradigms from propositional proof complexity cannot always be extended - in most cases feasible interpolation and consequent transfer of circuit lower bounds works, but obtaining lower bounds on size by providing lower bounds on width fails dramatically. A new paradigm with no analogue in the propositional world has emerged in the form of strategy extraction, allowing for transfer of circuit lower bounds, as well as obtaining independent genuine QBF lower bounds based on a semantic cost measure.
This talk will provide a broad overview of some of these developments.
- Finding Euler Tours in One Pass in the W-Streaming Model with O(n log n) Memory [Mar 13 2018 +]
Date: March 13, 2018 Time: 11:30 am - 12:30 pm Venue: CC 101, New CSE Building
We study the problem of finding an Euler tour in an undirected graph G in the W-Streaming model with O(n polylog(n)) RAM, where n, m are the number of nodes, edges of G. Our main result is the first one pass W-Streaming algorithm computing an Euler tour of G in the form of an edge successor function with only O(n log(n)) RAM which is optimal for this setting (e.g., Sun and Woodruff (2015)). The previously best-known result in this model is implicitly given by Demetrescu et al. (2010) with the parallel algorithm of Atallah and Vishkin (1984) using O(m/n) passes under the same RAM limitation. For graphs with omega(n) edges this is non-constant.
Our overall approach is to partition the edges into edge-disjoint cycles and to merge the cycles until a single Euler tour is achieved. Note that in the W-Streaming model such a merging is far from being obvious as the limited RAM allows the processing of only a constant number of cycles at once. This enforces us to merge cycles that partially are no longer present in RAM. Furthermore, the successor of an edge cannot be changed after the edge has left RAM. So, we steadily have to output edges and their designated successors, not knowing the appearance of edges and cycles yet to come. We solve this problem with a special edge swapping technique, for which two certain edges per node are sufficient to merge tours without having all of their edges in RAM. Mathematically, this is controlled by structural results on the space of certain equivalence classes corresponding to cycles and the characterization of associated successor functions. For example, we give conditions under which the swapping of edge successors leads to a merging of equivalence classes. The mathematical methods of our analysis are new and might be of independent interest for other routing problems in streaming models.
(Joint work with Christian Glazik, Jan Schiemann.)
- Homomorphic Secret Sharing [Feb 27 2018 +]
Date: February 27, 2018 Time: 2:00 pm to 3:00 pm Venue: CC 109, New CSE Building
A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports a compact local evaluation of functions of the shared secret. For the purpose of applications of HSS, it is useful to make the stronger requirement that the output can be reconstructed via addition. That is, if a secret \(s\) is split into shares \(s_1,\ldots,s_m,\) then \(f(s)\) can be written as \(F(s_1)+\ldots+F(s_m)\) for some efficiently computable \(F\), where addition is over a finite abelian group.
The talk will survey the state of the art on HSS and its applications, focusing mainly on: (1) computationally secure 2-out-of-2 HSS schemes for simple function classes using any one-way function, and (2) similar HSS schemes for branching programs from assumptions related to the hardness of discrete logarithms. These can provide alternatives to fully homomorphic encryption in the context of minimizing the communication complexity and round complexity of secure computation.
The talk is based mostly on joint works with Elette Boyle and Niv Gilboa.
- On Expressing Majority as a Majority of Majorities [Jan 25 2018 +]
Date: January 25, 2018 Time: 10:30 am to 11:30 am Venue: CC 109, New CSE Building
If \(k < n\), can one express the majority of \(n\) bits as the majority of at most \(k\) majorities, each of at most \(k\) bits? We prove that such an expression is possible only if \(k=\Omega(n^{4/5})\). This improves on a bound proved by Kulikov and Podolskii, who showed that \(k=\Omega(n^{0.7-\delta})\). Our proof is based on ideas originating in discrepancy theory, as well as a strong concentration bound for sums of independent Bernoulli random variables and a strong anticoncentration bound for the hypergeometric distribution.
- The Chasm at Depth Four, and Tensor Rank : Old results, new insights [Oct 25 2017 +]
Date: October 25, 2017 Time: 11:00 am to 12:00 pm Venue: Conference room, 1st Floor, CSE Kanwal Rekhi Bldg
Proving "good" lower bounds on the size of the arithmetic formulas computing an explicit polynomial is one of the central themes in the study of algebraic complexity. But the best known lower bound on the size of an arithmetic formula computing an explicit polynomial is quadratic in the number of variables, due to Kalorkoti [SIAM J. Comp. 1985]. There hasn’t been any progress on that front in the last 32 years.
But in a surprising result, Raz [J. ACM 2013] showed that for any n and d where d is sub-logarithmic in n, constructing explicit tensors of high enough rank would imply superpolynomial lower bounds for general arithmetic formulas. We first give a new and arguably simpler proof of this connection. We do this by showing a structured depth reduction to depth four for arithmetic formulas. This is a simpler proof of the depth reduction results of Agrawal and Vinay [FOCS 2008], Koiran [TCS 2012], and Tavenas [MFCS 2013]. We also extend the result of Raz to homogeneous formulas. In this setting, wee show that such a connection holds for any d that is sub-polynomial in n. As a corollary of our extension, we show that for any n and d where d is O(log n) (as opposed to the almost-logarithmic in n as in Raz’s result), constructing explicit tensors of high enough rank would imply superpolynomial lower bounds for general arithmetic formulas.
Joint work with Mrinal Kumar, Ramprasad Saptharishi and V. Vinay Available at https://eccc.weizmann.ac.il/report/2016/096/.- An approach to Distributed Synthesis [Oct 18 2017 +]
Date: October 18, 2017 Time: 11:00 am to 12:00 pm Venue: Conference room, 1st Floor, CSE Kanwal Rekhi Bldg
The Distributed Synthesis Problem(DSP) refers to the question of algorithmically synthesizing distributed systems from specifications. We consider some specification classes known to have a decidable DSP and show that these decidability results can be explained alternatively, in terms of the "bounded-model property" of a particular class of structures. Using this approach, we are able to show that DSP is decidable on a larger class of specifications than known previously.
- A finitary analogue of the downward Lowenheim-Skolem property [Sep 20 2017 +]
Date: September 20, 2017 Time: 11:00 am to 12:00 pm Venue: Room 105, New CSE Building
We present a model-theoretic property of finite structures, that can be seen as a finitary analogue of the well-studied downward Lowenheim-Skolem property from classical model theory. We call this property the *equivalent bounded substructure property*, denoted EBSP. Intuitively, EBSP states that a large finite structure contains a small "logically similar" substructure, where logical similarity means indistinguishability with respect to sentences of FO/MSO having a given quantifier nesting depth. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include regular languages of words, trees (unordered, ordered, ranked or partially ranked) and nested words, and various classes of graphs, such as cographs, graph classes of bounded tree-depth, those of bounded shrub-depth and m-partite cographs. Further, EBSP remains preserved in the classes generated from the above using various well-studied operations, such as complementation, transpose, the line-graph operation, disjoint union, join, and various products including the Cartesian and tensor products. Furthermore, by considering relations other than "substructure" in the EBSP definition, many more computationally interesting classes turn out to satisfy (the corresponding variant of) EBSP: these include graph classes of bounded tree-width, those of bounded clique-width, and those of bounded rank-width.
All of the aforementioned classes admit natural tree representations for their structures. We use this fact to show that the small and logically similar substructure of a large structure in any of these classes, can be computed in time linear in the size of the tree representation of the structure, giving linear time fixed parameter tractable (f.p.t.) algorithms for checking FO/MSO definable properties of the large structure (algorithmic meta-theorems). We conclude by presenting a strengthening of EBSP, that asserts "logical self-similarity at all scales" for a suitable notion of scale. We call this the *logical fractal* property and show that most of the classes mentioned above are indeed, logical fractals.
- Approximating Geometric Knapsack via L-packings [Aug 23 2017 +]
Date: August 23, 2017 Time: 11:30 am to 12:30 pm Venue: Conference room, KReSIT, first floor
We study the two-dimensional geometric knapsack problem (2DK), a geometric variant of the classical knapsack problem. In this problem we are given a set of axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack without rotating items. This is a very well-studied optimization problem and finds applications in scheduling, memory allocation, advertisement placement etc. The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is \(2+\epsilon\) [Jansen and Zhang, SODA 2004].
After more than a decade, in this paper we break the \(2\)-approximation barrier, achieving a polynomial-time \(17/9+\epsilon\) (which is less than \(1.89\)) approximation, which improves to \(558/325+\epsilon\) (i.e \(1.72\)) in the cardinality case.
We also consider the variant of the problem with rotations (2DKR) , where the items can be rotated by 90 degrees. Also in this case the best-known polynomial-time approximation factor (even for the cardinality case) is \(2+\epsilon\) [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time \(3/2+\epsilon\)-approximation for 2DKR, which improves to \(4/3+\epsilon\) in the cardinality case.
This is a joint work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala and Andreas Wiese. This result will appear in FOCS 2017.- General Strong-Polarization [Aug 11 2017 +]
Date: August 11, 2017 Time: 11:30 am to 12:30 pm Venue: 105, New CC, first floor
A martingale is a sequence of random variables that maintain their future expected value conditioned on the past. A \([0,1]\)-bounded martingale is said to polarize if it converges in the limit to either \(0\) or \(1\) with probability \(1\). A martingale is said to polarize strongly, if in \(t\) steps it is sub-exponentially close to its limit with all but exponentially small probability. In 2008, Arikan built a powerful class of error-correcting codes called Polar codes. The essence of his theory associates a martingale with every invertible square matrix over a field (and a channel) and showed that polarization of the martingale leads to a construction of codes that converge to Shannon capacity. In 2013, Guruswami and Xia, and independently Hassani et al. showed that strong polarization of the Arikan martingale leads to codes that converge to Shannon capacity at finite block lengths, specifically at lengths that are inverse polynomial in the gap to capacity, thereby resolving a major mathematical challenge associated with the attainment of Shannon capacity.
We show that a simple necessary condition for an invertible matrix to polarize over any non-trivial channel is also sufficient for strong polarization over all symmetric channels over all prime fields. Previously the only matrix which was known to polarize strongly was the \(2\times 2\) Hadamard matrix. In addition to the generality of our result, it also leads to arguably simpler proofs. The essence of our proof is a ``local definition'' of polarization which only restricts the evolution of the martingale in a single step, and a general theorem showing the local polarization suffices for strong polarization.
In this talk I will introduce polarization and polar codes and, time permitting, present a full proof of our main theorem. No prior background on polar codes will be assumed.
Based on joint work with Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran and Atri Rudra.- Derandomizing Isolation Lemma: A geometric approach [Jul 31 2017 +]
Date: July 31, 2017.
Time: 2pm to 3pm
Venue: Conference Room, Kanwal Rekhi Building, first floorWe present a geometric approach towards derandomizing the Isolation lemma for a given family of subsets, i.e., deterministically constructing a weight assignment which ensures a unique minimum weight set in the family. The idea is to work with a polytope corresponding to the family of sets. In this talk, we present the approach in terms of general polytopes and describe a sufficient condition on the polytope for this approach to work. The approach gives a quasi-polynomially bounded weight assignment. Finally, we show that two specific families - perfect matchings in bipartite graphs and common base sets of two matroids - satisfy the required condition and thus, we get an isolating weight assignment for these cases. This also puts the two problems in quasi-NC.
Based on joint works with Stephen Fenner and Thomas Thierauf. - Exploring Algebraic Methods: Applications and Key Challenges in Polynomials [Feb 21 2023 +]