Aviad Rubinstein - Hardness of Approximation Between P and NP

Hardness of Approximation Between P and NP

ACM Books

Editor in Chief

M. Tamer zsu, University of Waterloo

ACM Books is a series of high-quality books for the computer science community, published by ACM and many in collaboration with Morgan & Claypool Publishers. ACM Books publications are widely distributed in both print and digital formats through booksellers and to libraries (and library consortia) and individual ACM members via the ACM Digital Library platform.

Hardness of Approximation Between P and NP

Aviad Rubinstein, Stanford University

2019

Conversational UX Design: A Practitioners Guide to the Natural Conversation Framework

Robert J. Moore, IBM ResearchAlmaden

Raphael Arar, IBM ResearchAlmaden

2019

Heterogeneous Computing: Hardware and Software Perspectives

Mohamed Zahran, New York University

2019

Making Databases Work: The Pragmatic Wisdom of Michael Stonebraker

Editor: Michael L. Brodie

2018

The Handbook of Multimodal-Multisensor Interfaces, Volume 2: Signal Processing, Architectures, and Detection of Emotion and Cognition

Editors: Sharon Oviatt, Monash University

Bjrn Schuller, University of Augsburg and Imperial College London

Philip R. Cohen, Monash University

Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)

Gerasimos Potamianos, University of Thessaly

Antonio Krger, Saarland University and German Research Center for Artificial Intelligence (DFKI)

2018

Declarative Logic Programming: Theory, Systems, and Applications

Editors: Michael Kifer, Stony Brook University

Yanhong Annie Liu, Stony Brook University

2018

The Sparse Fourier Transform: Theory and Practice

Haitham Hassanieh, University of Illinois at Urbana-Champaign

2018

The Continuing Arms Race: Code-Reuse Attacks and Defenses

Editors: Per Larsen, Immunant, Inc.

Ahmad-Reza Sadeghi, Technische Universitt Darmstadt

2018

Frontiers of Multimedia Research

Editor: Shih-Fu Chang, Columbia University

2018

Shared-Memory Parallelism Can Be Simple, Fast, and Scalable

Julian Shun, University of California, Berkeley

2017

Computational Prediction of Protein Complexes from Protein Interaction Networks

Sriganesh Srihari, The University of Queensland Institute for Molecular Bioscience

Chern Han Yong, Duke-National University of Singapore Medical School

Limsoon Wong, National University of Singapore

2017

The Handbook of Multimodal-Multisensor Interfaces, Volume 1: Foundations, User Modeling, and Common Modality Combinations

Editors: Sharon Oviatt, Incaa Designs

Bjrn Schuller, University of Passau and Imperial College London

Philip R. Cohen, Voicebox Technologies

Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)

Gerasimos Potamianos, University of Thessaly

Antonio Krger, Saarland University and German Research Center for Artificial Intelligence (DFKI)

2017

Communities of Computing: Computer Science and Society in the ACM

Thomas J. Misa, Editor, University of Minnesota

2017

Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining

ChengXiang Zhai, University of Illinois at UrbanaChampaign

Sean Massung, University of Illinois at UrbanaChampaign

2016

An Architecture for Fast and General Data Processing on Large Clusters

Matei Zaharia, Stanford University

2016

Reactive Internet Programming: State Chart XML in Action

Franck Barbier, University of Pau, France

2016

Verified Functional Programming in Agda

Aaron Stump, The University of Iowa

2016

The VR Book: Human-Centered Design for Virtual Reality

Jason Jerald, NextGen Interactions

2016

Adas Legacy: Cultures of Computing from the Victorian to the Digital Age

Robin Hammerman, Stevens Institute of Technology

Andrew L. Russell, Stevens Institute of Technology

2016

Edmund Berkeley and the Social Responsibility of Computer Professionals

Bernadette Longo, New Jersey Institute 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 meanselectronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviewswithout 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

books.acm.org

http://books.acm.org

ISBN: 978-1-94748-723-9hardcover

ISBN: 978-1-94748-720-8paperback

ISBN: 978-1-94748-722-2ePub

ISBN: 978-1-94748-721-5eBook

Series ISSN: 2374-6769 print2374-6777 electronic

DOIs:

10.1145/3241304 Book

10.1145/3241304.3241305

10.1145/3241304.3241306

10.1145/3241304.3241307

10.1145/3241304.3241308

10.1145/3241304.3241309

10.1145/3241304.3241310

10.1145/3241304.3241311

10.1145/3241304.3241312

10.1145/3241304.3241313

10.1145/3241304.3241314

10.1145/3241304.3241315

10.1145/3241304.3241316

10.1145/3241304.3241317

10.1145/3241304.3241318

10.1145/3241304.3241319

10.1145/3241304.3241320

10.1145/3241304.3241321

10.1145/3241304.3241322

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 Z Z T E X.

First Edition

10 9 8 7 6 5 4 3 2 1

Contents

Preface

This book is based on my Ph.D. thesis (by the same title), which I wrote at the University of California, Berkeley, with the wise guidance of Christos Papadimitriou.