Subjects -> MATHEMATICS (Total: 1013 journals)     - APPLIED MATHEMATICS (92 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (714 journals)    - MATHEMATICS (GENERAL) (45 journals)    - NUMERICAL ANALYSIS (26 journals)    - PROBABILITIES AND MATH STATISTICS (113 journals) MATHEMATICS (714 journals)                  1 2 3 4 | Last

1 2 3 4 | Last

Similar Journals
 Computational ComplexityJournal Prestige (SJR): 0.381 Citation Impact (citeScore): 1Number of Followers: 5      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1420-8954 - ISSN (Online) 1016-3328 Published by Springer-Verlag  [2467 journals]
• On sets of linear forms of maximal complexity

Abstract: Abstract We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n – 1) additions.
PubDate: 2022-11-29

• Quantum versus Randomized Communication Complexity, with Efficient Players

Abstract: Abstract We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N, such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where at the beginning of the protocol Alice and Bob also have polylog(N) entangled EPR pairs). Any classical randomized protocol for f, with any number of rounds, has communication complexity at least $$\tilde{\Omega}\left(N^{1/4}\right)$$ . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog(N) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of $$\Omega\left(N^{1/2}\right)$$ in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
PubDate: 2022-10-28

• On Hitting-Set Generators for Polynomials that Vanish Rarely

Abstract: Abstract The problem of constructing pseudorandom generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: Is it easier to construct pseudorandom generators, or even hitting-set generators, for polynomials $$p:\mathbb{F}^n\rightarrow\mathbb{F}$$ of degree d if we are guaranteed that the polynomial vanishes on at most an $$\varepsilon > 0$$ fraction of its inputs' We will specifically be interested in tiny values of $$\varepsilon\ll d/ F$$ . This question was first considered by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for a particular application, and another specific setting was later studied by the third author (CCC 2017). In this work, our main interest is a systematic study of the relaxed problem,in its general form, and we prove results that significantly improve and extend the two previously known results. Our contributions are of two types: $$\circ$$ Over fields of size $$2\le \mathbb{F} \le\mathrm{poly}(n)$$ we show that the seed length of any hitting-set generator for polynomials of degree $$d\le n^{.49}$$ that vanish on at most $$\varepsilon= \mathbb{F} ^{-t}$$ of their inputs is at least $$\Omega\left((d/t)\cdot\log(n)\right)$$ . $$\circ$$ Over $$\mathbb{F}_2$$ , we show that there exists a (non-explicit) hitting-set generator for polynomials of degree $$d\le n^{.99}$$ that vanish on at most $$\varepsilon= \mathbb{F} ^{-t}$$ of their inputs with seed length $$O\left((d-t)\cdot\log(n)\right)$$ . We also show a polynomial-time computable hitting-set generator with seed length $$O\left( (d-t)\cdot\left(2^{d-t}+\log(n)\right) \right)$$ . In addition, we prove that the problem we study is closely related to the following question: “Does there exist a small set $$S\subseteq\mathbb{F}^n$$ whose degree-d closure is very large'”, where the degree-d closure of S is the variety induced by the set of degree-d polynomials that vanish on S.
PubDate: 2022-10-22

• Improved Hitting Set for Orbit of ROABPs

Abstract: Abstract The orbit of an n-variate polynomial $$f({\rm x})$$ over a field $$\mathbb{F}$$ is the set $$\{f(A{\rm x} + {\rm b})\,\mid\, A\in{\rm GL}(n, \mathbb{F})\mbox{ and }{\rm b}\in \mathbb{F}^n\}$$ , and the orbit of a polynomial class is the union of orbits of the polynomials in it. In this paper, we give improved constructions of hitting sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than $$d$$ , we construct a hitting set of size $$(ndw)^{O(w^2\log n\cdot \min\{w^2, d\log w\})}$$ for the orbit of ROABPs in unknown variable order where $$d$$ is the individual degree and $$w$$ is the width of ROABPs. We also give a hitting set of size $$(ndw)^{O(\min\{w^2,d\log w\})}$$ for the orbit of polynomials computed by width-w ROABPs in any variable order. Our hitting sets improve upon the results of Saha & Thankey (2021) who gave an $$(ndw)^{O(d\log w)}$$ size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and $$(nw)^{O(w^6\log n)}$$ size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance $$d>n$$ , was asked as an open problem by Saha & Thankey (2021) and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for polynomials over vector spaces, and they strengthen some previously known low-support-based rank concentration results shown in Forbes et al. (2013). These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets.
PubDate: 2022-10-12

• The Complexity of Finding Fair Independent Sets in Cycles

