All reports by Author Meena Mahajan:

__
TR23-132
| 12th September 2023
__

Yogesh Dahiya, Meena Mahajan, Sasank Mouli#### New lower bounds for Polynomial Calculus over non-Boolean bases

__
TR23-061
| 2nd May 2023
__

Abhimanyu Choudhury, Meena Mahajan#### Dependency schemes in CDCL-based QBF solving: a proof-theoretic study

__
TR23-039
| 28th March 2023
__

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan#### Query Complexity of Search Problems

Revisions: 1

__
TR23-012
| 16th February 2023
__

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah#### Linear threshold functions in decision lists, decision trees, and depth-2 circuits

__
TR22-080
| 25th May 2022
__

Meena Mahajan, Gaurav Sood#### QBF Merge Resolution is powerful but unnatural

__
TR22-001
| 28th December 2021
__

Yogesh Dahiya, Meena Mahajan#### On (Simple) Decision Tree Rank

Revisions: 1

__
TR20-188
| 12th December 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood#### Hard QBFs for Merge Resolution

__
TR20-082
| 23rd May 2020
__

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals#### MaxSAT Resolution and Subcube Sums

Revisions: 2

__
TR20-031
| 10th March 2020
__

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

__
TR20-005
| 17th January 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Revisions: 1

__
TR19-007
| 17th January 2019
__

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh#### Lower Bounds for Linear Decision Lists

__
TR18-172
| 11th October 2018
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Building Strategies into QBF Proofs

__
TR18-146
| 18th August 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Shortest path length with bounded-alternation $(\min, +)$ formulas

__
TR18-102
| 15th May 2018
__

Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan#### Short Proofs in QBF Expansion

__
TR18-020
| 30th January 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Computing the maximum using $(\min, +)$ formulas

Comments: 1

__
TR17-037
| 25th February 2017
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Understanding Cutting Planes for QBFs

__
TR16-164
| 25th October 2016
__

Andreas Krebs, Meena Mahajan, Anil Shukla#### Relating two width measures for resolution proofs

__
TR16-038
| 15th March 2016
__

Meena Mahajan, Nitin Saurabh#### Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

__
TR15-204
| 14th December 2015
__

Meena Mahajan, Anuj Tawari#### Sums of read-once formulas: How many summands suffice?

Revisions: 2

__
TR15-202
| 11th December 2015
__

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah#### Building above read-once polynomials: identity testing and hardness of representation

__
TR15-152
| 16th September 2015
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Are Short Proofs Narrow? QBF Resolution is not Simple.

__
TR15-118
| 23rd July 2015
__

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan#### The shifted partial derivative complexity of Elementary Symmetric Polynomials

__
TR15-059
| 10th April 2015
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Feasible Interpolation for QBF Resolution Calculi

__
TR14-180
| 22nd December 2014
__

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Space-Efficient Approximations for Subset Sum

__
TR14-163
| 29th November 2014
__

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh#### Homomorphism polynomials complete for VP

__
TR13-102
| 17th July 2013
__

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Small Depth Proof Systems

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

__
TR10-103
| 28th June 2010
__

Andreas Krebs, Nutan Limaye, Meena Mahajan#### Counting paths in VPA is complete for \#NC$^1$

__
TR10-101
| 25th June 2010
__

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer#### Counting Classes and the Fine Structure between NC$^1$ and L.

__
TR08-048
| 8th April 2008
__

Meena Mahajan, B. V. Raghavendra Rao#### Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

__
TR07-087
| 11th July 2007
__

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao#### Arithmetizing classes around NC^1 and L

__
TR06-100
| 17th July 2006
__

Meena Mahajan, Jayalal Sarma#### On the Complexity of Rank and Rigidity

__
TR06-009
| 10th January 2006
__

Nutan Limaye, Meena Mahajan, Jayalal Sarma#### Evaluating Monotone Circuits on Cylinders, Planes and Tori

__
TR00-088
| 28th November 2000
__

Meena Mahajan, V Vinay#### A note on the hardness of the characteristic polynomial

