Back to Results
First PageMeta Content
Mathematics / MAX-3SAT / Constraint satisfaction problem / 2-satisfiability / Constraint satisfaction / Decomposition method / Local consistency / Constraint programming / Theoretical computer science / Applied mathematics


Beating the random assignment on constraint satisfaction problems of bounded degree Boaz Barak∗ arXiv:1505.03424v1 [cs.CC] 13 May 2015
Add to Reading List

Document Date: 2015-05-13 20:27:45

Open Document

File Size: 278,29 KB

Share Result on Facebook

Company

AE ( x1 y2 x3 ) AE / 3Sat / NAE ( x1 x2 x3 ) AE / NAE (y1 y2 x3 ) AE / Computer Sciences / /

Facility

Cornell University / Courant Institute of Mathematical Sciences / New York University / /

IndustryTerm

classical algorithm / classical algorithms / quantum algorithm / /

Organization

Carnegie Mellon / New York University / Department of Electrical Engineering & Computer Sciences / Department of Computer Science / Mathematics Department / Courant Institute of Mathematical Sciences / MIT / Cornell University / /

Person

Prasad Raghavendra§ Aravindan Vijayaraghavan / David Witmer‡ Prasad Raghavendra / Luca Trevisan§ David Witmer / Oded Regev¶ Ankur Moitra / David Steurerk Ryan / Boaz Barak / /

ProvinceOrState

Oregon / /

Region

New England / /

Technology

three algorithms / randomized algorithm / quantum algorithm / /

URL

http /

SocialTag