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 improvementsin progressShuchi Chawla
6
Bin coveringDoes not exist -- needs a new article
7
Boolean Function AnalysisDoes not exist -- needs a new articlePseudo-Boolean functionfinishedYuval Filmus
8
Computational hardness assumptionNeeds to be fleshed out.finishedAviad Rubinstein
9
Correlation ClusteringExpansion of what's known for variantsunclaimed
10
Decision tree modelNeeds to be updated to reflect recent results, especially the "Relationship between different models" sectionin progressNikhil Mande, Suhail Sherif
11
Differential privacyArticle is generally poorly written.finished
12
Distribution (property) testingDoes not exist -- needs a new articleunclaimed
is this already completed? https://en.wikipedia.org/wiki/Property_testing
no: property testing is more general, distribution testing is a subfield (different by many aspects)
13
Downward separationDoes not exist — needs a new article
14
Dynamic ProgrammingNeeds citationsunclaimed
15
Fast matrix multiplication
Mentioned in article on "Coppersmith Winograd algorithm"; needs a separate article
Coppersmith-Winograd algorithm
unclaimed
16
Flow–cut gapDoes not exist — needs a new articleGNRS conjecture
17
ForrelationDoes not exist -- needs a new article
18
Frequent item detection ("heavy hitters")
Mentioned in a list of related algorithms in "streaming algorithms"; needs a separate article
Streaming algorithmunclaimed
19
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
20
Hardness of approximationToo short -- needs expansionunclaimed
21
Information complexityDoes not exist -- needs a new articleunclaimed
22
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
23
Junta problemDoes not exist -- needs a new articleThe junta problemunclaimed
24
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
25
Lattice-based cryptographyfinishedNoah Stephens-Davidowitz
26
Linearity testingDoes not exist — needs a new article
27
Log rank conjectureMentioned in "Communication Complexity"; needs a separate articleCommunication Complexityfinished
Nikhil Mande, Suhail Sherif, Yuval Filmus
28
Metric Embedding TheoryDoes not exist.Stretch factorunclaimed
29
Mirror descentDoes not exist -- needs a new article
30
Multiplayer gameDoes not exist -- maybe needs a new articleParallel Repetitionunclaimed
31
Parallel repetitionDoes not exist -- needs a new article; should have counterexamples, mention Raz's theorem, counterexamples for computationally sound protocolsin progress
Justin Holmgren (justin.holmgren@gmail.com)
32
Polynomial identity testingExpansion of what's known for special cases; needs citations; improvement of discussion of its relationship to other areasunclaimed
33
Price of stabilityMissing citations
34
Primal-dual approximationDoes not exist -- needs a new articlein progressevagelia
35
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
36
Prophet inequalityDoes not exist -- needs a new articleunclaimed
37
Pseudo-polynomial timeNeeds expansion of numerical examples like knapsack or subset sumin progressManish Purohit
I did an edit here, sorry! -Ewin
38
Raghavendra's theoremDoes not exist
Hardness of approximation, Unique games conjecture
39
Randomized rounding"might be confusing or unclear to some readers"
the method of conditional probabilities, the probabilistic method
finishedNeal Young
40
Semidefinite approximationListed in semidefinite programming but needs separate articleSemidefinite programmingunclaimed
41
Smoothed analysisToo short -- needs expansionfinishedSophie Huiberts
42
Space complexityVery short article needs expansionfinishedEwin
43
Spira's theoremDoes not exist -- needs a new article
44
Steinitz Problem/ConjectureDoes not exist. See https://users.renyi.hu/~barany/cikkek/steinitz.pdf
45
Sum-of-squares optimizationNeeds sections on 1. Approximation Algorithms via Sum-of-Squares and 2. Distributional Problema via Sum-of-Squares 3. Relationship to Proof Complexity
https://en.wikipedia.org/wiki/Sum-of-squares_optimization
unclaimed
46
TCS+does not existOded Regev
47
The method of conditional probabilitiesrandomized roundingfinishedNeal Young
48
Weisfeiler–Leman method for graph isomorphism
Does not exist -- needs a new article (or at least a section in the GI article)Graph Isomorphism problemunclaimed
49
Word RAM model of computingToo short -- needs expansionunclaimed
50
Very sparse; needs more detail, subareas, etc.
51
Sparsest cut problemCurrently a redirect to a short section within https://en.wikipedia.org/wiki/Cut_(graph_theory) — needs a separate article
52
Complexity of Graph ReconstructionNeeds new section on complexity aspects (cf. Kratsch-Hemaspaandra '94 and https://doi.org/10.1016/j.dam.2006.04.038)Reconstruction Conjecture
53
Linear time deterministic selection algorithm
No separate page
Selection algorithm, Quickselect, Median of medians
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...