article

Free access

Constant depth circuits, Fourier transform, and learnability

Authors:

Nathan Linial,

Yishay Mansour,

Noam NisanAuthors Info & Claims

Journal of the ACM (JACM), Volume 40, Issue 3

Pages 607 - 620

https://doi.org/10.1145/174130.174138

Published: 01 July 1993 Publication History

PDF eReader

References

[1]

~ AJTAI, M. E~l-formulae on finite structure. Ann. Pure Appl. Logic 24 (1983), 1-48.

Google Scholar

[2]

~AJTAI, M., AND WIGDERSON, A. Deterministic simulation of probabilistic constant depth ~circuits. In Aduances in computing research, Vol. 5. S. Micali, ed. JAI Press, Greenwich, Ct., ~1989, pp. 199-222.

Google Scholar

[3]

~BRANDMAN, Y., HENNESSY, J., AND ORLITSKY, A. A spectral lower bound technique for the ~size of decision trees and two level circuits. IEEE Trans. Comput. 39, 2 (1990), 282-287.

Crossref

Google Scholar

[4]

~DYM, H., AND MCKEAN, H.P. Fourier Series and httegrals. Academic Press, Orlando, Fla., ~1972.

Google Scholar

[5]

~FURST, M., SAXE, J., AND SIPSER, M. Parity, circuits, and the polynomial-time hierarchy. ~Math. Syst. Theory 17 (1984), 13-27.

Google Scholar

[6]

~GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. How to construct random functions. J. ~ACM 33, 4 (Oct. 1986), 792-807.

Crossref

Google Scholar

[7]

~HAGERUP, T., AND RUB, C. A guided tour to Chernoff bounds. Inf. Proc. Lett. 33 (1989), ~305-308.

Crossref

Google Scholar

[8]

~HASTAD, J. AND BOPPANA, Computational limitations for small depth circuits. Ph.D. disserta- ~tion, MIT Press, Cambridge, Mass., 1986.

Crossref

Google Scholar

[9]

~KAHN, J., KALAI, G., AND LINIAL, N. The influence of variables on Boolean functions. In ~Proceedings of the 29th Annual Symposium on Foundations of Computer Science (White Plains, ~N.Y., Oct.). IEEE, New York, 1988, pp. 68-80.

Google Scholar

[10]

~KEARNS, M., AND VALIANT, L. Cryptographic limitations on learning Boolean formulae and ~finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing ~(Seattle, Wash., May). ACM, New York, 1989, pp. 433-444.

Crossref

Google Scholar

[11]

~LINEAL, N., AND NISAN, N. Approximate inclusion-exclusion. In Proceedings of the 22nd ~Annual ACM Symposium on Theory of Computing. (Baltimore, Md., May 12-14). ACM, New ~York, 1990, pp. 260-270.

Crossref

Google Scholar

[12]

~MANSOUR, Y., NISAN, N., AND TIWARI, P. The computational complexity of universal ~hashing. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. ~(Baltimore, Md., May 12-14). ACM, New York, 1990, pp. 235-243.

Crossref

Google Scholar

[13]

~NISAN, N., AND WIGDERSON, m. Hardness vs. randomness. In Proceedings of the 29th Annual ~Symposium on Foundations of Computer Science (White Plains, N.Y., Oct.) IEEE, New York, ~1988, pp. 2-12.

Google Scholar

[14]

~RAZBOROV, A. A. Lower bounds for the size of circuits of bounded depth with basis ~AND, XOR. Math. Zametskz 41 (1987), 598-607 (in Russian). English translation in Math ~Notes 41 (1987), 333-338.

Google Scholar

[15]

~RIVEST, R.L. Learning decision lists. Machine Learning 2, 3 (1987), 229 246.

Crossref

Google Scholar

[16]

~ANTHA, M., AND WILSON, C. Polynomial size circuits with a hmited number of negations. In ~Proceedings of the 8th Am~ttal Symposium on Aspects of Theoretical Co,zputer Science. IEEE, ~New York, 1991, pp. 228 237.

Crossref

Google Scholar

[17]

~SMOLENSKY, R. Algebraic methods in the theory of lower bounds for Boolean circuit ~complexity. In Proceedings of the 19th Atmual ACM Symposmm on Theoty of Computing (New ~York City, N.Y., May 25-27). ACM, New York, 1987, pp. 77 82.

