Zobrazeno 1 - 10
of 182
pro vyhledávání: '"Mahajan, Meena"'
Autor:
Dahiya, Yogesh, Mahajan, Meena
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-com
Externí odkaz:
http://arxiv.org/abs/2209.12877
Autor:
Mahajan, Meena, Sood, Gaurav
Publikováno v:
Logical Methods in Computer Science, Volume 20, Issue 3 (September 10, 2024) lmcs:12710
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-distanc
Externí odkaz:
http://arxiv.org/abs/2205.13428
Publikováno v:
ACM Transactions on Computation Theory, Volume 16, Issue 2, Article No. 6 (March 2024)
We prove the first genuine QBF 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 resolutio
Externí odkaz:
http://arxiv.org/abs/2012.06779
Publikováno v:
ACM Trans. Comput. Logic 24, 1, Article 8 (January 2023)
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 devisin
Externí odkaz:
http://arxiv.org/abs/2005.11589
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 polyn
Externí odkaz:
http://arxiv.org/abs/2003.04834
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Dahiya, Yogesh, Mahajan, Meena
Publikováno v:
In Theoretical Computer Science 2 November 2023 978
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 com
Externí odkaz:
http://arxiv.org/abs/1901.05911
Publikováno v:
Logical Methods in Computer Science, Volume 13, Issue 2 (June 8, 2017) lmcs:2198
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 ex
Externí odkaz:
http://arxiv.org/abs/1611.01328
Autor:
Mahajan, Meena, Saurabh, Nitin
We provide a list of new natural $\mathsf{VNP}$-intermediate polynomial families, based on basic (combinatorial) $\mathsf{NP}$-complete problems that are complete under parsimonious reductions. Over finite fields, these families are in $\mathsf{VNP}$
Externí odkaz:
http://arxiv.org/abs/1603.04606