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

 
$
%
123
 
 
 
 
 
 
 
 
 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
TopicUpdates neededRelated articlesStatus
Person working on it currently
2
3
Adaptive data analysisDoes not exist -- needs a new articleunclaimed
4
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
5
Algorithmic Game TheoryMore citations, expansion of list of subtopics and their descriptions, stylistic improvementsunclaimed
6
Boolean Function AnalysisDoes not exist -- needs a new articlePseudo-Boolean functionfinishedYuval Filmus
7
Computational hardness assumptionNeeds to be fleshed out.finishedAviad Rubinstein
8
Correlation ClusteringExpansion of what's known for variantsunclaimed
9
Decision tree modelNeeds to be updated to reflect recent results, especially the "Relationship between different models" sectionunclaimed
10
Differential privacyArticle is generally poorly written.unclaimed
11
Distribution (property) testingDoes not exist -- needs a new articleunclaimed
12
Downward separationDoes not exist — needs a new article
13
Dynamic ProgrammingNeeds citationsunclaimed
14
Fast matrix multiplicationMentioned in article on "Coppersmith Winograd algorithm"; needs a separate article
Coppersmith-Winograd algorithm
unclaimed
15
Flow–cut gapDoes not exist — needs a new articleGNRS conjecture
16
Frequent item detection ("heavy hitters")
Mentioned in a list of related algorithms in "streaming algorithms"; needs a separate article
Streaming algorithmunclaimed
17
Group isomorphism problemNeeds to be fleshed out - currently only talks about uncomputability of isomorphism for finitely presented groups, nothing about other variants with important complexity aspectsunclaimed
18
Hardness of approximationToo short -- needs expansionunclaimed
19
Information complexityDoes not exist -- needs a new articleunclaimed
20
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
21
Junta problemDoes not exist -- needs a new articleThe junta problemunclaimed
22
Laplacian SolverDoes not exist — needs a new article
https://en.wikipedia.org/wiki/System_of_linear_equations, https://en.wikipedia.org/wiki/Electric_current
unclaimed
23
Lattice-based cryptographyfinishedNoah Stephens-Davidowitz
24
Linearity testingDoes not exist — needs a new article
25
Log rank conjectureMentioned in "Communication Complexity"; needs a separate articleCommunication Complexityunclaimed
26
Metric Embedding TheoryDoes not exist.Stretch factorunclaimed
27
Polynomial identity testingExpansion of what's known for special cases; needs citations; improvement of discussion of its relationship to other areasunclaimed
28
Primal-dual approximationDoes not exist -- needs a new articleunclaimed
29
Proof complexityWriting and exposition could use improvement. (Note added by Iddo Tzameret: I have edited a year ago the preabmle [i.e., first few paragraphs], which provides a high level exposition of the field; but anything below the Contents has not been touched and should probably be improved or changed).unclaimed
30
Prophet inequalityDoes not exist -- needs a new articleunclaimed
31
Pseudo-polynomial timeNeeds expansion of numerical examples like knapsack or subset sum
32
Randomized rounding"might be confusing or unclear to some readers"
the method of conditional probabilities, the probabilistic method
finishedNeal Young
33
Semidefinite approximationListed in semidefinite programming but needs separate articleSemidefinite programmingunclaimed
34
Smoothed analysisToo short -- needs expansionunclaimed
35
Space complexityVery short article needs expansion
36
Steinitz Problem/ConjectureDoes not exist. See https://users.renyi.hu/~barany/cikkek/steinitz.pdf
37
The method of conditional probabilities
randomized roundingfinishedNeal Young
38
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
39
Word RAM model of computingToo short -- needs expansionunclaimed
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...