Gotowe bibliografie tematyczne / Multilinear Depth 3 Circuits

Spis treści

Artykuły w czasopismach
Rozprawy doktorskie
Części książek
Streszczenia konferencji

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"

Ghosal, Purnata, i B. V. Raghavendra Rao. "On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models". Fundamenta Informaticae 177, nr 1 (18.12.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.

Saraf, Shubhangi, i Ilya Volkovich. "Black-Box Identity Testing of Depth-4 Multilinear Circuits". Combinatorica 38, nr 5 (9.12.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.

Raz, Ran, i Amir Yehudayoff. "Lower Bounds and Separations for Constant Depth Multilinear Circuits". computational complexity 18, nr 2 (czerwiec 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.

Chillara, Suryajith. "On Computing Multilinear Polynomials Using Multi- r -ic Depth Four Circuits". ACM Transactions on Computation Theory 13, nr 3 (30.09.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.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Kayal, Neeraj, Vineet Nair i Chandan Saha. "Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits". ACM Transactions on Computation Theory 12, nr 1 (25.02.2020): 1–27. http://dx.doi.org/10.1145/3369928.

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Kayal, Neeraj, i Nitin Saxena. "Polynomial Identity Testing for Depth 3 Circuits". computational complexity 16, nr 2 (maj 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.

Fang, M., S. Fenner, F. Green, S. Homer i Y. Zhang. "Quantum lower bounds for fanout". Quantum Information and Computation 6, nr 1 (styczeń 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.

Lovett, Shachar, i Emanuele Viola. "Bounded-Depth Circuits Cannot Sample Good Codes". computational complexity 21, nr 2 (30.03.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ł

Rozprawy doktorskie na temat "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.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Części książek na temat "Multilinear Depth 3 Circuits"

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

Streszczenia konferencji na temat "Multilinear Depth 3 Circuits"

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

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!