Matthias Krause
- A89.Allender,E.: A note on the power of threshold circuits, Proceedings der 30. IEEE Symposium FOCS, 1989, 580-584.Google Scholar
Digital Library
- AB91.Alon,N.,J.Bruck: Explicit constructions of depth-2 majority circuits for comparison and addition, Technical Report RJ 8300 (75661) of the IBM Almaden Research Center, San Jose, 1991.Google Scholar
- ABFR91.Aspnes,J.,R.Beigel,M.Furst,S.Rudich: The expressive power of voting polynomials Proc. ACM Conference 23th STOC, 1991, 402-409. Google ScholarDigital Library
- Ba92.Barrington,D.A: Quasipolynomial size circuits. Proc. IEEE Conference Structure in Complexity, 1992, 86-93.Google Scholar
- Be92.Beigel,R.: Perceptrons, PP, and the Polynomial Hierarchy. Proc. of SCT'92, 14-19.Google Scholar
- Be93.Beigel,R.: The polynomial method in circuit complexity SCT'93, 82-95.Google Scholar
- B90.Bruek,J.: Harmonic analysis of polynomial threshold functions, SIAM Journal of Discrete Mathematics, 3, Nr. 22, 1990, 168-177.Google ScholarCross Ref
- BKS92.Bruck,J.,Th.Hofmeister,Th.Kailath,K.Y.Siu: Depth efficient networks for division and related problems. Technical Report 1992, to appear in 1993.Google Scholar
- BS90.Bruck,J.,R.Smolensky: Polynomial threshold functions, AC~-functions and spectral norms Proc. 31th IEEE Conference FOCS, 1990, 632-641.Google Scholar
- G93.Goldmann,M.: A note on the power of majority gates and modular gates, preprint, 1993.Google Scholar
- GHR92.Goldmann,M.,J.H~stad,A.A.Razborov: Majority Gates versus general weighted threshold gates, J. of Computational Complexity 2 (1992), 277-300.Google ScholarCross Ref
- GK93.Goldmann,M.,M.Karpinski: Simulating Threshold Circuits by Majority Circuits. Proc. 25th ACM Conference STOC, 1993. Google ScholarDigital Library
- HR89.Hagerup, T., Riib, C.: A guided tour of Chernoff bounds, Inf. Process. Letters, 33, 1989/90,305-308. Google ScholarDigital Library
- HMPST87.ttaj nal,A.,W.Maass,P.Pudlhk,M.Szegedy, G.Turgm: Threshold circuits of bounded depth, Proc. 28th IEEE Conf. FOCS, 1987, 99-110.Google Scholar
- HHK91.Hofmeister,Th.,W.Hohberg,S.KShling: Some notes on threshold circuits and multiplication in depth 4. IPL 39 (1991) 219-225 Google ScholarDigital Library
- LMN89.Linial,N.,Y.Mansour,N.Nisan: Constant Depth Circuits, Fourier Transforms, and Learnability. Proc. 30th IEEE Conference FOCS, 1990.Google Scholar
- KORS91.Kailath,Th., A.Orlitsky, V.Roychowdhury, K.Y.Siu: A geometric approach to Threshold Circuit Complexity, Proc. 4th ACM Conference COLT, 1991, 97-111. Google ScholarDigital Library
- K90.Krause,M. Geometric Arguments yield better bounds for threshold circuits and distributed computing. Proc. of SCT'91,314-322.Google Scholar
- KW91.Krause,M.,S.Waack, Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in, Proc. 32th IEEE Conference FOCS, 1991, 777-787. Google ScholarDigital Library
- MSS91.Maass,W.,G.Schnitger,E.Sonntag On the Computational Power of Sigmoid versus Boolean Threshold Circuits Proc. of FOCS'91,767-776. Google ScholarDigital Library
- MP68.Minsky, M.,S.Papert: Perceptrons MIT Press, Cambridge 1988 Expanded edition. First edition appeared in 1968.Google Scholar
- R87.Razborov, A.A: Lower bounds for the size of circuits of bounded depth with basis {#, A}, Journal Math. Zametki. 41, 1987, 598-607.Google Scholar
- S87.Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proc. 19th ACM Conference STOC, 1987, 77-82. Google ScholarDigital Library
- T91.Tarui,J.: Randomized polynomials, threshold circuits, and the polynomial hierarchy. Proc. of STACS'91, 238-251. Google ScholarDigital Library
- Ts93.Tsai,S.-C.: Lower bounds on representing boolean functions as polynomials. SCT'93, 96-101.Google Scholar
- YP94.Yan, P.Y., Parberry, i.: Exponential size lower bounds for some depth three circuits. Information and Computation, to appear. Google ScholarDigital Library
- Y90.Yao,A.C.: On A CC and Threshold Circuits, Proc. 31th IEEE Conference FOCS, 1990, 619-628.Google Scholar
Index Terms
- On the computational power of depth 2 circuits with threshold and modulo gates
Recommendations
Exponential lower bound for bounded depth circuits with few threshold gates
We prove an exponential lower bound on the size of bounded depth circuits with O(logn) threshold gates computing an explicit function (namely, the parity function). Previously exponential lower bounds were known only for circuits with one threshold ...
On the computational power of sigmoid versus boolean threshold circuits (extended abstract)
SFCS '91: Proceedings of the 32nd annual symposium on Foundations of computer scienceThe power of constant depth circuits with sigmoid (i.e., smooth) threshold gates for computing Boolean functions is examined. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size Boolean ...
Design of Arithmetic Circuits Using Reversible Logic Gates and Power Dissipation Calculation
ISED '10: Proceedings of the 2010 International Symposium on Electronic System DesignIn the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nano technology and optical computing. Reversible logic circuits provide less power dissipation as well as distinct ...
Comments