Acceder

Bibliografías temáticas / Algebraic Branching Programs / Artículos de revistas

Artículos de revistas sobre el tema "Algebraic Branching Programs"

Siga este enlace para ver otros tipos de publicaciones sobre el tema: Algebraic Branching Programs.

Autor: Grafiati

Publicado: 6 de septiembre de 2023

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte los 16 mejores artículos de revistas para su investigación sobre el tema "Algebraic Branching Programs".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Explore artículos de revistas sobre una amplia variedad de disciplinas y organice su bibliografía correctamente.

1

Kayal, Neeraj, Vineet Nair, Chandan Saha y Sébastien Tavenas. "Reconstruction of Full Rank Algebraic Branching Programs". ACM Transactions on Computation Theory 11, n.º 1 (16 de enero de 2019): 1–56. http://dx.doi.org/10.1145/3282427.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

Kumar, Mrinal. "A quadratic lower bound for homogeneous algebraic branching programs". computational complexity 28, n.º 3 (8 de junio de 2019): 409–35. http://dx.doi.org/10.1007/s00037-019-00186-3.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

Ghosal, Purnata y B. V. Raghavendra Rao. "On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models". Fundamenta Informaticae 177, n.º 1 (18 de diciembre de 2020): 69–93. http://dx.doi.org/10.3233/fi-2020-1980.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

Allender, Eric y Fengming Wang. "On the power of algebraic branching programs of width two". computational complexity 25, n.º 1 (5 de noviembre de 2015): 217–53. http://dx.doi.org/10.1007/s00037-015-0114-7.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

Anderson, Matthew, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka y Ben Lee Volk. "Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs". ACM Transactions on Computation Theory 10, n.º 1 (30 de enero de 2018): 1–30. http://dx.doi.org/10.1145/3170709.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

Kayal, Neeraj, Vineet Nair y Chandan Saha. "Average-case linear matrix factorization and reconstruction of low width algebraic branching programs". computational complexity 28, n.º 4 (18 de julio de 2019): 749–828. http://dx.doi.org/10.1007/s00037-019-00189-0.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

Kayal, Neeraj, Vineet Nair y Chandan Saha. "Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits". ACM Transactions on Computation Theory 12, n.º 1 (25 de febrero de 2020): 1–27. http://dx.doi.org/10.1145/3369928.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

Chaugule, Prasad, Nutan Limaye y Aditya Varre. "Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes". ACM Transactions on Computation Theory 13, n.º 4 (31 de diciembre de 2021): 1–26. http://dx.doi.org/10.1145/3470858.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

STRAUBING, HOWARD. "CONSTANT-DEPTH PERIODIC CIRCUITS". International Journal of Algebra and Computation 01, n.º 01 (marzo de 1991): 49–87. http://dx.doi.org/10.1142/s0218196791000043.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

Šíma, Jiří y Stanislav Žák. "A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3". Fundamenta Informaticae 184, n.º 4 (7 de marzo de 2022): 307–54. http://dx.doi.org/10.3233/fi-2021-2101.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Chikalov, Igor. "On Average Time Complexity of Decision Trees and Branching Programs". Fundamenta Informaticae 39, n.º 4 (1999): 337–57. http://dx.doi.org/10.3233/fi-1999-39401.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

Hrushovski, Ehud, Joël Ouaknine, Amaury Pouly y James Worrell. "On Strongest Algebraic Program Invariants". Journal of the ACM, 8 de agosto de 2023. http://dx.doi.org/10.1145/3614319.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

Dutta, Pranjal, Nitin Saxena y Amit Sinhababu. "Discovering the roots: Uniform closure results for algebraic classes under factoring". Journal of the ACM, 23 de febrero de 2022. http://dx.doi.org/10.1145/3510359.

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!