Log in

Relevant bibliographies by topics / Multilinear Depth 3 Circuits

Contents

Journal articles

Academic literature on the topic 'Multilinear Depth 3 Circuits'

Author: Grafiati

Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Multilinear Depth 3 Circuits.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "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.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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 arith

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!