Готові списки джерел за темами / Algebraic Branching Programs / Статті в журналах

Статті в журналах з теми "Algebraic Branching Programs"

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Algebraic Branching Programs.
Автор: Grafiati
Опубліковано: 6 вересня 2023

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-16 статей у журналах для дослідження на тему "Algebraic Branching Programs".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
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.

Повний текст джерела
Анотація:
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 та ін.
Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!

До бібліографії