__
TR99-030
| 9th July 1999
__

Meena Mahajan, P R Subramanya, V Vinay#### A Combinatorial Algorithm for Pfaffians

__
TR99-008
| 19th March 1999
__

Eric Allender, Vikraman Arvind, Meena Mahajan#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1
,
Comments: 1

__
TR98-012
| 2nd February 1998
__

Meena Mahajan, V Vinay#### Determinant: Old Algorithms, New Insights

__
TR97-036
| 1st August 1997
__

Meena Mahajan, V Vinay#### Determinant: Combinatorics, Algorithms, and Complexity

__
TR97-033
| 1st August 1997
__

Meena Mahajan, Venkatesh Raman#### Parametrizing Above Guaranteed Values: MaxSat and MaxCut

__
TR95-043
| 14th September 1995
__

Eric Allender, Jia Jiao, Meena Mahajan, V Vinay#### Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

Yogesh Dahiya, Meena Mahajan, Sasank Mouli

In this paper, we obtain new size lower bounds for proofs in the

Polynomial Calculus (PC) proof system, in two different settings.

1. When the Boolean variables are encoded using $\pm 1$ (as opposed

to $0,1$): We establish a lifting theorem using an asymmetric gadget

$G$, showing ...
more >>>

Abhimanyu Choudhury, Meena Mahajan

We formalize the notion of proof systems obtained by adding normal dependency schemes into the QCDCL proof system underlying algorithms for solving Quantified Boolean Formulas, by exploring the addition of the dependency schemes via two approaches: one as a preprocessing tool, and second in propagation and learnings in the QCDCL ... more >>>

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF$\circ$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists ... more >>>

Meena Mahajan, Gaurav Sood

The Merge Resolution proof system (M-Res) for QBFs, proposed by Beyersdorff et al. in 2019, explicitly builds partial strategies inside refutations. The original motivation for this approach was to overcome the limitations encountered in long-distance Q-Resolution proof system (LD-Q-Res), where the syntactic side-conditions, while prohibiting all unsound resolutions, also end ... more >>>

Yogesh Dahiya, Meena Mahajan

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood

We prove the first proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantified Boolean formulas (QBF) with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs in MRes consist of resolution steps together ... more >>>

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>>

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.

We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study bounded depth $(\min, +)$ formulas computing the shortest path polynomial. For depth $2d$ with $d \geq 2$, we obtain lower bounds parametrized by certain fan-in restrictions on all $+$ gates except those at the bottom level. For depth $4$, in two regimes of the parameter, the bounds are ... more >>>

Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan

For quantified Boolean formulas (QBF) there are two main different approaches to solving: QCDCL and expansion solving. In this paper we compare the underlying proof systems and show that expansion systems admit strictly shorter proofs than CDCL systems for formulas of bounded quantifier complexity, thus pointing towards potential advantages of ... more >>>

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$

over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ...
more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>>

Andreas Krebs, Meena Mahajan, Anil Shukla

In this short note, we revisit two hardness measures for resolution proofs: width and asymmetric width. It is known that for every unsatisfiable CNF F,

width(F \derives \Box) \le awidth(F \derives \Box) + max{ awidth(F \derives \Box), width(F)}.

We give a simple direct proof of the upper bound, ... more >>>

Meena Mahajan, Nitin Saurabh

We provide a list of new natural VNP-intermediate polynomial

families, based on basic (combinatorial) NP-complete problems that

are complete under \emph{parsimonious} reductions. Over finite

fields, these families are in VNP, and under the plausible

hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under

oracle-circuit reductions) nor in VP. Prior to ...
more >>>

Meena Mahajan, Anuj Tawari

An arithmetic read-once formula (ROF) is a formula (circuit of fan-out

1) over

$+, \times$ where each variable labels at most one leaf.

Every multilinear polynomial can be expressed as the sum of ROFs.

In this work, we prove, for certain multilinear polynomials,

a tight lower bound ...
more >>>

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Polynomial Identity Testing (PIT) algorithms have focused on

polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted

formulas. Read-once polynomials (ROPs) are computed by read-once

formulas (ROFs) and are the simplest of read-restricted polynomials.

Building structures above these, we show the following:

\begin{enumerate}

\item A deterministic polynomial-time non-black-box ...
more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

The groundbreaking paper `Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>>

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan

We continue the study of the shifted partial derivative measure, introduced by Kayal (ECCC 2012), which has been used to prove many strong depth-4 circuit lower bounds starting from the work of Kayal, and that of Gupta et al. (CCC 2013).

We show a strong lower bound on the dimension ... more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or expansion-based solving. This both provides the first general lower bound method for QBF ... more >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

SUBSET SUM is a well known NP-complete problem:

given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ...
more >>>

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

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 systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

Meena Mahajan, B. V. Raghavendra Rao

Functions in arithmetic NC1 are known to have equivalent constant

width polynomial degree circuits, but the converse containment is

unknown. In a partial answer to this question, we show that syntactic

multilinear circuits of constant width and polynomial degree can be

depth-reduced, though the resulting circuits need not be ...
more >>>

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

The parallel complexity class NC^1 has many equivalent models such as

polynomial size formulae and bounded width branching

programs. Caussinus et al. \cite{CMTV} considered arithmetizations of

two of these classes, #NC^1 and #BWBP. We further this study to

include arithmetization of other classes. In particular, we show that

counting paths ...
more >>>

Meena Mahajan, Jayalal Sarma

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound

$k$, we want to decide whether the rank of $M$ can be brought down to

below $r$ by changing at most $k$ entries of $M$. This is a decision

version of the well-studied notion of ...
more >>>

Nutan Limaye, Meena Mahajan, Jayalal Sarma

We re-examine the complexity of evaluating monotone planar circuits

MPCVP, with special attention to circuits with cylindrical

embeddings. MPCVP is known to be in NC^3, and for the special

case of upward stratified circuits, it is known to be in

LogDCFL. We characterize cylindricality, which ...
more >>>

Meena Mahajan, V Vinay

In this note, we consider the problem of computing the

coefficients of the characteristic polynomial of a given

matrix, and the related problem of verifying the

coefficents.

Santha and Tan [CC98] show that verifying the determinant

(the constant term in the characteristic polynomial) is

complete for the class C=L, ...
more >>>

Meena Mahajan, P R Subramanya, V Vinay

The Pfaffian of an oriented graph is closely linked to

Perfect Matching. It is also naturally related to the determinant of

an appropriately defined matrix. This relation between Pfaffian and

determinant is usually exploited to give a fast algorithm for

computing Pfaffians.

We present the first completely combinatorial algorithm for ... more >>>

Eric Allender, Vikraman Arvind, Meena Mahajan

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root ...
more >>>

Meena Mahajan, V Vinay

In this paper we approach the problem of computing the characteristic

polynomial of a matrix from the combinatorial viewpoint. We present

several combinatorial characterizations of the coefficients of the

characteristic polynomial, in terms of walks and closed walks of

different kinds in the underlying graph. We develop algorithms based

more >>>

Meena Mahajan, V Vinay

We prove a new combinatorial characterization of the

determinant. The characterization yields a simple

combinatorial algorithm for computing the

determinant. Hitherto, all (known) algorithms for

determinant have been based on linear algebra. Our

combinatorial algorithm requires no division and works over

arbitrary commutative rings. It also lends itself to

more >>>

Meena Mahajan, Venkatesh Raman

In this paper we investigate the parametrized

complexity of the problems MaxSat and MaxCut using the

framework developed by Downey and Fellows.

Let $G$ be an arbitrary graph having $n$ vertices and $m$

edges, and let $f$ be an arbitrary CNF formula with $m$

clauses on $n$ variables. We improve ...
more >>>

Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

We investigate the phenomenon of depth-reduction in commutative

and non-commutative arithmetic circuits. We prove that in the

commutative setting, uniform semi-unbounded arithmetic circuits of

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the ...
more >>>