Relevant bibliographies by topics / Multilinear Depth 3 Circuits

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

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 (December 18, 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 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, and other styles
2

Saraf, Shubhangi, and Ilya Volkovich. "Black-Box Identity Testing of Depth-4 Multilinear Circuits." Combinatorica 38, no. 5 (December 9, 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 (June 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 (September 30, 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 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).
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 (January 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 (February 25, 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 (January 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 (May 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 (January 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-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.
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 (March 30, 2012): 245–66. http://dx.doi.org/10.1007/s00037-012-0039-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Multilinear Depth 3 Circuits"

1

Nair, Vineet. "Expanders in Arithmetic Circuit Lower Bound : Towards a Separation Between ROABPs and Multilinear Depth 3 Circuits." Thesis, 2015. https://etd.iisc.ac.in/handle/2005/4811.

Full text
Abstract:
Consider the problem of Polynomial Identity Testing(PIT): we are given an arithmetic circuit computing a multivariate polynomial over some eld and we have to determine whether that polynomial is identically zero or not. PIT is a fundamental problem and has applications in both algorithms and complexity theory. In this work, our aim is to study PIT for the model of multilinear depth three circuits for which no deterministic polynomial time identity test is known. An nO(log n) time blackbox PIT for set-multilinear depth three circuits (a special kind of multilinear depth three circuits) is known due to [ASS12], [FS13]. To get a better understanding of the problem at hand, we move towards multilinear depth three circuits by considering in- termediate circuit classes which encompasse more polynomials than set-multilinear depth three circuits and are `natural' subclasses of multilinear depth three circuits. One such model is `superposition of set-multilinear depth 3 circuits'. Our initial observations are: There is an nO(log n) whitebox PIT for superposition of two set-multilinear depth 3 circuits. There is a sub-exponential time whitebox PIT for superposition of constantly many set- multilinear depth 3 circuits. The second observation is subsumed by the recent independent and almost simultaneous work by [OSV15] that gives sub-exponential time hitting set for multilinear depth three circuits. A recent line of research considers hitting set for Read Once Oblivious Algebraic Branching Programs (ROABP's) which subsumes set-multilinear depth three circuits. An nO(log n) black box PIT is given for ROABP's of width polynomial in the number of variables in [AGKS14]. It is natural to ask whether this result on ROABP PIT can be used to give e cient (meaning polynomial or quasi-polynomial time) PIT for multilinear depth three circuits. For instance, the result by [OSV15] elegantly uses ROABP PIT as a `base case' (in a certain sense) to give a sub-exponential time PIT algorithm for multilinear depth three circuits. At this point, we wondered if multilinear depth three circuits of size s could also be computed by an ROABP of size polynomial in s. If true then this would immediately imply a quasi-polynomial time hitting set for multilinear depth three circuits, which is a long standing open problem in algebraic complexity theory. For instance, it can be shown that any multlinear depth three circuit with top fan-in two and just two variables per linear polynomial can be computed by an ROABP with constant width. But we show in our main result that this is not true for general multilinear depth three circuits that are superpositions of only two set-multilinear depth three circuits. There is a polynomial computed by a superposition of two set-multilinear depth 3 circuits with top fan-in just three and size polynomial in the number of variables n, such that any ROABP computing the polynomial has width 2 (n). There is a polynomial computed by a superposition of three set-multilinear depth 3 circuits with top fan-in just two and size polynomial in the number of variables n, such that any ROABP computing the polynomial has width 2 (n). This means the approach of directly converting a multilinear depth 3 circuit (even a superposi- tion of set-multilinear depth 3 circuits) to an ROABP and then applying the existing PIT for ROABP will not work. However the underlying techniques in [ASS12], [AGKS14] and [OSV15] might still be useful. The proofs of the above lower bounds are based on explicit construction of expander graphs that can be used to design multilinear depth three circuits (in particular su- perposition of set-multilinear depth 3 circuits) with high `evaluation dimension' - a complexity measure that is well suited to capture a `weakness' of ROABPs.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Multilinear Depth 3 Circuits"

1

Goldreich, Oded, and Avishay Tal. "On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions." In Lecture Notes in Computer Science, 306–25. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-43662-9_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Goldreich, Oded, and Avi Wigderson. "On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions." In Lecture Notes in Computer Science, 41–86. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-43662-9_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bhargava, Vishwas, Shubhangi Saraf, and Ilya Volkovich. "Reconstruction of Depth-4 Multilinear Circuits." In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2144–60. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2020. http://dx.doi.org/10.1137/1.9781611975994.132.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Jukna, Stasys. "Depth-3 Circuits." In Algorithms and Combinatorics, 303–38. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-24508-4_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jukna, Stasys. "Large-Depth Circuits." In Algorithms and Combinatorics, 339–69. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-24508-4_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Razborov, Alexander A. "On small depth threshold circuits." In Algorithm Theory — SWAT '92, 42–52. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/3-540-55706-7_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Garg, Sanjam, Craig Gentry, Shai Halevi, Amit Sahai, and Brent Waters. "Attribute-Based Encryption for Circuits from Multilinear Maps." In Advances in Cryptology – CRYPTO 2013, 479–99. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40084-1_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Tang, Fei, Hongda Li, and Bei Liang. "Attribute-Based Signatures for Circuits from Multilinear Maps." In Lecture Notes in Computer Science, 54–71. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-13257-0_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Lingas, Andrzej. "Lower Bounds for Monotone q-Multilinear Boolean Circuits." In Lecture Notes in Computer Science, 301–12. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-23101-8_20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Klivans, Adam R. "On the Derandomization of Constant Depth Circuits." In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 249–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-44666-4_28.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Multilinear Depth 3 Circuits"

1

Bhargava, Vishwas, Shubhangi Saraf, and Ilya Volkovich. "Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits." In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3406325.3451096.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Chillara, Suryajith, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. "A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits." In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. http://dx.doi.org/10.1109/focs.2018.00092.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Saraf, Shubhangi, and Ilya Volkovich. "Black-box identity testing of depth-4 multilinear circuits." In the 43rd annual ACM symposium. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/1993636.1993693.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Raz, Ran, and Amir Yehudayoff. "Lower Bounds and Separations for Constant Depth Multilinear Circuits." In 2008 23rd Annual IEEE Conference on Computational Complexity. IEEE, 2008. http://dx.doi.org/10.1109/ccc.2008.8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Gupta, Ankit, Neeraj Kayal, and Satya Lokam. "Reconstruction of depth-4 multilinear circuits with top fan-in 2." In the 44th symposium. New York, New York, USA: ACM Press, 2012. http://dx.doi.org/10.1145/2213977.2214035.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Karnin, Zohar S., Partha Mukhopadhyay, Amir Shpilka, and Ilya Volkovich. "Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in." In the 42nd ACM symposium. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1806689.1806779.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Paturi, Ramamohan, Michael E. Saks, and Francis Zane. "Exponential lower bounds for depth 3 Boolean circuits." In the twenty-ninth annual ACM symposium. New York, New York, USA: ACM Press, 1997. http://dx.doi.org/10.1145/258533.258556.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Kayal, Neeraj, and Shubhangi Saraf. "Blackbox Polynomial Identity Testing for Depth 3 Circuits." In 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2009. http://dx.doi.org/10.1109/focs.2009.67.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Dutta, Pranjal, Prateek Dwivedi, and Nitin Saxena. "Demystifying the border of depth-3 algebraic circuits." In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. http://dx.doi.org/10.1109/focs52979.2021.00018.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Grigoriev, Dima, and Marek Karpinski. "An exponential lower bound for depth 3 arithmetic circuits." In the thirtieth annual ACM symposium. New York, New York, USA: ACM Press, 1998. http://dx.doi.org/10.1145/276698.276872.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Multilinear Depth 3 Circuits' for particular source types:
Journal articles
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!

To the bibliography