Gotowe bibliografie tematyczne / Algebraic Branching Programs

Spis treści

  1. Artykuły w czasopismach
  2. Rozprawy doktorskie
  3. Części książek
  4. Streszczenia konferencji

Gotowa bibliografia na temat „Algebraic Branching Programs”

Autor: Grafiati
Data publikacji: 6 września 2023
Data aktualizacji: 31 lipca 2025

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Zobacz listy aktualnych artykułów, książek, rozpraw, streszczeń i innych źródeł naukowych na temat „Algebraic Branching Programs”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Artykuły w czasopismach na temat "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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.
Więcej źródeł

Rozprawy doktorskie na temat "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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Streszczenie:
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
Style APA, Harvard, Vancouver, ISO itp.

Części książek na temat "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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.

Streszczenia konferencji na temat "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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
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.

Pełny tekst źródła
Style APA, Harvard, Vancouver, ISO itp.
Możesz być także zainteresowany rozszerzonymi bibliografiami na temat „Algebraic Branching Programs” dla poszczególnych typów źródeł:
Artykuły w czasopismach
Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!

Do bibliografii