NDLI: Time-space tradeoffs in the counting hierarchy

Content Provider	IEEE Xplore Digital Library
Author	Allender, E. Koucky, M. Ronneburger, D. Roy, S. Vinay, V.
Copyright Year	2001
Description	Author affiliation: Dept. of Comput. Sci., Rutgers Univ., Piscataway, NJ, USA (Allender, E.)
Abstract	Extends the lower-bound techniques of L. Fortnow (2000) to the unbounded-error probabilistic model. A key step in the argument is a generalization of V.A. Nepomnjas/spl caron/c/spl caron/ii/spl breve/'s (1970) theorem from the Boolean setting to the arithmetic setting. This generalization is made possible due to the recent discovery of logspace-uniform TC/sup 0/ circuits for iterated multiplication (A. Chiu et al., 2000). As an example of the sort of lower bounds that we obtain, we show that MAJ-MAJSAT is not contained in PrTiSp(n/sup 1+o(1)/, n/sup /spl epsiv//) for any /spl epsiv/<1. We also extend one of Fortnow's lower bounds, from showing that S~A~T~ does not have uniform NC/sup 1/ circuits of size n/sup 1+o(1)/, to a similar result for SAC/sup 1/ circuits.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Math. Found. Comput
Starting Page	295
Ending Page	302
File Size	710702
Page Count	8
File Format	PDF
ISBN	0769510531
DOI	10.1109/CCC.2001.933896
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-06-18
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Circuits Computer science Arithmetic Automation Binary decision diagrams Polynomials Complexity theory
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Time-space tradeoffs for branching programs

Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits

Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Hybrid decision diagrams

Primality and identity testing via Chinese remaindering

Extremal properties of polynomial threshold functions

Time-space tradeoffs in the counting hierarchy

Similar Documents

Time-space tradeoffs for branching programs

Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits

Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Hybrid decision diagrams

Primality and identity testing via Chinese remaindering

Extremal properties of polynomial threshold functions

Time-space tradeoffs in the counting hierarchy