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

31st Conference on Computational complexity (CCC)

作者： Forbes, Michael A. Shpilka, Amir Tzameret, Iddo Wigderson, Avi Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Tel Aviv Univ Dept Comp Sci Tel Aviv Israel Royal Holloway Univ London Dept Comp Sci Egham Surrey England Inst Adv Study Sch Math Princeton NJ 08540 USA

ISBN: (纸本)9783959770088

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi [26], where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov [25], which is a function f : {0,1}n F such that any polynomial f agreeing with f on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where [f(g) equals l/p(,) for a constant -degree polynomial p depending on the relevant circuit class. We believe

关键词： Proof complexity algebraic complexity Nullstellensatz Subset-Sum

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the uniqueness and computation of commuting extensions

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2024年 703卷 645-666页

作者： Koiran, Pascal Univ Claude Bernard Lyon 1 ENS Lyon CNRS INRIALIPUMR 5668 F-69342 Lyon 07 France

A tuple (Z(1) , ... , Z( p) ) of matrices of size r x r is said to be a commuting extension of a tuple (A(1), ... , A(p) ) of matrices of size n x n if the Z i pairwise commute and each A i sits in the upper left corner of a block decomposition of Z i (here, r and n are two arbitrary integers with n < r ). This notion was discovered and rediscovered in several contexts including algebraic complexity theory (in Strassen's work on tensor rank), in numerical analysis for the construction of cubature formulas and in quantum mechanics for the study of computational methods and the study of the so-called "quantum Zeno dynamics." Commuting extensions have also attracted the attention of the linear algebra community. In this paper we present 3 types of results: (i) Theorems on the uniqueness of commuting extensions for three matrices or more. (ii) Algorithms for the computation of commuting extensions of minimal size. These algorithms work under the same assumptions as our uniqueness theorems. They are applicable up to r = 4n/3, n/ 3, and are apparently the first provably efficient algorithms for this problem applicable beyond r = n + 1. (iii) A genericity theorem showing that our algorithms and uniqueness theorems can be applied to a wide range of input matrices. (c) 2024 The Author. Published by Elsevier Inc. This is an open access article under the CC BY license (http:// *** /licenses /by /4 .0/).

关键词： Commuting matrices Algorithms algebraic complexity Tensor rank Quantum information Numerical analysis

来源：评论

学校读者我要写书评

暂无评论

Functional Lower Bounds in algebraic Proofs: Symmetry, Lifting, and Barriers 2024

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifti...

引用

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

作者： Hakoniemi, Tuomas Limaye, Nutan Tzameret, Iddo Univ Helsinki Helsinki Finland IT Univ Copenhagen Copenhagen Denmark Imperial Coll London London England

ISBN: (纸本)9798400703836

Strong algebraic proof systems such as IPS (Ideal Proof System;Grochow-Pitassi [***, 65(6):37:155, 2018]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound Method (Forbes, Shpilka, Tzameret and Wigderson [Theory Comput., 17: 1-88, 2021]), which reduces the hardness of refuting a polynomial equation f((x) over tilde)=0 with no Boolean solutions to the hardness of computing the function 1/f((x) over tilde) over the Boolean cube with an algebraic circuit. Using symmetry we provide a general way to obtain many new hard instances against fragments of IPS via the functional lower bound method. This includes hardness over finite fields and hard instances different from Subset Sum variants both of which were unknown before, and stronger constant-depth lower bounds. Conversely, we expose the limitation of this method by showing it cannot lead to proof complexity lower bounds for any hard Boolean instance (e.g., CNFs) for any sufficiently strong proof systems. Specifically, we show the following: center dot Nullstellensatz degree lower bounds using symmetry: Extending [Forbes et al. Theory Comput., 17: 1-88, 2021] we show that every unsatisfiable symmetric polynomial with n variables requires degree > n refutations (over sufficiently large characteristic). Using symmetry again, by characterising the n/2-homogeneous slice appearing in refutations, we show that unsatisfiable invariant polynomials of degree n/2 require degree >= n refutations. center dot Lifting to size lower bounds: Lifting our Nullstellensatz degree bounds to IPS-size lower bounds, we obtain exponential lower bounds for any poly-logarithmic degree symmetric instance against IPS refutations written as oblivious read-once algebraic programs (roABP-IPS). For invariant polynomials, we show lower bounds agains

关键词： Proof complexity algebraic circuits algebraic complexity algebraic proof systems lower bounds Nullstellensatz IPS

来源：评论

学校读者我要写书评

暂无评论

New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials 49

New Bounds on Quotient Polynomials with Applications to Exac...

引用

International Symposium on Symbolic and algebraic Computation (ISSAC)

作者： Nahshon, Ido Shpilka, Amir Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9798400706967

We prove that for monic polynomials f,g epsilon C[x] such that g divides f, the l(2)-norm of the quotient f/g is bounded by parallel to f parallel to(1) . (O) over tilde(parallel to g parallel to(3)(0) deg(2) f)parallel to g parallel to-1, improving upon the previously known exponential (in deg(f)) bounds for general polynomials. This result implies that the trivial long division algorithm runs in quasi-linear time relative to the input size and number of terms of the quotient, thus solving a long-standing problem. We also bound the number of terms of f/g in some special cases. When f,g epsilon Z[x] and g is a cyclotomic-free (i.e., it has no cyclotomic factors) trinomial, we prove that parallel to f/g parallel to(0) <= O (parallel to f parallel to(0) size (f)(2) . log(6) deg g). When.. is a binomial with g(+/- 1) not equal 0, we prove that the sparsity is at most O (parallel to f parallel to(0) (log parallel to f parallel to(0) + log parallel to f parallel to(infinity))). Both upper bounds are polynomial in the input-size. Leveraging these results, we provide a polynomialtime algorithm for deciding whether a cyclotomic-free trinomial divides a sparse polynomial over the integers.

关键词： Sparse Polynomials algebraic complexity Number Theory Divisibility Testing Long Division Euclidean Division

来源：评论

学校读者我要写书评

暂无评论

DERANDOMIZATION FROM algebraic HARDNESS

引用

SIAM JOURNAL ON COMPUTING 2022年第2期51卷 315-335页

作者： Guo, Zeyu Kumar, Mrinal Saptharishi, Ramprasad Solomon, Noam Univ Haifa Dept Comp Sci Haifa Israel IIT Kanpur Kanpur Uttar Pradesh India Indian Inst Technol Dept Comp Sci & Engn Mumbai Maharashtra India Univ Toronto Toronto ON Canada Tata Inst Fundamental Res Mumbai Maharashtra India MIT Dept Math Cambridge MA 02139 USA

A hitting-set generator (HSG) is a polynomial map Gen : F-k -> F-n such that for all n-variate polynomials C of small enough circuit size and degree, if C is nonzero, then C circle Gen is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following result over any field F of characteristic zero: Let k is an element of N and delta > 0 be arbitrary constants. Suppose {P-d}(d is an element of N) is an explicit family of k-variate polynomials such that deg P-d = d and P-d requires algebraic circuits of size d(delta). Then, there are explicit hitting sets of polynomial size for the class VP. This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps [N. Nisan and A. Wigderson, J. Comput. System Sci., 49 (1994), pp. 149-167;V. Kabanets and R. Impagliazzo, Comput. complexity, 13 (2004), pp. 1-46;M. Agrawal, S. Ghosh, and ***, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8107-8118;M. Kumar, R. Saptharishi, and A. Tengse, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 639-646], our construction is purely algebraic and does not rely on the notion of combinatorial designs. As a direct consequence, we show that even saving a single point from the "trivial" explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let k is an element of N and delta > 0 be arbitrary constants. Suppose for every s large enough, there is an explicit hitting set of size at most ((s + 1)(k) - 1) for the class of k-variate polynomials of individual degree s that are computable by size s(delta) circuits. Then

关键词： algebraic complexity polynomial identity testing hardness versus randomness algebraic circuit lower bounds hitting set generators

来源：评论

学校读者我要写书评

暂无评论

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof complexity 2021

Iterated Lower Bound Formulas: A Diagonalization-Based Appro...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Santhanam, Rahul Tzameret, Iddo Univ Oxford Oxford England Imperial Coll London London England

ISBN: (纸本)9781450380539

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally. We use the approach to give an explicit sequence of CNF formulas {phi(n)} such that VNP not equal VP iff there are no polynomial-size IPS proofs for the formulas phi(n). This provides a natural equivalence between proof complexity lower bounds and standard algebraic complexity lower bounds. Our proof of this fact uses the implication from IPS lower bounds to algebraic complexity lower bounds due to Grochow and Pitassi together with a diagonalization argument: the formulas phi(n) themselves assert the non-existence of short IPS proofs for formulas encoding VNP not equal VP at a different input length. Our result also has meta-mathematical implications: it gives evidence for the difficulty of proving strong lower bounds for IPS within IPS. For any strong enough propositional proof system R, we define the iterated R-lower bound formulas, which inductively assert the non-existence of short R proofs for formulas encoding the same statement at a different input length, and propose them as explicit hard candidates for the proof system R. We observe that this hypothesis holds for Resolution following recent results of Atserias and Muller and of Garlik, and give evidence in favour of it for other proof systems.

关键词： diagonalization proof complexity lower bounds circuit complexity lower bounds iterated lower bound formulas Ideal Proof System algebraic complexity

来源：评论

学校读者我要写书评

暂无评论

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

引用

JOURNAL OF THE ACM 2022年第2期69卷 1-44页

作者： Chiesa, Alessandro Forbes, Michael A. Gur, Tom Spooner, Nicholas Univ Calif Berkeley Berkeley CA 94720 USA Ecole Polytech Fed Lausanne Lausanne Switzerland Univ Illinois Champaign IL 61801 USA Univ Warwick Coventry CV34 5TL W Midlands England

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP* model captures this setting. In this work, we study the following question: Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers;that is, NEXP subset of ZK-MIP*. Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP* model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge;this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.

关键词： Zero knowledge multi-prover interactive proofs quantum entangled strategies interactive PCPs sumcheck protocol algebraic complexity

来源：评论

学校读者我要写书评

暂无评论

Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication 2022

Set-Multilinear and Non-commutative Formula Lower Bounds for...

引用

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

作者： Tavenas, Sebastien Limaye, Nutan Srinivasan, Srikanth Univ Grenoble Alpes Univ Savoie Mt Blanc CNRS LAMA Chambery France ITU Copenhagen Copenhagen Denmark Aarhus Univ Aarhus Denmark

ISBN: (纸本)9781450392648

An algebraic Formula for a polynomialP is an element of F[x(1),...,...,x(N)] is an algebraic expression for P(x(1,)...,...,x(N)) using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class NC1. Proving lower bounds against this model is thus an important problem. It is known that, to prove superpolynomial lower bounds against algebraic formulas, it suffices to prove good enough lower bounds against restricted kinds of formulas known as Set-Multilinear formulas, for computing a polynomia P(x(1),...,...,x(N)) of degree O( logN/log logN). In the past, many superpolynomial lower bounds were found, but they are of the form Omega(f (d) poly(N)) (where f is typically a subexponential function) which is insufficient to get lower bounds for general formulas. Recently, the authors proved the first non-FPT lower bounds, i.e., a lower bound of the form N-Omega,(f((d))) against small-depth set-multilinear formulas (and also for circuits). In this work, we extend this result in two directions. Large-depth set-multilinear formulas. In the setting of general set-multilinear formulas, we prove a lower bound of ( logn) (Omega(logd)) for computing the Iterated Matrix Multiplication polynomial IMMn,d. In particular, this implies the first superpolynomial lower bound against unbounded-depth set-multilinear formulas computing IMMn,n. As a corollary, this resolves the homogeneous version of a question of Nisan (asked in 1991) regarding the relative power of algebraic formulas and Branching programs in the non-commutative setting. Stronger bounds for homogeneous non-commutative settings. small-depth circuits. In the small-depth homogeneous noncommutative case, we prove a lower bound of n(d1/Delta/2O(Delta)), which yields non-FPT bounds for depths up to o(root logd). In comparison, our previous bound works in the harder commutative set-multilinear setting, but only up to depths o( log logd). Moreover, our lower

关键词： algebraic complexity Set-multilinear formulas Non-commutative formulas Iterated Matrix Multiplication

来源：评论

学校读者我要写书评

暂无评论

Limits on the Universal Method for Matrix Multiplication

引用

THEORY OF COMPUTING 2021年 17卷 1-30页

作者： Alman, Josh Columbia Univ Dept Comp Sci New York NY 10027 USA

We prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams (FOCS'18) recently defined the Universal Method, which generalizes all the known approaches, including Strassen's Laser Method (J. reine angew. Math., 1987) and Cohn and Umans's Group Theoretic Method (FOCS'03). We prove concrete lower bounds on the algorithms one can design by applying the Universal Method to many different tensors. Our proofs use new tools to give upper bounds on the asymptotic slice rank of a wide range of tensors. Our main result is that the Universal Method applied to any Coppersmith-Winograd tensor CWq cannot yield a bound on omega, the exponent of matrix multiplication, better than 2:16805. It was previously known (Alman and Vassilevska Williams, FOCS'18) that the weaker "Galactic Method" applied to CWq could not achieve an exponent of 2. We also study the Laser Method (which is a special case of the Universal Method) and prove that it is "complete" for matrix multiplication algorithms: when it applies to a tensor T, it achieves omega = 2 if and only if it is possible for the Universal Method applied to T to achieve omega = 2. Hence, the Laser Method, which was originally used as an algorithmic tool, can also be seen as a lower-bound tool for a large class of algorithms. For example, in their landmark paper, Coppersmith and Winograd (J. Symbolic Computation, 1990) achieved a bound of omega <= 2.376, by applying the Laser Method to CWq. By our result, the fact that they did not achieve omega = 2 implies a lower bound on the Universal Method applied to CWq.

关键词： matrix multiplication algebraic complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：