NDLI: Meanders, Ramsey theory and lower bounds for branching programs

Content Provider	IEEE Xplore Digital Library
Author	Alon, Noga Maass, Wolfgang
Copyright Year	1986
Abstract	A novel technique for obtaining lower bounds for the time versus space complexity of certain functions in a general input oblivious sequential model of computation is developed. This is demonstrated by studying the intrinsic complexity of the following set equality problem SE(n,m): Given a sequence x1,x2,....,xn, y1,....,yn of 2n numbers of m bits each, decide whether the sets [x1,....,xn] and [y1,...,yn] coincide. We show that for any log log n ≤ m ≤1/2log n and any 1 ≤ s ≤ log n, any input oblivious sequential computation that solves SE(n,m) using 2m/s space, takes Ω(n ? s) time. This result is sharp for all admissible values of n,m,s and is the first known nontrivial time space tradeoff lower bound (for space = ω (log n) of a set recognition problem on such a general model of computation. Our method also supplies lower bounds on the length of arbitrary (not necessarily input oblivious) branching programs for several natural symmetric functions, improving results of Chandra, Furst and Lipton, of Pudlák and of Ajtai et. al. For example we show that for the majority - function any branching program of width w(n) has length ω(n ? log n/w (n) ? log w (n)), in particular for bounded width we get length ω (n log n) (independently of our work Babai et. al. [BPRS] have simultaneously proved this last result). Our lower bounds for branching programs imply lower bounds on the number of steps that are needed to pebble arbitrary computation graphs for the same computational problems. To establish our lower bounds we introduce the new concept of a meander that captures superconcentrator-type properties of sequences. We prove lower bounds on the length of meanders via a new Ramsey theoretic lemma that is of interest in its own right. This lemma has other applications, including a tight lower bound on the size of weak superconcentrators of depth 2 that strengthens the known lower bound of Pippenger [Pi]. A surprising new feature of these applications of Ramsey theory in lower bound arguments is the fact that no numbers are required to be unusually large and that several of the resulting superlinear lower bounds are in fact optimal.
Starting Page	410
Ending Page	417
File Size	1152502
Page Count	8
File Format	PDF
ISBN	0818607408
ISSN	02725428
DOI	10.1109/SFCS.1986.31
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1986-10-27
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Binary decision diagrams Computational modeling Input variables Time sharing computer systems Business process re-engineering Decision trees
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

Superlinear lower bounds for bounded-width branching programs

Lower bounds for monotone span programs

A non-linear time lower bound for Boolean branching programs

Super-linear time-space tradeoff lower bounds for randomized computation

On arithmetic branching programs

Efficient oblivious branching programs for threshold functions

Some lower and upper bounds for algebraic decision trees and the separation problem

Meanders, Ramsey theory and lower bounds for branching programs (1986)

Meanders, Ramsey theory and lower bounds for branching programs

Similar Documents

Time-space tradeoffs for branching programs

Superlinear lower bounds for bounded-width branching programs

Lower bounds for monotone span programs

A non-linear time lower bound for Boolean branching programs

Super-linear time-space tradeoff lower bounds for randomized computation

On arithmetic branching programs

Efficient oblivious branching programs for threshold functions

Some lower and upper bounds for algebraic decision trees and the separation problem

Meanders, Ramsey theory and lower bounds for branching programs (1986)

Meanders, Ramsey theory and lower bounds for branching programs