Zero knowledge and the chromatic number (Q1276168): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2058422149
@@ Property / OpenAlex ID: W2058422149 / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomized graph products
@@ Property / cites work: Derandomized graph products / rank @@
+Normal rank
@@ Property / cites work @@
+Q4004078
@@ Property / cites work: Q4004078 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230322
@@ Property / cites work: Q4230322 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230321
@@ Property / cites work: Q4230321 / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Efficient probabilistically checkable proofs and applications to approximations
+Normal rank
@@ Property / cites work @@
+Improved non-approximability results
@@ Property / cites work: Improved non-approximability results / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of approximating the independent set problem
+Normal rank
@@ Property / cites work @@
+Approximating maximum independent sets by excluding subgraphs
+Normal rank
@@ Property / cites work @@
+Q4318695
@@ Property / cites work: Q4318695 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized graph products, chromatic numbers, and Lovasz j-function
+Normal rank
@@ Property / cites work @@
+Interactive proofs and the hardness of approximating cliques
+Normal rank
@@ Property / cites work @@
+Two prover protocols
@@ Property / cites work: Two prover protocols / rank @@
+Normal rank
@@ Property / cites work @@
+Q4252726
@@ Property / cites work: Q4252726 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Near-Optimal Graph Coloring
@@ Property / cites work: The Complexity of Near-Optimal Graph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
+Normal rank
@@ Property / cites work @@
+A still better performance guarantee for approximate graph coloring
+Normal rank
@@ Property / cites work @@
+Q4228449
@@ Property / cites work: Q4228449 / rank @@
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4864429
@@ Property / cites work: Q4864429 / rank @@
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimization problems
+Normal rank
@@ Property / cites work @@
+The hardness of approximation: Gap location
@@ Property / cites work: The hardness of approximation: Gap location / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234093
@@ Property / cites work: Q4234093 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1276168