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

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

Wybierz rodzaj źródła:

Sprawdź 16 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 i Sébastien Tavenas. "Reconstruction of Full Rank Algebraic Branching Programs". ACM Transactions on Computation Theory 11, nr 1 (16.01.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, nr 3 (8.06.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, i B. V. Raghavendra Rao. "On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models". Fundamenta Informaticae 177, nr 1 (18.12.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 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.
Style APA, Harvard, Vancouver, ISO itp.
4

Allender, Eric, i Fengming Wang. "On the power of algebraic branching programs of width two". computational complexity 25, nr 1 (5.11.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 i Ben Lee Volk. "Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs". ACM Transactions on Computation Theory 10, nr 1 (30.01.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 i Chandan Saha. "Average-case linear matrix factorization and reconstruction of low width algebraic branching programs". computational complexity 28, nr 4 (18.07.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 i Chandan Saha. "Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits". ACM Transactions on Computation Theory 12, nr 1 (25.02.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 i Aditya Varre. "Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes". ACM Transactions on Computation Theory 13, nr 4 (31.12.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 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.
Style APA, Harvard, Vancouver, ISO itp.
9

STRAUBING, HOWARD. "CONSTANT-DEPTH PERIODIC CIRCUITS". International Journal of Algebra and Computation 01, nr 01 (marzec 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 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.
Style APA, Harvard, Vancouver, ISO itp.
10

Šíma, Jiří, i Stanislav Žák. "A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3". Fundamenta Informaticae 184, nr 4 (7.03.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 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.
Style APA, Harvard, Vancouver, ISO itp.
11

Chikalov, Igor. "On Average Time Complexity of Decision Trees and Branching Programs". Fundamenta Informaticae 39, nr 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.
12

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

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

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

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

Beimel, Amos. "Lower Bounds for Monotone Span Programs". BRICS Report Series 1, nr 46 (15.12.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-cliques.
Style APA, Harvard, Vancouver, ISO itp.
15

Hrushovski, Ehud, Joël Ouaknine, Amaury Pouly i James Worrell. "On Strongest Algebraic Program Invariants". Journal of the ACM, 8.08.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 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.
Style APA, Harvard, Vancouver, ISO itp.
16

Dutta, Pranjal, Nitin Saxena i Amit Sinhababu. "Discovering the roots: Uniform closure results for algebraic classes under factoring". Journal of the ACM, 23.02.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 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).
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