14 citations · 30 across the 18 of their papers we have counts for
19 papers · 1 filter
Tight Lower Bounds for Algebraic Communication and Applications
Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +2
Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. In this work, we study an algebraic varia…
New and Improved Concrete Lower Bounds for Orthogonal Vectors
Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah +1
The Orthogonal Vectors Problem (OV) takes as input two sets each containing -dimensional Boolean vectors, and outputs if and only if there exists …
Hard CNF Instances for Ideal Proof Systems
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments.…
Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
Amik Raj Behera, Magnus Rahbek Dalgaard Hansen, Nutan Limaye +1
In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). S…
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +3
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure…
New Bounds for the Ideal Proof System in Positive Characteristic
Amik Raj Behera, Nutan Limaye, Varun Ramanathan +1
In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by…
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi [GP18]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propos…
Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
Per Austrin, Ioana O. Bercea, Mayank Goswami +2
Given a -CNF formula and an integer , we study algorithms that obtain solutions to the formula that are maximally dispersed. For , the problem of computing the diame…
Towards Optimal Depth-Reductions for Algebraic Formulas
Hervé Fournier, Nutan Limaye, Guillaume Malod +2
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s)…
Schur Polynomials do not have small formulas if the Determinant doesn't!
Prasad Chaugule, Mrinal Kumar, Nutan Limaye +3
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric fu…
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush +2
We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit made up of gates that compute constant-degree Polynomial Threshold function…
A Fixed-Depth Size-Hierarchy Theorem for AC via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan +2
We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC circuits; in particular, for fixed , the class of uniform AC for…
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Suryajith Chillara, Christian Engels, Nutan Limaye +1
We study the size blow-up that is necessary to convert an algebraic circuit of product-depth to one of product-depth in the multilinear setting. We show that for every po…
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
In this paper, we study the algebraic formula complexity of multiplying many matrices, denoted , and show that the well-known divide-and-conquer a…
Small Depth Proof Systems
Andreas Krebs, Nutan Limaye, Meena Mahajan +1
A proof system for a language L is a function f such that Range(f) is exactly L. In this paper, we look at proofsystems from a circuit complexity point of view and study proof syst…
Streaming algorithms for recognizing nearly well-parenthesized expressions
Andreas Krebs, Nutan Limaye, Srikanth Srinivasan
We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there…
A Log-space Algorithm for Canonization of Planar Graphs
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar +2
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. We bridge this gap for a n…
3-connected Planar Graph Isomorphism is in Log-space
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar
We show that the isomorphism of 3-connected planar graphs can be decided in deterministic log-space. This improves the previously known bound ULcoUL of Thierauf and Wagner.
Longest paths in Planar DAGs in Unambiguous Logspace
Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar
We show via two different algorithms that finding the length of the longest path in planar directed acyclic graph (DAG) is in unambiguous logspace UL, and also in the complement cl…