Relevant bibliographies by topics / Algebraic Branching Programs

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Algebraic Branching Programs'

Author: Grafiati
Published: 6 September 2023
Last updated: 31 July 2025

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Algebraic Branching Programs"

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 (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 (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 (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 fou
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 (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 (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 (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 (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 (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 V
APA, Harvard, Vancouver, ISO, and other styles
9

STRAUBING, HOWARD. "CONSTANT-DEPTH PERIODIC CIRCUITS." International Journal of Algebra and Computation 01, no. 01 (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 a
APA, Harvard, Vancouver, ISO, and other styles
10

Ait El Manssour, Rida, George Kenison, Mahsa Shirmohammadi, and Anton Varonka. "Simple Linear Loops: Algebraic Invariants and Applications." Proceedings of the ACM on Programming Languages 9, POPL (2025): 745–71. https://doi.org/10.1145/3704862.

Full text
Abstract:
The automatic generation of loop invariants is a fundamental challenge in software verification. While this task is undecidable in general, it is decidable for certain restricted classes of programs. This work focuses on invariant generation for (branching-free) loops with a single linear update. Our primary contribution is a polynomial-space algorithm that computes the strongest algebraic invariant for simple linear loops, generating all polynomial equations that hold among program variables across all reachable states. The key to achieving our complexity bounds lies in mitigating the blow-up
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Algebraic Branching Programs"

1

Forbes, Michael Andrew. "Polynomial identity testing of read-once oblivious algebraic branching programs." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/89843.

Full text
Abstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>Cataloged from student-submitted PDF version of thesis.<br>Includes bibliographical references (pages 209-220).<br>We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an effic
APA, Harvard, Vancouver, ISO, and other styles
2

Nair, Vineet. "Expanders in Arithmetic Circuit Lower Bound : Towards a Separation Between ROABPs and Multilinear Depth 3 Circuits." Thesis, 2015. https://etd.iisc.ac.in/handle/2005/4811.

Full text
Abstract:
Consider the problem of Polynomial Identity Testing(PIT): we are given an arithmetic circuit computing a multivariate polynomial over some eld and we have to determine whether that polynomial is identically zero or not. PIT is a fundamental problem and has applications in both algorithms and complexity theory. In this work, our aim is to study PIT for the model of multilinear depth three circuits for which no deterministic polynomial time identity test is known. An nO(log n) time blackbox PIT for set-multilinear depth three circuits (a special kind of multilinear depth three circuits) i
APA, Harvard, Vancouver, ISO, and other styles
3

Nair, Vineet. "On Learning and Lower Bound Problems Related to the Iterated Matrix Multiplication Polynomial." Thesis, 2020. https://etd.iisc.ac.in/handle/2005/4597.

Full text
Abstract:
The iterated matrix multiplication polynomial (IMM) of width w and length d is the 1x1 entry in the product of d square matrices of size w. The w^2d entries in the d matrices are distinct variables. In this thesis, we study certain learning and lower bound problems related to IMM. Our first work gives a polynomial time randomized algorithm for equivalence testing of IMM. At its core, the equivalence testing algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM and the layer spaces
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Algebraic Branching Programs"

1

Malod, Guillaume. "Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes." In Fundamentals of Computation Theory. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22953-4_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Allender, Eric, and Fengming Wang. "On the Power of Algebraic Branching Programs of Width Two." In Automata, Languages and Programming. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22006-7_62.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bhargav, C. S., Prateek Dwivedi, and Nitin Saxena. "Lower Bounds for the Sum of Small-Size Algebraic Branching Programs." In Lecture Notes in Computer Science. Springer Nature Singapore, 2024. http://dx.doi.org/10.1007/978-981-97-2340-9_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Algebraic Branching Programs"

1

Forbes, Michael A., Ramprasad Saptharishi, and Amir Shpilka. "Hitting sets for multilinear read-once algebraic branching programs, in any order." In STOC '14: Symposium on Theory of Computing. ACM, 2014. http://dx.doi.org/10.1145/2591796.2591816.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Forbes, Michael A., and Amir Shpilka. "Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs." In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2013. http://dx.doi.org/10.1109/focs.2013.34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Algebraic Branching Programs' for particular source types:
Journal articles
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!

To the bibliography