Gotowe bibliografie tematyczne / Algebraic Branching Programs / Artykuły w czasopismach
Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Algebraic Branching Programs.

Artykuły w czasopismach 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:

Sprawdź 20 najlepszych artykułów w czasopismach 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.

Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.

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.
11

Ší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 (2022): 307–54. http://dx.doi.org/10.3233/fi-2021-2101.

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

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.

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

Chatterjee, Abhranil, Mrinal Kumar, and Ben Lee Volk. "Determinants vs. Algebraic Branching Programs." computational complexity 33, no. 2 (2024). http://dx.doi.org/10.1007/s00037-024-00258-z.

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

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

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

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

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

Bhargav, C. S., Prateek Dwivedi, and Nitin Saxena. "Lower Bounds for the Sum of Small-size Algebraic Branching Programs." Theoretical Computer Science, April 2025, 115214. https://doi.org/10.1016/j.tcs.2025.115214.

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

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

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

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.

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

Zilberstein, Noam. "Outcome Logic: A Unified Approach to the Metatheory of Program Logics with Branching Effects." ACM Transactions on Programming Languages and Systems, June 6, 2025. https://doi.org/10.1145/3743131.

Pełny tekst źródła
Streszczenie:
Starting with Hoare Logic over 50 years ago, numerous program logics have been devised to reason about the different kinds of programs encountered in the real world. This includes reasoning about computational effects, particularly those effects that cause the program execution to branch into multiple paths due to, e.g., nondeterministic or probabilistic choice. Outcome Logic reimagines Hoare Logic with branching at its core, using an algebraic representation of choice to capture programs that branch into many outcomes. In this article, we give a comprehensive account of the Outcome Logic meta
Style APA, Harvard, Vancouver, ISO itp.
20

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.

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