of Technology
2015
Candidate Multilinear Maps
Sanjam Garg, University of California, Berkeley
2015
Smarter Than Their Machines: Oral Histories of Pioneers in Interactive Computing
John Cullinane, Northeastern University; Mossavar-Rahmani Center for Business and Government, John F. Kennedy School of Government, Harvard University
2015
A Framework for Scientific Discovery through Video Games
Seth Cooper, University of Washington
2014
Trust Extension as a Mechanism for Secure Code Execution on Commodity Computers
Bryan Jeffrey Parno, Microsoft Research
2014
Embracing Interference in Wireless Systems
Shyamnath Gollakota, University of Washington
2014
Hardness of Approximation Between P and NP
Aviad Rubinstein
Stanford University
ACM Books #24
Copyright © 2019 by Association for Computing Machinery and Morgan & Claypool Publishers
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews—without the prior permission of the publisher.
Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which the Association for Computing Machinery is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
Hardness of Approximation Between P and NP
Aviad Rubinstein
ISBN: 978-1-94748-723-9 hardcover
ISBN: 978-1-94748-720-8 paperback
ISBN: 978-1-94748-722-2 ePub
ISBN: 978-1-94748-721-5 eBook
Series ISSN: 2374-6769 print 2374-6777 electronic
DOIs:
10.1145/3241304 Book
10.1145/3241304.3241305 Preface
10.1145/3241304.3241306 Chapter 1
10.1145/3241304.3241307 Chapter 2
10.1145/3241304.3241308 Chapter 3
10.1145/3241304.3241309 Chapter 4
10.1145/3241304.3241310 Chapter 5
10.1145/3241304.3241311 Chapter 6
10.1145/3241304.3241312 Chapter 7
10.1145/3241304.3241313 Chapter 8
10.1145/3241304.3241314 Chapter 9
10.1145/3241304.3241315 Chapter 10
10.1145/3241304.3241316 Chapter 11
10.1145/3241304.3241317 Chapter 12
10.1145/3241304.3241318 Chapter 13
10.1145/3241304.3241319 Chapter 14
10.1145/3241304.3241320 Chapter 15
10.1145/3241304.3241321 Chapter 16
10.1145/3241304.3241322 References/Index/Bios
A publication in the ACM Books series, #24
Editor in Chief: M. Tamer Özsu, University of Waterloo
This book was typeset in Arnhem Pro 10/14 and Flama using ZZTEX.
First Edition
10 9 8 7 6 5 4 3 2 1
Contents
| Preface | |
| Acknowledgments | |
| PART I | OVERVIEW |
|
|
