NDLI: AT2 bounds for a class of VLSI problems and string matching

Please wait, while we are loading the content...

An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract)

A comparison of parallel algorithms for connected components

Improved bounds for routing and sorting on multi-dimensional meshes

2d-bubblesorting in average time O(√N lg N)*

Parallel sorting by over partitioning

Efficient compilation of high-level data parallel algorithms

SIMD instruction cache

Improved parity-declustered layouts for disk arrays

Scheduling trees using FIFO queues: a control-memory tradeoff

Studying overheads in massively parallel MIN/MAX-tree evaluation

List ranking and list scan on the Cray C-90

Dynamic parallel tree contraction (extended abstract)

Experiences with parallel N-body simulation

Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks

AT2 bounds for a class of VLSI problems and string matching

An Ω(√ log log n) lower bound for routing in optical networks

Programming DEC-Alpha based multiprocessors the easy way (extended abstract)

Diffracting trees (preliminary version)

On testing cache-coherent shared memories

Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?

Scheduling parallelizable tasks to minimize average response time

Job scheduling in rings

An analysis of diffusive load-balancing

Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract)

Efficient low-contention parallel algorithms

Constructive deterministic PRAM simulation on a mesh-connected computer

An optical simulation of shared memory

Construction of the mesh and the torus tolerating a large number of faults

O(log2 n) time efficient parallel factorization of dense, sparse separable, and banded matrices

How much can we speedup Gaussian elimination with pivoting?

Efficient algorithms for all-to-all communications in multi-port message-passing systems

An architecture for optimal all-to-all personalized communication

Communication efficient matrix multiplication on hypercubes

A model for multi-grained parallelism (extended abstract)

Increasing network bandwidth on meshes

Bounds on the greedy routing algorithm for array networks

Minimal adaptive routing on the mesh with bounded queue size

Segment router: a novel router design for parallel computers

AT2 bounds for a class of VLSI problems and string matching

Content Provider	ACM Digital Library
Author	Byers, John Adler, Micah
Abstract	We present a class of boolean functions which have regional mappings, a generalization of the transitivity property defined in [12]. We prove that all transitive problems have regional mappings, as do a variety of interesting computational problems such as merging two sorted lists of arbitrary length, generalized integer multiplication and matrix-vector products. We present a general area-time lower bound for VLSI implementations of problems with regional mappings and confirm that the lower bound matches the previously known bound for transitive problems. For generalized integer multiplication, we present a custom VLSI implementation which provides a matching upper bound. The results improve AT2 bounds on a number of open problems.In related work, we consider the problem of finding occurrences of a P-bit pattern in an N-bit text string. We show that every chip capable of solving this string matching problem requires AT2 = &OHgr;(PN). A custom VLSI design, using an idea similar to that used for generalized integer multiplication, provides a matching upper bound when N is polynomial in P.
Starting Page	140
Ending Page	146
Page Count	7
File Format	PDF
ISBN	0897916719
DOI	10.1145/181014.181092
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1994-08-01
Publisher Place	New York
Access Restriction	Subscribed
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

Bounds for a class of vlsi problems and string matching (1994).

Tighter Lower Bounds on the Exact Complexity of String Matching

String Matching... String Matching Problems and Bioinformatics

A Lower Bound for Parallel String Matching

Bounds for linear vlsi-layout problems (1993).

A framework for the analysis and design of algorithms for a class of VLSI-CAD optimization problems

Bounds for linear VLSI-layout problems

Tight bounds on the complexity of the Boyer-Moore string matching algorithm

Tight Comparison Bounds for the String Prefix-Matching Problem (1993)

AT2 bounds for a class of VLSI problems and string matching

Similar Documents

Bounds for a class of vlsi problems and string matching (1994).

Tighter Lower Bounds on the Exact Complexity of String Matching

String Matching... String Matching Problems and Bioinformatics

A Lower Bound for Parallel String Matching

Bounds for linear vlsi-layout problems (1993).

A framework for the analysis and design of algorithms for a class of VLSI-CAD optimization problems

Bounds for linear VLSI-layout problems

Tight bounds on the complexity of the Boyer-Moore string matching algorithm

Tight Comparison Bounds for the String Prefix-Matching Problem (1993)

AT2 bounds for a class of VLSI problems and string matching