Zaloguj się

Gotowe bibliografie tematyczne / Multilinear Depth 3 Circuits

Spis treści

Artykuły w czasopismach

Gotowa bibliografia na temat „Multilinear Depth 3 Circuits”

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:

Zobacz listy aktualnych artykułów, książek, rozpraw, streszczeń i innych źródeł naukowych na temat „Multilinear Depth 3 Circuits”.

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 "Multilinear Depth 3 Circuits"

1

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

2

Saraf, Shubhangi, and Ilya Volkovich. "Black-Box Identity Testing of Depth-4 Multilinear Circuits." Combinatorica 38, no. 5 (2017): 1205–38. http://dx.doi.org/10.1007/s00493-016-3460-4.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

Raz, Ran, and Amir Yehudayoff. "Lower Bounds and Separations for Constant Depth Multilinear Circuits." computational complexity 18, no. 2 (2009): 171–207. http://dx.doi.org/10.1007/s00037-009-0270-8.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

4

Chillara, Suryajith. "On Computing Multilinear Polynomials Using Multi- r -ic Depth Four Circuits." ACM Transactions on Computation Theory 13, no. 3 (2021): 1–21. http://dx.doi.org/10.1145/3460952.

Pełny tekst źródła

Streszczenie:

In this article, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which the polynomial computed at every node has a bound on the individual degree of r ≥ 1 with respect to all its variables (referred to as multi- r -ic circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better bounds as the value of r increases. Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing an explicit multilinear polynomial on n O (1) variables and degree d must have size at least ( n / r 1.1 ) Ω(√ d / r ) . This bound, however, deteriorates as the value of r increases. It is a natural question to ask if we can prove a bound that does not deteriorate as the value of r increases, or a bound that holds for a larger regime of r . In this article, we prove a lower bound that does not deteriorate with increasing values of r , albeit for a specific instance of d = d ( n ) but for a wider range of r . Formally, for all large enough integers n and a small constant η, we show that there exists an explicit polynomial on n O (1) variables and degree Θ (log 2 n ) such that any depth four circuit of bounded individual degree r ≤ n η must have size at least exp(Ω(log 2 n )). This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).

Style APA, Harvard, Vancouver, ISO itp.

5

Karnin, Zohar S., Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. "Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in." SIAM Journal on Computing 42, no. 6 (2013): 2114–31. http://dx.doi.org/10.1137/110824516.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

6

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.

7

Gupta, Ankit, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. "Arithmetic Circuits: A Chasm at Depth 3." SIAM Journal on Computing 45, no. 3 (2016): 1064–79. http://dx.doi.org/10.1137/140957123.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

8

Kayal, Neeraj, and Nitin Saxena. "Polynomial Identity Testing for Depth 3 Circuits." computational complexity 16, no. 2 (2007): 115–38. http://dx.doi.org/10.1007/s00037-007-0226-9.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

Fang, M., S. Fenner, F. Green, S. Homer, and Y. Zhang. "Quantum lower bounds for fanout." Quantum Information and Computation 6, no. 1 (2006): 46–57. http://dx.doi.org/10.26421/qic6.1-3.

Pełny tekst źródła

Streszczenie:

We consider the resource bounded quantum circuit model with circuits restricted by the number of qubits they act upon and by their depth. Focusing on natural universal sets of gates which are familiar from classical circuit theory, several new lower bounds for constant depth quantum circuits are proved. The main result is that parity (and hence fanout) requires log depth quantum circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancill\ae. Under this constraint, this bound is close to optimal. In the case of a non-constant number $a$ of ancill\ae\ and $n$ input qubits, we give a tradeoff between $a$ and the required depth, that results in a non-constant lower bound for fanout when $a = n^{1-o(1)}$. We also show that, regardless of the number of ancill\ae\, arbitrary arity Toffoli gates cannot be simulated exactly by a constant depth circuit family with gates of bounded arity.

Style APA, Harvard, Vancouver, ISO itp.

10

Lovett, Shachar, and Emanuele Viola. "Bounded-Depth Circuits Cannot Sample Good Codes." computational complexity 21, no. 2 (2012): 245–66. http://dx.doi.org/10.1007/s00037-012-0039-3.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Więcej źródeł

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!