X
Search Filters
Format Format
Subjects Subjects
Subjects Subjects
X
Sort by Item Count (A-Z)
Filter by Count
computer science (36) 36
computer science, theory & methods (22) 22
hardness of approximation (22) 22
approximation algorithms (21) 21
algorithms (17) 17
polynomials (17) 17
hardness (16) 16
mathematics, applied (15) 15
computational complexity (14) 14
pcp (13) 13
approximation (12) 12
mathematical analysis (9) 9
mathematics (9) 9
algorithm analysis and problem complexity (8) 8
inapproximability (8) 8
lattices (8) 8
computer science - computational complexity (7) 7
discrete mathematics in computer science (7) 7
games (7) 7
semidefinite programming (7) 7
studies (7) 7
proofs (6) 6
unique games conjecture (6) 6
boolean functions (5) 5
computer science, hardware & architecture (5) 5
forge furnaces (5) 5
forging (5) 5
hammering (5) 5
learning (5) 5
linear equations (5) 5
mathematical models (5) 5
mechanical metal-working without essentially removingmaterial (5) 5
pcps (5) 5
performing operations (5) 5
pressing metal (5) 5
punching metal (5) 5
riveting (5) 5
transporting (5) 5
unique games (5) 5
actuating-floats (4) 4
applied mathematics (4) 4
biomass (4) 4
blasting (4) 4
cocks (4) 4
computation (4) 4
computation by abstract devices (4) 4
computational theory and mathematics (4) 4
computer communication networks (4) 4
computer networks and communications (4) 4
computer science, software engineering (4) 4
constants (4) 4
devices for venting or aerating (4) 4
educational institutions (4) 4
engineering elements and units (4) 4
equations (4) 4
general measures for producing and maintaining effectivefunctioning of machines or installations (4) 4
geometry (4) 4
halfspaces (4) 4
heating (4) 4
lighting (4) 4
making forged or pressed metal products, e.g. horse-shoes,rivets, bolts or wheels (4) 4
mechanical engineering (4) 4
probabilistically checkable proofs (4) 4
shortest vector problem (4) 4
taps (4) 4
theoretical computer science (4) 4
thermal insulation in general (4) 4
user-generated content (4) 4
valves (4) 4
vectors (4) 4
weapons (4) 4
2-to-2 games (3) 3
algorithm design and analysis (3) 3
analysis (3) 3
artificial intelligence (3) 3
biodiesel (3) 3
biodiesel fuels (3) 3
biotechnology & applied microbiology (3) 3
books (3) 3
classification (3) 3
color (3) 3
coloring (3) 3
cryptography (3) 3
decision tree complexity (3) 3
engineering profession (3) 3
evasiveness (3) 3
fuel properties (3) 3
gaussian processes (3) 3
grassmann graph (3) 3
hypercubes (3) 3
hypergraph vertex cover (3) 3
inequality (3) 3
integrality gap (3) 3
linear code (3) 3
mathematical problems (3) 3
mechanical properties (3) 3
monotone graph properties (3) 3
np-complete problem (3) 3
numeric computing (3) 3
oleaginous fungi (3) 3
more...
Language Language
Publication Date Publication Date
Click on a bar to filter by decade
Slide to change publication date range


