Log in

Relevant bibliographies by topics / Algebraic Branching Programs / Journal articles

To see the other types of publications on this topic, follow the link: Algebraic Branching Programs.

Journal articles on the topic 'Algebraic Branching Programs'

Author: Grafiati

Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 16 journal articles for your research on the topic 'Algebraic Branching Programs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Kayal, Neeraj, Vineet Nair, Chandan Saha, and Sébastien Tavenas. "Reconstruction of Full Rank Algebraic Branching Programs." ACM Transactions on Computation Theory 11, no. 1 (January 16, 2019): 1–56. http://dx.doi.org/10.1145/3282427.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Kumar, Mrinal. "A quadratic lower bound for homogeneous algebraic branching programs." computational complexity 28, no. 3 (June 8, 2019): 409–35. http://dx.doi.org/10.1007/s00037-019-00186-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Ghosal, Purnata, and B. V. Raghavendra Rao. "On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models." Fundamenta Informaticae 177, no. 1 (December 18, 2020): 69–93. http://dx.doi.org/10.3233/fi-2020-1980.

Full text

Abstract:

We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., nΩ(t(k)) lower bound for some function t of k) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g(k)nO(1) for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.

APA, Harvard, Vancouver, ISO, and other styles

4

Allender, Eric, and Fengming Wang. "On the power of algebraic branching programs of width two." computational complexity 25, no. 1 (November 5, 2015): 217–53. http://dx.doi.org/10.1007/s00037-015-0114-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Anderson, Matthew, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. "Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs." ACM Transactions on Computation Theory 10, no. 1 (January 30, 2018): 1–30. http://dx.doi.org/10.1145/3170709.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Kayal, Neeraj, Vineet Nair, and Chandan Saha. "Average-case linear matrix factorization and reconstruction of low width algebraic branching programs." computational complexity 28, no. 4 (July 18, 2019): 749–828. http://dx.doi.org/10.1007/s00037-019-00189-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Kayal, Neeraj, Vineet Nair, and Chandan Saha. "Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits." ACM Transactions on Computation Theory 12, no. 1 (February 25, 2020): 1–27. http://dx.doi.org/10.1145/3369928.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Chaugule, Prasad, Nutan Limaye, and Aditya Varre. "Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–26. http://dx.doi.org/10.1145/3470858.

Full text

Abstract:

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2018). We consider three different variants of graph homomorphisms, namely injective homomorphisms , directed homomorphisms , and injective directed homomorphisms , and obtain polynomial families complete for VF, VBP, VP, and VNP under each one of these. The polynomial families have the following properties: • The polynomial families complete for VF, VBP, and VP are model independent, i.e., they do not use a particular instance of a formula, algebraic branching programs, or circuit for characterising VF, VBP, or VP, respectively. • All the polynomial families are hard under p -projections.

APA, Harvard, Vancouver, ISO, and other styles

9

STRAUBING, HOWARD. "CONSTANT-DEPTH PERIODIC CIRCUITS." International Journal of Algebra and Computation 01, no. 01 (March 1991): 49–87. http://dx.doi.org/10.1142/s0218196791000043.

Full text

Abstract:

This paper is devoted to the languages accepted by constant-depth, polynomial-size families of circuits in which every circuit element computes the sum of its input bits modulo a fixed period q. It has been conjectured that such a circuit family cannot compute the AND function of n inputs. Here it is shown that such circuit families are equivalent in power to polynomial-length programs over finite solvable groups; in particular, the conjecture implies that Barrington's result on the computational power of branching programs over nonsolvable groups cannot be extended to solvable groups. It is also shown that polynomial-length programs over dihedral groups cannot compute the AND function. Furthermore, it is shown that the conjecture is equivalent to a characterization, in terms of finite semigroups and formal logic, of the regular languages accepted by such circuit families. There is, moreover, considerable independent evidence for this characterization. This last result is established using new theorems, of independent interest, concerning the algebraic structure of finite categories.

APA, Harvard, Vancouver, ISO, and other styles

10

Šíma, Jiří, and Stanislav Žák. "A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3." Fundamenta Informaticae 184, no. 4 (March 7, 2022): 307–54. http://dx.doi.org/10.3233/fi-2021-2101.

Full text