Crossref

Google Scholar

[18]

~VALIANT, L.G. A theory of the learnable. Commun ACM 27, 11 (Nov. 1984), 1134-1142.

Crossref

Google Scholar

[19]

~YAO, A.C. Theory and applications of trapdoor functions. In Proceedings of the 23rd A~mual ~Symposium on Foundatzons of Computer Science. IEEE, New York, 1982, pp. 80-91.

Google Scholar

[20]

~YAo, A.C. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th ~Anmtal Symposuon on Foundations of Computer Sctence (Portland, Ore. Oct.). IEEE, New ~York, 1985, pp. 1-10.

Crossref

Google Scholar

Cited By

View all

Arunachalam SDoriguello J(2024)Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet caseACM Transactions on Computation Theory10.1145/368882416:4(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3688824
Gur TJahanara MKhodabandeh MRajgopal NSalamatian BShinkar IMohar BShinkar IO'Donnell R(2024)On the Power of Interactive Proofs for LearningProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649784(1063-1070)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649784
Huang HLiu YBroughton MKim IAnshu ALandau ZMcClean JMohar BShinkar IO'Donnell R(2024)Learning Shallow Quantum CircuitsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649722(1343-1351)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649722
Show More Cited By

Index Terms

Constant depth circuits, Fourier transform, and learnability

Recommendations

Constant depth circuits, Fourier transform, and learnability
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

Boolean functions in AC/sup O/ are studied using the harmonic analysis of the cube. The main result is that an AC/sup O/ Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of ...
Constant-Depth Circuits vs. Monotone Circuits
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity Conference

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

• For every k ≥ 1, there is a monotone function in AC⁰ (constant-depth poly-size circuits) that requires monotone circuits of depth Ω(log^k n). ...
Complexity Based on Partitioning of Boolean Circuits and their Relation to Multivalued Circuits

We present a new complexity measure for Boolean functions based on partitions of combinatorial circuits into subcircuits, and give upper and lower bounds on the complexity for Boolean functions. Roughly speaking, for a function g whose range is the set ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 40, Issue 3

July 1993

369 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/174130

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Published in JACM Volume 40, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

424
Total Citations
View Citations
2,587
Total Downloads

Downloads (Last 12 months)260
Downloads (Last 6 weeks)20

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Arunachalam SDoriguello J(2024)Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet caseACM Transactions on Computation Theory10.1145/368882416:4(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3688824
Gur TJahanara MKhodabandeh MRajgopal NSalamatian BShinkar IMohar BShinkar IO'Donnell R(2024)On the Power of Interactive Proofs for LearningProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649784(1063-1070)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649784
Huang HLiu YBroughton MKim IAnshu ALandau ZMcClean JMohar BShinkar IO'Donnell R(2024)Learning Shallow Quantum CircuitsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649722(1343-1351)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649722
Nadimpalli SParham NVasconcelos FYuen HMohar BShinkar IO'Donnell R(2024)On the Pauli Spectrum of QAC0Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649662(1498-1506)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649662
Gamarnik DJagannath AWein A(2024)Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin DynamicsSIAM Journal on Computing10.1137/22M150263X53:1(1-46)Online publication date: 13-Feb-2024
https://doi.org/10.1137/22M150263X
Chatterjee DPratihar KHazra ARührmair UMukhopadhyay D(2024)Systematically Quantifying Cryptanalytic Nonlinearities in Strong PUFsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.332943819(1126-1141)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3329438
Rouzé CWirth MZhang H(2024)Quantum Talagrand, KKL and Friedgut’s Theorems and the Learnability of Quantum Boolean FunctionsCommunications in Mathematical Physics10.1007/s00220-024-04981-0405:4Online publication date: 9-Apr-2024
https://doi.org/10.1007/s00220-024-04981-0
Beimel AMalkin TMazor N(2024)Structural Lower Bounds on Black-Box Constructions of Pseudorandom FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_16(459-488)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_16
Harsha PMolli TShankar A(2023)Criticality of AC0-FormulaeProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.19(1-24)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.19
Kumar V(2023)Tight Correlation Bounds for Circuits Between AC0 and TC0Proceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.18(1-40)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.18
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations