NDLI: More on average case vs approximation complexity

Content Provider	IEEE Xplore Digital Library
Author	Alekhnovich, M.
Copyright Year	2003
Description	Author affiliation: Lab. for Comput. Sci., MIT, Cambridge, MA, USA (Alekhnovich, M.)
Abstract	We consider the problem to determine the maximal number of satisfiable equations in a linear system chosen at random. We make several plausible conjectures about the average case hardness of this problem for some natural distributions on the instances, and relate them to several interesting questions in the theory of approximation algorithms and in cryptography. Namely we show that our conjectures imply the following facts: (1) Feige's hypothesis about the hardness of refuting a random 3CNF is true, which in turn implies inapproximability within a constant for several combinatorial problems, for which no NP-hardness of approximation is known. (2) It is hard to approximate the nearest codeword within factor n/sup 1 - /spl epsi//. (3) It is hard to estimate the rigidity of a matrix. More exactly, it is hard to distinguish between matrices of low rigidity and random ones. (4) There exists a secure public-key (probabilistic) cryptosystem, based on the intractability of decoding of random binary codes. Our conjectures are strong in that they assume cryptographic hardness: no polynomial algorithm can solve the problem on any non-negligible fraction of inputs. Nevertheless, to the best of our knowledge no efficient algorithms are currently known that refute any of our hardness conjectures.
Sponsorship	IEEE Comput. Soc. Tech. Soc. on Found. Comput
Starting Page	298
Ending Page	307
File Size	351136
Page Count	10
File Format	PDF
ISBN	0769520405
ISSN	02725428
DOI	10.1109/SFCS.2003.1238204
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-10-11
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer aided software engineering Cryptography Decoding Equations Linear systems Approximation algorithms Polynomials Computer science NP-complete problem Public key
Content Type	Text
Resource Type	Article

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

LR(k) testing is average case complete

The computational complexity of simultaneous Diophantine approximation problems

Relativized Separations of Worst-Case and Average-Case Complexities for NP

Average-case Complexity

A new public-key cipher system based upon the diophantine equations

On average P vs. average NP

Approximation Algorithms

Average-case computations - comparing AvgP, HP, and nearly-P

On worst-case to average-case reductions for NP problems

More on average case vs approximation complexity

Similar Documents

LR(k) testing is average case complete

The computational complexity of simultaneous Diophantine approximation problems

Relativized Separations of Worst-Case and Average-Case Complexities for NP

Average-case Complexity

A new public-key cipher system based upon the diophantine equations

On average P vs. average NP

Approximation Algorithms

Average-case computations - comparing AvgP, HP, and nearly-P

On worst-case to average-case reductions for NP problems

More on average case vs approximation complexity