Abstract:

Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental issue of derandomizing space-bounded computations. Such constructions have been known only in the case of width 2 and in very restricted cases of bounded width. In this paper, we characterize the hitting sets for read-once branching programs of width 3 by a so-called richness condition. Namely, we show that such sets hit the class of read-once conjunctions of DNF and CNF (i.e. the weak richness). Moreover, we prove that any rich set extended with all strings within Hamming distance of 3 is a hitting set for read-once branching programs of width 3. Then, we show that any almost O(log n)-wise independent set satisfies the richness condition. By using such a set due to Alon et al. (1992) our result provides an explicit polynomial-time construction of a hitting set for read-once branching programs of width 3 with acceptance probability ɛ > 5/6. We announced this result at conferences more than ten years ago, including only proof sketches, which motivated a number of subsequent results on pseudorandom generators for restricted read-once branching programs. This paper contains our original detailed proof that has not been published yet.

APA, Harvard, Vancouver, ISO, and other styles

11

Chikalov, Igor. "On Average Time Complexity of Decision Trees and Branching Programs." Fundamenta Informaticae 39, no. 4 (1999): 337–57. http://dx.doi.org/10.3233/fi-1999-39401.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

"On Algebraic Branching Programs of Small Width." Journal of the ACM 65, no. 5 (September 18, 2018): 1–29. http://dx.doi.org/10.1145/3209663.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Chatterjee, Prerona, Mrinal Kumar, Adrian She, and Ben Lee Volk. "Quadratic Lower Bounds for Algebraic Branching Programs and Formulas." computational complexity 31, no. 2 (July 5, 2022). http://dx.doi.org/10.1007/s00037-022-00223-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Beimel, Amos. "Lower Bounds for Monotone Span Programs." BRICS Report Series 1, no. 46 (December 15, 1994). http://dx.doi.org/10.7146/brics.v1i46.21596.

Full text

Abstract:

The model of span programs is a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for contact schemes, symmetric branching programs and for formula size. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. The main result proved here yields quadratic lower bounds for the size of monotone span programs, improving on the largest previously known bounds for explicit functions. The bound is asymptotically tight for the function corresponding to a class of 4-cliques.

APA, Harvard, Vancouver, ISO, and other styles

15

Hrushovski, Ehud, Joël Ouaknine, Amaury Pouly, and James Worrell. "On Strongest Algebraic Program Invariants." Journal of the ACM, August 8, 2023. http://dx.doi.org/10.1145/3614319.

Full text

Abstract:

A polynomial program is one in which all assignments are given by polynomial expressions and in which all branching is nondeterministic (as opposed to conditional). Given such a program, an algebraic invariant is one that is defined by polynomial equations over the program variables at each program location. Müller-Olm and Seidl have posed the question of whether one can compute the strongest algebraic invariant of a given polynomial program. In this paper we show that, while strongest algebraic invariants are not computable in general, they can be computed in the special case of affine programs, that is, programs with exclusively linear assignments. For the latter result our main tool is an algebraic result of independent interest: given a finite set of rational square matrices of the same dimension, we show how to compute the Zariski closure of the semigroup that they generate.

APA, Harvard, Vancouver, ISO, and other styles

16

Dutta, Pranjal, Nitin Saxena, and Amit Sinhababu. "Discovering the roots: Uniform closure results for algebraic classes under factoring." Journal of the ACM, February 23, 2022. http://dx.doi.org/10.1145/3510359.

Full text

Abstract:

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the number of roots r is small but, the multiplicities are exponentially large. Our method sets up a linear system in r unknowns and iteratively builds the roots as formal power series. For an algebraic circuit f ( x 1 , …, x n ) of size s , we prove that each factor has size at most a polynomial in: s and the degree of the squarefree part of f . Consequently, if f 1 is a 2 Ω ( n ) -hard polynomial then any nonzero multiple \prod _{i} f_i^{e_i} is equally hard for arbitrary positive e i ’s, assuming that \sum _i\deg (f_i) is at most 2 O ( n ) . It is an old open question whether the class of poly( n )-sized formulas (respectively algebraic branching programs) is closed under factoring. We show that given a polynomial f of degree n O (1) and formula (respectively ABP) size n O (log n ) we can find a similar size formula (respectively ABP) factor in randomized poly( n log n )-time. Consequently, if determinant requires n Ω (log n ) size formula, then the same can be said about any of its nonzero multiples. In all our proofs, we exploit the following property of multivariate polynomial factorization. Under a random linear transformation τ , the polynomial f(\tau \overline{x}) completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. This with allRootsNI are the techniques that help us make progress towards the old open problems; supplementing the vast body of classical results and concepts in algebraic circuit factorization (eg. Zassenhaus, J.NT 1969; Kaltofen, STOC 1985-7 & Bürgisser, FOCS 2001).

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!