Tools

LEADER 03339nam 2200625Ma 4500

001 ocn610959057;

003 OCoLC;

005 20141212051525.0;

006 m e d ;

007 cr bn||||m|||a;

008 100117s2009 maua fsab 000 0 eng d;

020 a| 9781601983015 (electronic);

020 a| 1601983018 (electronic);

024 7 a| 10.1561/04000000332| doi;

035 a| (Sirsi) o610959057;

035 a| (OCoLC)610959057;

040 a| SFBc| SFBd| EREd| UtOrBLW;

049 a| EREE;

050 4 a| QA76.9.M35b| V566 2009;

082 04 a| 0042| 22;

100 1 a| Viola, Emanuele.?| UNAUTHORIZED;

245 10 a| On the power of small-depth computation /c| Emanuele Viola.;

300 a| 1 electronic text (72 pages : illustrations) :b| digital file.;

336 a| text2| rdacontent;

337 a| computer2| rdamedia;

338 a| online resource2| rdacarrier;

490 1 a| Foundations and trends in theoretical computer science,x| 1551-3068 ;v| v. 5, issue 1, p. 1-72;

500 a| Title from PDF (viewed on January 17, 2010).;

504 a| Includes bibliographical references (p. 67-72).;

505 0 a| Abstract -- 1. Introduction -- 2. Polynomials over {0,1} -- 3. The correlation of parity with small-depth circuits -- 4. Logarithmic depth vs. depth 3 -- 5. Cryptography in bounded depth -- References.;

510 0 a| Google Scholar.;

510 0 a| Google Book Search.;

510 0 a| INSPEC.;

510 0 a| Scopus.;

510 0 a| ACM Computing Guide.;

510 0 a| DBPLP Computer Science Bibliography.;

510 0 a| Zentralblatt MATH Database.;

510 0 a| AMS MathSciNet.;

510 0 a| ACM Computing Reviews.;

520 a| In this work we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain: (1) A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0, 1}.(2) An unpublished proof that small bounded-depth circuits (AC0) have exponentially small correlation with the parity function. The proof is due to Klivans and Vadhan; it builds upon and simplifies previous ones. (3) Valiant's simulation of log-depth linear-size circuits of fan-in 2 by sub-exponential size circuits of depth 3 and unbounded fan-in. To our knowledge, a proof of this result has never appeared in full. (4) Applebaum, Ishai, and Kushilevitz's cryptography in bounded depth.;

524 a| Emanuele Viola (2009) "On the Power of Small-Depth Computation", Foundations and Trends in Information Retrieval: Vol. 5: No 1, pp 1-72.;

530 a| Also available in print.;

538 a| Mode of access: World Wide Web.;

538 a| System requirements: Adobe Acrobat Reader.;

650 0 a| Computer science.=| ^A267953;

650 0 a| Computer sciencex| Mathematics.=| ^A236643;

830 0 a| Foundations and trends in theoretical computer science (Online) ;v| v. 5, issue 1, p. 1-72.?| UNAUTHORIZED;

856 40 u| http://dx.doi.org/10.1561/0400000033;

949 a| QA76.9.M35b| V566 2009h| JOYNER48o| jmpli| 30372015332718;

994 a| C0b| ERE;

596 a| 1;

998 a| 2266575;

999 a| QA76.9 .M35w| LCc| 1i| 30372015332718d| 3/18/2013f| 3/18/2013g| 1l| JGESm| JOYNERr| Ys| Yt| JGESBKu| 5/12/2010x| BOOKz| JSTACKSo| .STAFF. jmpl;

On the power of small-depth computation / Emanuele Viola.

Author/creator	Viola, Emanuele
Format	Electronic
Publication Info	Hanover, Mass. : Now Publishers, ©2009.
Description	1 electronic text (72 pages : illustrations) : digital file.
Supplemental Content	http://dx.doi.org/10.1561/0400000033
Subjects	Computer science. Computer science--Mathematics.

Series	Foundations and trends in theoretical computer science, 1551-3068 ; v. 5, issue 1, p. 1-72 Foundations and trends in theoretical computer science (Online) ; v. 5, issue 1, p. 1-72. UNAUTHORIZED
Contents	Abstract -- 1. Introduction -- 2. Polynomials over {0,1} -- 3. The correlation of parity with small-depth circuits -- 4. Logarithmic depth vs. depth 3 -- 5. Cryptography in bounded depth -- References.
Abstract	In this work we discuss selected topics on small-depth computation, presenting a few unpublished proofs along the way. The four sections contain: (1) A unified treatment of the challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0, 1}.(2) An unpublished proof that small bounded-depth circuits (AC0) have exponentially small correlation with the parity function. The proof is due to Klivans and Vadhan; it builds upon and simplifies previous ones. (3) Valiant's simulation of log-depth linear-size circuits of fan-in 2 by sub-exponential size circuits of depth 3 and unbounded fan-in. To our knowledge, a proof of this result has never appeared in full. (4) Applebaum, Ishai, and Kushilevitz's cryptography in bounded depth.
General note	Title from PDF (viewed on January 17, 2010).
Bibliography note	Includes bibliographical references (p. 67-72).
Citation/references note	Google Scholar.
Citation/references note	Google Book Search.
Citation/references note	INSPEC.
Citation/references note	Scopus.
Citation/references note	ACM Computing Guide.
Citation/references note	DBPLP Computer Science Bibliography.
Citation/references note	Zentralblatt MATH Database.
Citation/references note	AMS MathSciNet.
Citation/references note	ACM Computing Reviews.
Cite as	Emanuele Viola (2009) "On the Power of Small-Depth Computation", Foundations and Trends in Information Retrieval: Vol. 5: No 1, pp 1-72.
Other forms	Also available in print.
Technical details	Mode of access: World Wide Web.
Technical details	System requirements: Adobe Acrobat Reader.
ISBN	9781601983015 (electronic)
ISBN	1601983018 (electronic)
Standard identifier#	10.1561/0400000033

Availability

Library	Location	Call Number	Status	Item Actions
Joyner	General Stacks	QA76.9 .M35	✔ Available	Place Hold

On the power of small-depth computation / Emanuele Viola.

Click here for more information about this title

Availability