NDLI: Shallow multiplication circuits and wise financial investments

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

Biased random walks

Approximations of general independent distributions

Sample spaces uniform on neighborhoods

Balanced matroids

Competitive algorithms for distributed data management (extended abstract)

New algorithms for an ancient scheduling problem

Alphabet independent two dimensional matching

A constant-time optimal parallel string-matching algorithm

Methods for message routing in parallel machines

Computing Frobenius maps and factoring polynomials

Parallel computation over hyperbolic groups

Structure forest and composition factors for small base groups in nearly linear time

Feasibility testing for systems of real quadratic equations

Fault tolerant planar communication networks

Existence and construction of edge disjoint paths on expander graphs

Simple algorithms for routing on butterfly networks with bounded queues

Computing with faulty arrays

Linear decision trees: volume estimates and topological bounds

Entropy and sorting

Randomized versus nondeterministic communication complexity

Exponential lower bounds for the pigeonhole principle

Finding approximate separators and computing tree width quickly

Faster algorithms for finding small edge cuts in planar graphs

The complexity of multiway cuts (extended abstract)

Graph decomposition is NPC - a complete proof of Holyer's conjecture

Online minimization of transition systems (extended abstract)

Exponential determinization for Ω-automata with strong-fairness acceptance condition (extended abstract)

A new recursion-theoretic characterization of the polytime functions (extended abstract)

Asymptomatic conditional probabilities for first-order logic

Efficient program transformations for resilient parallel computation via randomization (preliminary version)

Efficient PRAM simulation on a distributed memory machine

A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension

On the parallel complexity of computing a maximal independent set in a hypergraph

Computational learning theory: survey and selected bibliography

Learning arithmetic read-once formulas

Fast learning of k-term DNF formulas with queries

Can finite samples detect singularities of real-valued functions?

A logspace algorithm for tree canonization (extended abstract)

A hypercubic sorting network with nearly logarithmic depth

Small-depth counting networks

Shallow multiplication circuits and wise financial investments

Symmetry and complexity

When do extra majority gates help?

Representing Boolean functions as polynomials modulo composite numbers

On the degree of Boolean functions as real polynomials

On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

A subexponential randomized simplex algorithm (extended abstract)

Polynomial algorithms for linear programming over the algebraic numbers

Fully dynamic planarity testing (extended abstract)

Planar separators and parallel polygon triangulation (preliminary version)

Ray shooting and parametric search

On the angular resolution of planar graphs

Ham-sandwich cuts in $R^{d}$

A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)

Adapting to asynchronous dynamic networks (extended abstract)

Competitive distributed job scheduling (extended abstract)

Improved distributed algorithms for coloring and network decomposition problems

Efficient fault tolerant algorithms for resource allocation in distributed systems

The history and status of the P versus NP question

On the complexity of RAM with various operation sets

Average case intractability of matrix and diophantine problems (extended abstract)

On the hardness of computing the permanent of random matrices (extended abstract)

Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!

Self-stabilizing symmetry breaking in constant-space (extended abstract)

A correctness condition for high-performance multiprocessors (extended abstract)

Target shooting with programmed random variables

Communication complexity of secure computation (extended abstract)

Making zero-knowledge provers efficient

A note on efficient zero-knowledge proofs and arguments (extended abstract)

Two-prover one-round proof systems: their power and their problems (extended abstract)

On the all-pairs-shortest-path problem

A parallel randomized approximation scheme for shortest paths

Biconnectivity approximations and graph carvings

e-approximations with minimum packing constraint violation (extended abstract)

Shallow multiplication circuits and wise financial investments

Content Provider	ACM Digital Library
Author	Paterson, Michael S. Zwick, Uri
Abstract	Paterson, Pippenger and Zwick have recently obtained a general theory that describes the optimal way in which given carry-save adders can be combined into carry-save networks. Their work produces, in particular, multiplication circuits of depth 3.71 log2 n (these circuits put out two numbers whose sum is the result of the multiplication).In this work an extension of the above general theory is obtained. We now consider carry-save adders that may receive inputs and produce outputs using several different representation methods. We describe the optimal way of utilising any such collection of carry-save adders. The optimality proof uses the min-max theorem of game theory.By using several different representation standards, the depth of multiplication circuits can be surprisingly reduced to 3.48 log2 n (again two output numbers are produced). We introduce bit level redundancy by using a novel coding scheme in which each bit is distributed over four wires. Interestingly, the information on these four wires is usually not transmitted simultaneously.Finally, an analogy is made between the optimisation problem faced by the circuit designer and the optimisation problem faced by an investor, offered a collection of financial investment plans, each involving perhaps several different currencies. This analogy is used to obtain intuitive explanations of the results obtained.
Starting Page	429
Ending Page	438
Page Count	10
File Format	PDF
ISBN	0897915119
DOI	10.1145/129712.129753
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-07-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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