SIAM Journal on Computing, ISSN 0097-5397, 2006, Volume 36, Issue 4, pp. 1025 - 1071
Assuming that NP not subset of boolean AND(epsilon>0) BPTIME(2(n epsilon)), we show that graph min-bisection, dense k-subgraph, and bipartite clique have no... 
Approximation algorithms | Probabilistically checkable proofs (PCPs) | Hardness of approximation | MATHEMATICS, APPLIED | PROOFS | PCPS | APPROXIMATION | probabilistically checkable proofs (PCPs) | hardness of approximation | COMPUTER SCIENCE, THEORY & METHODS | approximation algorithms | HARDNESS
Journal Article
SIAM Journal on Computing, ISSN 0097-5397, 2017, Volume 46, Issue 1, pp. 235 - 271
Journal Article
SIAM Journal on Computing, ISSN 0097-5397, 01/2017, Volume 46, Issue 1, pp. 235 - 271
Journal Article
2010 IEEE 25th Annual Conference on Computational Complexity, ISSN 1093-0159, 06/2010, pp. 99 - 121
This article surveys recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis,... 
Algorithm design and analysis | Computational geometry | Engineering profession | User-generated content | Approximation algorithms | Hypercubes | Polynomials | NP-complete problem | Computational complexity | Programming profession
Conference Proceeding
Journal of Computer and System Sciences, ISSN 0022-0000, 2008, Volume 74, Issue 3, pp. 335 - 349
Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th... 
Vertex cover | Unique games conjecture | Hardness of approximation | hardness of approximation | unique games conjecture | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | COMPUTER SCIENCE, THEORY & METHODS | vertex cover
Journal Article
SIAM Journal on Computing, ISSN 0097-5397, 2007, Volume 37, Issue 1, pp. 319 - 357
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of alpha(GW) + is an element of for... 
Constraint satisfaction | MAX-CUT | Unique games | Hardness of approximation | MATHEMATICS, APPLIED | SPACES | INEQUALITY | hardness of approximation | THRESHOLD | APPROXIMATION ALGORITHMS | constraint satisfaction | Unique Games | BOOLEAN FUNCTIONS | OPTIMIZATION | VARIABLES | COMPUTER SCIENCE, THEORY & METHODS
Journal Article
2011, Lecture Notes in Computer Science, ISBN 3642220053, Volume 6755, Issue 1
We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over $\mathbb{F}_2$ . We also show how to extend... 
Computation by Abstract Devices | Discrete Mathematics in Computer Science | Algorithm Analysis and Problem Complexity | Computer Communication Networks | Computer Science | Information Storage and Retrieval
Book Chapter
Proceedings of the forty-eighth annual ACM symposium on theory of computing, ISSN 0737-8017, 06/2016, Volume 19-21-, pp. 63 - 76
Conference Proceeding
SIAM Journal on Computing, ISSN 0097-5397, 01/2013, Volume 42, Issue 3, pp. 752 - 791
  In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most... 
Computation | Mathematical analysis | Linearity | Games | Constants | Mathematical models | Gaussian | Linear equations
Journal Article
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969, 08/2016, Volume 57
Conference Proceeding
Leibniz International Proceedings in Informatics, LIPIcs, ISSN 1868-8969, 09/2016, Volume 60
Conference Proceeding
Journal of the Association for Computing Machinery, ISSN 0004-5411, 02/2015, Volume 62, Issue 1, p. 8
Journal Article
Association for Computing Machinery. Journal of the Association for Computing Machinery, ISSN 0004-5411, 02/2015, Volume 62, Issue 1, p. 1
  This article disproves a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ... with constant distortion. This paper shows... 
Studies | Mathematical problems | Computer science | Embedded systems | Simulation | Proof theory
Journal Article
Journal of the ACM, ISSN 0004-5411, 02/2015, Volume 62, Issue 1, pp. 1 - 39
In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into Y sub(1) with constant distortion. We show... 
Reduction | Construction | Embedded systems | Equivalence | Games | Distortion | Constants | Hardness
Journal Article
Proceedings of the 49th Annual ACM SIGACT Symposium on theory of computing, ISSN 0737-8017, 06/2017, Volume 128415, pp. 576 - 589
We present a candidate reduction from the 3-Lin problem to the 2-to-2 Games problem and present a combinatorial hypothesis about Grassmann graphs which, if... 
PCP | Vertex-Cover | Unique Games | Unique games
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, 2015, Volume 9134, pp. 822 - 833
Conference Proceeding
IEEE Transactions on Information Theory, ISSN 0018-9448, 10/2014, Volume 60, Issue 10, pp. 6636 - 6645
Journal Article
Journal of the ACM (JACM), 03/2015, Volume 62, Issue 1, pp. 1 - 39
In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into 1 with constant distortion. We show that... 
semidefinite programming | unique games conjecture | negative-type metrics | sparsest cut | integrality gap | hardness of approximation | Metric embeddings
Journal Article
No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.