TCS Wikipedia articles needing work
Comments
 Share
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

 
$
%
123
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Still loading...
ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
TopicUpdates neededRelated articlesStatus
Person working on it currently
2
3
Algorithmic Game TheoryMore citations, expansion of list of subtopics and their descriptions, stylistic improvementsunclaimed
4
Boolean Function AnalysisDoes not exist -- needs a new articlePseudo-Boolean functionin progressYuval Filmus
5
Correlation ClusteringExpansion of what's known for variantsunclaimed
6
Dynamic ProgrammingNeeds citationsunclaimed
7
Fast matrix multiplicationMentioned in article on "Coppersmith Winograd algorithm"; needs a separate article
Coppersmith-Winograd algorithm
unclaimed
8
Frequent item detection ("heavy hitters")
Mentioned in a list of related algorithms in "streaming algorithms"; needs a separate article
Streaming algorithmunclaimed
9
Hardness of approximationToo short -- needs expansionunclaimed
10
Integrality gapMentioned in "Linear Programming Relaxation"; needs a separate article, especially because it also applies to semi-definite relaxations, e.g.
Linear programming relaxation
unclaimed
11
Junta problemDoes not exist -- needs a new articleThe junta problemunclaimed
12
Log rank conjectureMentioned in "Communication Complexity"; needs a separate articleCommunication Complexityunclaimed
13
Primal-dual approximationDoes not exist -- needs a new articleunclaimed
14
Prophet inequalityDoes not exist -- needs a new articleunclaimed
15
Semidefinite approximationListed in semidefinite programming but needs separate articleSemidefinite programmingunclaimed
16
Smoothed analysisToo short -- needs expansionunclaimed
17
Word RAM model of computingDoes not exist -- needs a new articleunclaimed
18
Information complexityDoes not exist -- needs a new articleunclaimed
19
Weisfeiler-Lehman method for graph iso
Does not exist -- needs a new article (or at least a section in the GI article)Graph Isomorphism problemunclaimed
20
Proof complexityWriting and exposition could use improvementunclaimed
21
Algebraic proof complexityDoes not exist -- needs a new article (or at least a section in the proof complexity article)
https://en.wikipedia.org/wiki/Proof_complexity, https://en.wikipedia.org/wiki/Hilbert%27s_Nullstellensatz#Effective_Nullstellensatz
unclaimed
22
Polynomial identity testingExpansion of what's known for special cases; needs citations; improvement of discussion of its relationship to other areasunclaimed
23
Differential privacyArticle is generally poorly written.unclaimed
24
Adaptive data analysisDoes not exist -- needs a new articleunclaimed
25
Computational hardness assumptionNeeds to be fleshed out.unclaimed
26
Lattice-based cryptographyin progressNoah Stephens-Davidowitz
27
Metric Embedding TheoryDoes not exist.Stretch factorunclaimed
28
Pseudo-polynomial timeNeeds expansion of numerical examples like knapsack or subset sum
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Loading...
 
 
 
Sheet1