检索结果-内蒙古大学图书馆

monotone Arithmetic complexity of Graph Homomorphism Polynomials

ALGORITHMICA 2023年第9期85卷 2554-2579页

作者： Komarath, Balagopal Pandey, Anurag Rahul, C. S. IIT Gandhinagar Discipline Comp Sci Gandhinagar 382055 Gujarat India Saarland Univ Dept Comp Sci Saarland Informat Campus D-66123 Saarbrucken Saarland Germany IIT Goa Dept Comp Sci Ponda 403401 Goa India

We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP , VP , and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Further-more, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formu-las in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials.

关键词： Homomorphism polynomials monotone complexity Algebraic complexity Graph algorithms Fine-grained complexity Fixed-parameter algorithms and complexity Treewidth Pathwidth Treedepth Graph homomorphisms Algebraic circuits Algebraic branching programs Algebraic formulas

来源：评论

学校读者我要写书评

暂无评论

Proof complexity of monotone Branching Programs 1

引用

18th Conference on Computability in Europe (CiE)

作者： Das, Anupam Delkos, Avgerinos Univ Birmingham Birmingham W Midlands England

ISBN: (数字)9783031087400

ISBN: (纸本)9783031087400;9783031087394

We investigate the proof complexity of systems based on positive branching programs, i.e. non-deterministic branching programs (NBPs) where, for any 0-transition between two nodes, there is also a 1-transition. Positive NBPs compute monotone Boolean functions, like negation-free circuits or formulas, but constitute a positive version of (non-uniform) NL, rather than P or NC1, respectively. The proof complexity of NBPs was investigated in previous work by Buss, Das and Knop, using extension variables to represent the dagstructure, over a language of (non-deterministic) decision trees, yielding the system eLNDT. Our system eLNDT(+) is obtained by restricting their systems to a positive syntax, similarly to how the `monotone sequent calculus' MLK is obtained from the usual sequent calculus LK by restricting to negation-free formulas. Our main result is that eLNDT(+) polynomially simulates eLNDT over positive sequents. Our proof method is inspired by a similar result for MLK by Atserias, Galesi and Pudl ' ak, that was recently improved to a bona fide polynomial simulation via works of Je.r ' abek and Buss, Kabanets, Kolokolova and Kouck ' y. Along the way we formalise several properties of counting functions within eLNDT(+) by polynomial-size proofs and, as a case study, give explicit polynomial-size poofs of the propositional pigeonhole principle.

关键词： Proof complexity Branching Programs monotone complexity

来源：评论

学校读者我要写书评

暂无评论

PROOF complexity OF POSITIVE BRANCHING PROGRAMS

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2025年第1期21卷 23:1-23:35页

作者： Das, Anupam Delkos, Avgerinos Univ Birmingham Birmingham England

We investigate the proof complexity of systems based on positive branching programs, i.e. non-deterministic branching programs (NBPs) where, for any 0-transition between two nodes, there is also a 1-transition. Positive NBPs compute monotone Boolean functions, just like negation-free circuits or formulas, but constitute a positive version of (non-uniform) NL, rather than P or NC1, respectively. The proof complexity of NBPs was investigated in previous work by Buss, Das and Knop, using extension variables to represent the dag-structure, over a language of (non- deterministic) decision trees, yielding the system eLNDT. Our system eLNDT` is obtained by restricting their systems to a positive syntax, similarly to how the 'monotone sequent calculus' MLK is obtained from the usual sequent calculus LK by restricting to negation-free formulas. Our main result is that eLNDT` polynomially simulates eLNDT over positive sequents. Our proof method is inspired by a similar result for MLK by Atserias, Galesi and Pudlak, that was recently improved to a bona fide polynomial simulation via works of Jerabek and Buss, Kabanets, Kolokolova and Koucky. Along the way we formalise several properties of counting functions within eLNDT` by polynomial-size proofs and, as a case study, give explicit polynomial-size proofs of the propositional pigeonhole principle.

关键词： complexity monotone complexity Branching programs

来源：评论

学校读者我要写书评

暂无评论

Triviality and Minimality in the Degrees of monotone complexity

引用

JOURNAL OF LOGIC AND COMPUTATION 2012年第2期22卷 197-206页

作者： Calhoun, William C. Bloomsburg Univ Dept Math Comp Sci & Stat Bloomsburg PA 17815 USA

monotone complexity, K-m, is a variant of Kolmogorov complexity that was introduced independently by Levin and Schnorr. The relative randomness of reals may be defined via monotone complexity. Equivalence classes of reals under monotone complexity are the K-m-degrees, similar to the K-degrees defined via prefix-free complexity. A real alpha is K-m-trivial if K-m(alpha (sic) n) <= K-m(n). Here, an argument by Stephan is strengthened to show that each Turing degree d >= 0' contains a K-m-trivial real. In contrast, all K-trivial reals are Delta(0)(2) (Chaitin) and low, since they are low for random (Hirschfeldt and Nies). A non-decreasing, function f: omega ->omega is defined to be computably infinitesimal if it is dominated by every computable, nondecreasing, unbounded function. It is shown that the monotone complexity of any Km-trivial real is computably infinitesimal. If a K-m-minimal real exists, it is K-m-trivial. The operation circle times horizontally stretches the complexity graph of a real alpha by a strictly increasing computable function f. Areal a is invariant under computable stretching if alpha circle times f equivalent to K-m alpha for any such f. It is shown that any K-m-minimal real is invariant under computable stretching.

关键词： Kolmogorov complexity monotone complexity randomness trivial reals

来源：评论

学校读者我要写书评

暂无评论

Lifting Nullstellensatz to monotone Span Programs over Any Field 2018

