Готові списки джерел за темами / Multilinear Depth 3 Circuits

Добірка наукової літератури з теми "Multilinear Depth 3 Circuits"

Автор: Grafiati

Опубліковано: 6 вересня 2023

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

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

Зміст

Статті в журналах
Дисертації
Частини книг
Тези доповідей конференцій

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Multilinear Depth 3 Circuits".

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

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

Статті в журналах з теми "Multilinear Depth 3 Circuits"

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Анотація:

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 та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Більше джерел

Дисертації з теми "Multilinear Depth 3 Circuits"

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.

Повний текст джерела

Анотація:

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 та ін.

Частини книг з теми "Multilinear Depth 3 Circuits"

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "Multilinear Depth 3 Circuits"

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

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.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!