Bibliografías temáticas / Multilinear Depth 3 Circuits

Literatura académica sobre el tema "Multilinear Depth 3 Circuits"

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:

Índice

Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Multilinear Depth 3 Circuits".

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.

Artículos de revistas sobre el tema "Multilinear Depth 3 Circuits"

1

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

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

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

Texto completo
Resumen
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).
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

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

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

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

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
Más fuentes

Tesis sobre el tema "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.

Texto completo
Resumen
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.
Los estilos APA, Harvard, Vancouver, ISO, etc.

Capítulos de libros sobre el tema "Multilinear Depth 3 Circuits"

1

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
2

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

Bhargava, Vishwas, Shubhangi Saraf y Ilya Volkovich. "Reconstruction of Depth-4 Multilinear Circuits". En 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.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
7

Garg, Sanjam, Craig Gentry, Shai Halevi, Amit Sahai y Brent Waters. "Attribute-Based Encryption for Circuits from Multilinear Maps". En 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.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

Klivans, Adam R. "On the Derandomization of Constant Depth Circuits". En 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.

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

Actas de conferencias sobre el tema "Multilinear Depth 3 Circuits"

1

Bhargava, Vishwas, Shubhangi Saraf y Ilya Volkovich. "Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits". En 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.

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
2

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
3

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
4

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
5

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
6

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
7

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
8

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
9

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
10

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

Texto completo
Los estilos APA, Harvard, Vancouver, ISO, etc.
También puede estar interesado en las bibliografías ampliadas sobre el tema "Multilinear Depth 3 Circuits" para tipos de fuentes particulares:
Artículos de revistas
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!

Pasar a la bibliografía