SESSION 2: INVITED PLENARY ABSTRACT
Who Says You Have to Look at the Input? The Brave New World of Sublinear Computing Bernard Chazelle Princeton University and NEC Laboratories America, Inc. Surprisingly often, a computational problem will come up for which sampling a vanishing fraction of the input is sufficient to obtain excellent approximate answers. How is that possible? Which sort of problems fall into that category? What are the techniques known to make this "sublinearity" phenomenon happen? This talk will address each of these questions briefly by looking at specific examples.
Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

141