Abstract: Abstract Let G be a cycle graph and let $$V_1,\ldots,V_m$$ be a partition of its vertex set into m sets. An independent set S of G is said to fairly represent the partition if $$S \cap V_i \geq \frac{1}{2} \cdot V_i -1$$ for all $$i \in [m]$$ . It is known that for every cycle and every partition of its vertex set, there exists an independent set that fairly represents the partition (Aharoni et al. 2017). We prove that the problem of finding such an independent set is PPA-complete. As an application, we show that the problem of finding a monochromatic edge in a Schrijver graph, given a succinct representation of a coloring that uses fewer colors than its chromatic number, is PPA-complete as well. The work is motivated by the computational aspects of the cycle plus triangles' problem and of its extensions.
PubDate: 2022-10-11

• Quantum generalizations of the polynomial hierarchy with applications to
QMA(2)

Abstract: Abstract The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, $$\rm{QCPH}$$ , uses classical proofs, and the second, $$\rm{QPH}$$ , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $$\rm{Q\Sigma_3}$$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $$\rm{QMA(2)}$$ , the variant of Quantum Merlin-Arthur ( $$\rm{QMA}$$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $$\rm{QCPH = QPH}$$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs equivalent''), then QMA(2) is in the counting hierarchy (specifically, in $$Po^{pp^{pp}}$$ ). Second, because $$\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$$ , $$\rm{QMA(2)}$$ is strictly contained in NEXP unless $$\rm{QMA(2)}=\rm{Q\Sigma_3}$$ (i.e., alternating quantifiers do not help in the presence of `unentanglement'').
PubDate: 2022-09-20
DOI: 10.1007/s00037-022-00231-8

• A Lower Bound on Determinantal Complexity

Abstract: Abstract The determinantal complexity of a polynomial $$P \in \mathbb{F}[x_1, \ldots, x_n]$$ over a field $$\mathbb{F}$$ is the dimension of the smallest matrix M whose entries are affine functions in $$\mathbb{F}[x_1, \ldots, x_n]$$ such that $$P = {\rm Det}(M)$$ . We prove that the determinantal complexity of the polynomial $$\sum_{i = 1}^n x_i^n$$ is at least $$1.5n - 3$$ . For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long-standing open problem to prove a lower bound which is super linear in $$\max\{n,d\}$$ . Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than $$\max\{n,d\}$$ , and improves upon the prior best bound of $$n + 1$$ , proved by Alper et al. (2017) for the same polynomial.
PubDate: 2022-09-19
DOI: 10.1007/s00037-022-00228-3

• Zeros and approximations of Holant polynomials on the complex plane

Abstract: We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
PubDate: 2022-07-27
DOI: 10.1007/s00037-022-00226-5

• A cost-scaling algorithm for computing the degree of determinants

Abstract: Abstract In this paper, we address computation of the degree $$\deg {\rm Det} A$$ of Dieudonné determinant $${\rm Det} A$$ of \begin{aligned} A = \sum_{k=1}^m A_k x_k t^{c_k}, \end{aligned} where $$A_k$$ are $$n \times n$$ matrices over a field $$\mathbb{K}$$ , $$x_k$$ are noncommutative variables, t is a variable commuting with $$x_k$$ , $$c_k$$ are integers, and the degree is considered for t. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that $$\deg {\rm Det} A$$ is obtained by a discrete convex optimization on a Euclidean building (Hirai 2019). We extend this framework by incorporating a cost-scaling technique and show that $$\deg {\rm Det} A$$ can be computed in time polynomial of $$n,m,\log_2 C$$ , where $$C:= \max_k c_k$$ . We give a polyhedral interpretation of $$\deg {\rm Det}$$ , which says that $$\deg {\rm Det}$$ A is given by linear optimization over an integral polytope with respect to objective vector $$c = (c_k)$$ . Based on it, we show that our algorithm becomes a strongly polynomial one. We also apply our result to an algebraic combinatorial optimization problem arising from a symbolic matrix having $$2 \times 2$$ -submatrix structure.
PubDate: 2022-07-23
DOI: 10.1007/s00037-022-00227-4

• Disjointness through the Lens of Vapnik–Chervonenkis Dimension:
Sparsity and Beyond

Abstract: Abstract The disjointness problem—where Alice and Bob are given two subsets of $$\{1, \dots, n\}$$ and they have to check if their sets intersect—is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $$\Theta(n)$$ , it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik—Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by d, we analyze how large can the deterministic and randomized communication complexities be, as a function of d and n. The d-sparse set disjointness problem, where the sets have size at most d, is one such set system with VC dimension d. The deterministic and the randomized communication complexities of the d-sparse set disjointness problem have been well studied and are known to be $$\Theta \left( d \log \left({n}/{d}\right)\right)$$ and $$\Theta(d)$$ , respectively, in the multi-round communication setting. In this paper, we address the question of whether the randomized communication complexity of the disjointness problem is always upper bounded by a function of the VC dimension of the set system, and does there always exist a gap between the deterministic and randomized communication complexities of the disjointness problem for set systems with small VC dimension. We construct two natural set systems of VC dimension d, motivated from geometry. Using these set systems, we show that the deterministic and randomized communication complexity can be $$\widetilde{\Theta}\left(d\log \left( n/d \right)\right)$$ for set systems of VC dimension d and this matches the deterministic upper bound for all set systems of VC dimension d. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exist set systems of VC dimension d such that both deterministic and randomized (one-way and multi-round) complexities for the set intersection problem can be as high as $$\Theta\left( d\log \left( n/d \right) \right)$$ .
PubDate: 2022-07-05
DOI: 10.1007/s00037-022-00225-6

• Quadratic Lower Bounds for Algebraic Branching Programs and Formulas

Abstract: Abstract We show that any Algebraic Branching Program (ABP) computing the polynomial $$\sum _{i = 1}^n x_i^n$$ has at least $$\Omega (n^2)$$ vertices. This improves upon the lower bound of $$\Omega (n\log n)$$ , which follows from the classical result of Strassen (1973a) and Baur & Strassen (1983), and extends the results in Kumar (2019), which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction, which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial $$\sum _{i=1}^n x_i^n$$ can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial $$\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})$$ , for a structured “error polynomial” $$\varepsilon ({\bf x})$$ . To complete the proof, we then observe that the lower bound in Kumar (2019) is robust enough and continues to hold for all polynomials $$\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})$$ , where $$\varepsilon ({\bf x})$$ has the appropriate structure. We also use our ideas to show an $$\Omega (n^2)$$ lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree 0.1n on n variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of $$\Omega (n^2/\log n)$$ Kalorkoti (1985); Nechiporuk (1966); Shpilka & Yehudayoff (2010). Interestingly, this lower bound is asymptotically better than $$n^2/\log n$$ , the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth-3 formula) of size $$O(n^2)$$ . Prior to this work, Ben-Or’s construction was known to be optimal only for algebraic formulas of depth-3 (Shpilka & Wigderson 2001).
PubDate: 2022-07-05
DOI: 10.1007/s00037-022-00223-8

• Improved bounds on the AN-complexity of $$O(1)$$ O ( 1 ) -linear functions

Abstract: Abstract We consider arithmetic circuits with arbitrary gates for computing Boolean functions that are represented by low-degree polynomials over GF(2). An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number. This model and the corresponding complexity measure, called AN-complexity, were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), and it is meaningful only for low-degree polynomials (where the arity of a gate is not due to the degree of the polynomial that the gate computes but rather to the number of variables in it). The AN-complexity of a function yields an upper bound on the size of depth-three Boolean circuits for computing the function. Specifically, the depth-three size of Boolean circuits is at most exponential in the AN-complexity of the function. Hence, proving linear lower bounds on the AN-complexity of explicit O(1)-linear functions is an essential step toward proving that depth-three Boolean circuits for these functions require exponential size. In this work, we present explicit O(1)-linear functions that require depth-two arithmetic circuits of almost linear AN-complexity. Specifically, for every $$\epsilon > 0$$ , we show an explicit poly $$({1/ \epsilon})$$ -linear function $$f:\{0,1\}^{\mathrm{poly} (1/\epsilon)\cdot n}\to \{0,1\}$$ such that any depth-two arithmetic circuit that computes f must use gates of arity at least $$n^{1-\epsilon}$$ . In particular, for every $$\epsilon > 0$$ and $$t=O(1/\epsilon^2)$$ , the $$\Omega(n^{1-\epsilon})$$ lower bound holds also for the t-linear function \begin{aligned}f(x^{(1)},x^{(2)},...,x^{(t)}) = \sum_{i_1,...,i_{t-1}\in[n]} \left(\prod_{j\in[t-1]} x^{(j)}_{i_{j}}\right) \cdot x^{(t)}_{{i_1+i_2+\cdots+i_{t-1}}} \end{aligned} This improves over a corresponding lower bound of $$\tilde \Omega(n^{2/3})$$ that was known for an explicit trilinear function (Goldreich and Tal, Computational Complexity, 2018), but leaves open the problem of showing similar AN-complexity lower bounds for arithmetic circuits of larger depth. A key aspect in our proof is considering many (extremely skewed) random restrictions, and contrasting the sum of the values of the original function and the circuit (which supposedly computes it) taken over a (carefully chosen) subset of these random restrictions. We show that if the original circuit has too low AN-complexity, then these two sums cannot be equal, which yields a contradiction.
PubDate: 2022-06-23
DOI: 10.1007/s00037-022-00224-7

• A quasi-linear irreducibility test in $$\mathbb{K}[[x]][y]$$ K [ [ x ] ] [
y ]

Abstract: Abstract We provide an irreducibility test in the ring $$\mathbb{K}[[x]][y]$$ whose complexity is quasi-linear with respect to the discriminant valuation, assuming the input polynomial $$F$$ is square-free and $$\mathbb{K}$$ is a perfect field of characteristic not dividing $$\deg(F)$$ . The algorithm uses the theory of approximate roots and may be seen as a generalisation of Abhyankar's irreducibility criterion to the case of non-algebraically closed residue fields.
PubDate: 2022-06-11
DOI: 10.1007/s00037-022-00221-w

• Computing zero-dimensional tropical varieties via projections

Abstract: Abstract We present an algorithm for computing zero-dimensional tropical varieties using projections. Our main tools are fast monomial transforms of triangular sets. Given a Gröbner basis, we prove that our algorithm requires only a polynomial number of arithmetic operations, and, for ideals in shape position, we show that its timings compare well against univariate factorization and backsubstitution. We conclude that the complexity of computing positive-dimensional tropical varieties via a traversal of the Gröbner complex is dominated by the complexity of the Gröbner walk.
PubDate: 2022-05-20
DOI: 10.1007/s00037-022-00222-9

• Expander-Based Cryptography Meets Natural Proofs

Abstract: Abstract We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich’s pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander’s neighbor function and/or of the local predicate. Our two key conceptual contributions are: We put forward the possibility that the choice of expander matters in expander-based cryptography. In particular, using expanders whose neighbor function has low circuit complexity might compromise the security of Goldreich’s PRG and OWF in certain settings. We show that the security of Goldreich’s PRG and OWF over arbitrary expanders is closely related to two other long-standing problems: The existence of unbalanced lossless expanders with low-complexity neighbor function, and limitations on circuit lower bounds (i.e., natural proofs). In particular, our results further motivate the investigation of affine/local unbalanced lossless expanders and of average-case lower bounds against DNF-XOR circuits. We prove two types of technical results. First, in the regime of quasipolynomial stretch (in which the output length of the PRG and the running time of the distinguisher are quasipolynomial in the seed length) we unconditionally break Goldreich’s PRG, when instantiated with a specific expander whose existence we prove, and for a class of predicates that match the parameters of the currently-best “hard” candidates. Secondly, conditioned on the existence of expanders whose neighbor functions have extremely low circuit complexity, we present attacks on Goldreich’s PRG in the regime of polynomial stretch. As one corollary, conditioned on the existence of the foregoing expanders, we show that either the parameters of natural properties for several constant-depth circuit classes cannot be improved, even mildly; or Goldreich’s PRG is insecure in the regime of a large polynomial stretch for some expander graphs, regardless of the predicate used.
PubDate: 2022-03-16
DOI: 10.1007/s00037-022-00220-x

• Amplification with One NP Oracle Query

Abstract: Abstract We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, onesided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our inclusions are tight for relativizing techniques.
PubDate: 2022-02-05
DOI: 10.1007/s00037-021-00219-w

• The complexity of approximating the complex-valued Potts model

Abstract: Abstract We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q $$\geq$$ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.
PubDate: 2022-02-03
DOI: 10.1007/s00037-021-00218-x

• Rank and border rank of Kronecker powers of tensors and Strassen's laser
method

Abstract: Abstract We prove that the border rank of the Kronecker square of the little Coppersmith–Winograd tensor $$T_{cw,q}$$ is the square of its border rank for $$q > 2$$ and that the border rank of its Kronecker cube is the cube of its border rank for $$q > 4$$ . This answers questions raised implicitly by Coppersmith & Winograd (1990, §11) and explicitly by Bläser (2013, Problem 9.8) and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith–Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith–Winograd tensor, $$T_{skewcw,q}$$ . For $$q = 2$$ , the Kronecker square of this tensor coincides with the $$3\times 3$$ determinant polynomial, $$\det_{3} \in \mathbb{C}^{9} \otimes \mathbb{C}^{9} \otimes \mathbb{C}^{9}$$ , regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of $$\det_3$$ , exhibiting a strict submultiplicative behaviour for $$T_{skewcw,2}$$ which is promising for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in $$\mathbb{C}^{3} \otimes \mathbb{C}^{3} \otimes \mathbb{C}^{3}$$ .
PubDate: 2021-12-18
DOI: 10.1007/s00037-021-00217-y

• Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations
of Tseitin Formulas for All Constant-Degree Graphs

PubDate: 2021-11-17
DOI: 10.1007/s00037-021-00216-z

• Factorization of Polynomials Given by Arithmetic Branching Programs

Abstract: Abstract Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly $$(s^{ {\rm \log} s})$$ .
PubDate: 2021-10-15
DOI: 10.1007/s00037-021-00215-0

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762