Lifting Nullstellensatz to Monotone Span Programs over Any F...

引用

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC)

作者： Pitassi, Toniann Robere, Robert Univ Toronto Toronto ON Canada Inst Adv Study Olden Lane Princeton NJ 08540 USA

ISBN: (纸本)9781450355599

We characterize the size of monotone span programs computing certain "structured" boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula. This yields the first exponential lower bounds for monotone span programs over arbitrary fields, the first exponential separations between monotone span programs over fields of different characteristic, and the first exponential separation between monotone span programs over arbitrary fields and monotone circuits. We also show tight quasipolynomial lower bounds on monotone span programs computing directed st-connectivity over arbitrary fields, separating monotone span programs from non-deterministic logspace and also separating monotone and non-monotone span programs over GF (2). Our results yield the same lower bounds for linear secret sharing schemes due to the previously known relationship between monotone span programs and linear secret sharing. To prove our characterization we introduce a new and general tool for lifting polynomial degree to rank over arbitrary fields.

关键词： circuit complexity monotone complexity span programs rank method switching networks comparator circuits formulas

来源：评论

学校读者我要写书评

暂无评论

Strongly Exponential Lower Bounds for monotone Computation 2017

Strongly Exponential Lower Bounds for Monotone Computation

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Pitassi, Toniann Robere, Robert Univ Toronto Dept Comp Sci Toronto ON Canada

ISBN: (纸本)9781450345286

For a universal constant alpha > 0, we prove size lower bounds of 2(alpha N) for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where N is the number of variables of the underlying function. Our lower bounds improve on the best previous bounds in each of these models, and are the best possible for any function up to the constant factor alpha. Moreover, we give one unified proof that is short and fairly elementary.

关键词： circuit complexity monotone complexity span programs rank method switching networks comparator circuits formulas

来源：评论

学校读者我要写书评

暂无评论

The price of query rewriting in ontology-based data access

引用

ARTIFICIAL INTELLIGENCE 2014年 213卷 42-59页

作者： Gottlob, Georg Kikot, Stanislav Kontchakov, Roman Podolskii, Vladimir Schwentick, Thomas Zakharyaschev, Michael Univ Oxford Dept Comp Sci Oxford OX1 2JD England Univ London Dept Comp Sci & Informat Syst London WC1E 7HU England VA Steklov Math Inst Moscow 117333 Russia TU Dortmund Fak Informat Dortmund Germany

We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontology-based data access with ontology languages such as OWL 2 QL, linear Datalog(+/-) and sticky Datalog. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case of datalog rewritings), suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP subset of P/poly. We also prove that nonrecursive datalog rewritings are in general exponentially more succinct than positive existential rewritings, while first-order rewritings can be superpolynomially more succinct than positive existential rewritings. On the other hand, we construct polynomial-size positive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Ontology Datalog Conjunctive query Query rewriting Succinctness Boolean circuit monotone complexity

来源：评论

学校读者我要写书评

暂无评论

Just a Pebble Game

Just a Pebble Game

引用

28th Annual IEEE Conference on Computational complexity (CCC)

作者： Chan, Siu Man Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)9780769549972

The two-player pebble game of Dymond-Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems. Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the pebbling algorithm of Dymond-Tompa. These lower bounds include, the monotone separation of m-L from m-NL by studying the size of monotone switching networks in Potechin '10;a new semantic separation of NC from P and of NCi from NCi+1 by studying circuit depth, based on the techniques developed for the semantic separation of NC1 from NC2 by the universal composition relation in Edmonds-Impagliazzo-Rudich-Sgall '01 and in Hastad-Wigderson '97;and the monotone separation of m-NC from m-P and of m-NCi from m-NCi+1 by studying - the depth of monotone circuits in Raz-McKenzie '99;and - the size of monotone switching networks in Chan-Potechin '12. This supports the attempt to separate NC from P by focusing on depth complexity, and suggests the study of combinatorial invariants shaped by pebbling for proving lower bounds. An application to proof complexity gives tight bounds for the size and the depth of some refinements of resolution refutations.

关键词： parallel algorithms depth space circuits switching networks proof complexity resolution refutations monotone complexity pebble games hardness escalation

来源：评论

学校读者我要写书评

暂无评论

A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials

引用

SBORNIK MATHEMATICS 2012年第10期203卷 1411-1447页

作者： Gashkov, S. B. Sergeev, I. S. Moscow MV Lomonosov State Univ Fac Mech & Math Moscow Russia

This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis {x + y, x . y} boolean OR {a . x vertical bar a is an element of R+}. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree m - 1 in each of the n variables with coefficients 0 and 1 having additive monotone complexity m((1-o(1))n) and multiplicative monotone complexity m((1/2-o(1))n) as m(n) -> infinity. In this form, the lower bounds derived here are sharp.

关键词： lower bounds for complexity arithmetic circuits thin sets monotone complexity permanent

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for monotone Switching Networks via Fourier Analysis 12

Tight Bounds for Monotone Switching Networks via Fourier Ana...

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Chan, Siu Man Potechin, Aaron Univ Calif Berkeley Berkeley CA 94720 USA MIT Cambridge MA USA

ISBN: (纸本)9781450312455

We prove tight size bounds on monotone switching networks for the k-clique problem, and for an explicit monotone problem by analyzing the generation problem with a pyramid structure of height h. This gives alternative proofs of the separations of m-NC from m-P and of m-NCi from m-NCi+1, different from Raz-McKenzie (Combinatorica '99). The enumerative-combinatorial and Fourier analytic techniques in this work are very different from a large body of work on circuit depth lower bounds, and may be of independent interest.

关键词： Lower bounds space complexity parallel complexity monotone complexity switching networks

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：