A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | Topic | Updates needed | Related articles | Status | Person working on it currently | |||||||||||||||||||||

2 | ||||||||||||||||||||||||||

3 | Adaptive data analysis | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

4 | Algebraic proof complexity | Does 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 Theory | More citations, expansion of list of subtopics and their descriptions, stylistic improvements | in progress | Shuchi Chawla | ||||||||||||||||||||||

6 | Bin covering | Does not exist -- needs a new article | ||||||||||||||||||||||||

7 | Boolean Function Analysis | Does not exist -- needs a new article | Pseudo-Boolean function | finished | Yuval Filmus | |||||||||||||||||||||

8 | Computational hardness assumption | Needs to be fleshed out. | finished | Aviad Rubinstein | ||||||||||||||||||||||

9 | Correlation Clustering | Expansion of what's known for variants | unclaimed | |||||||||||||||||||||||

10 | Decision tree model | Needs to be updated to reflect recent results, especially the "Relationship between different models" section | in progress | Nikhil Mande, Suhail Sherif | ||||||||||||||||||||||

11 | Differential privacy | Article is generally poorly written. | finished | |||||||||||||||||||||||

12 | Distribution (property) testing | Does not exist -- needs a new article | unclaimed | 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 separation | Does not exist — needs a new article | ||||||||||||||||||||||||

14 | Dynamic Programming | Needs citations | unclaimed | |||||||||||||||||||||||

15 | Fast matrix multiplication | Mentioned in article on "Coppersmith Winograd algorithm"; needs a separate article | Coppersmith-Winograd algorithm | unclaimed | ||||||||||||||||||||||

16 | Flow–cut gap | Does not exist — needs a new article | GNRS conjecture | |||||||||||||||||||||||

17 | Forrelation | Does 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 algorithm | unclaimed | ||||||||||||||||||||||

19 | Group isomorphism problem | Needs to be fleshed out - currently only talks about uncomputability of isomorphism for finitely presented groups, nothing about other variants with important complexity aspects | unclaimed | |||||||||||||||||||||||

20 | Hardness of approximation | Too short -- needs expansion | unclaimed | |||||||||||||||||||||||

21 | Information complexity | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

22 | Integrality gap | Mentioned 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 problem | Does not exist -- needs a new article | The junta problem | unclaimed | ||||||||||||||||||||||

24 | Laplacian Solver | Does 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 cryptography | finished | Noah Stephens-Davidowitz | |||||||||||||||||||||||

26 | Linearity testing | Does not exist — needs a new article | ||||||||||||||||||||||||

27 | Log rank conjecture | Mentioned in "Communication Complexity"; needs a separate article | Communication Complexity | finished | Nikhil Mande, Suhail Sherif, Yuval Filmus | |||||||||||||||||||||

28 | Metric Embedding Theory | Does not exist. | Stretch factor | unclaimed | ||||||||||||||||||||||

29 | Mirror descent | Does not exist -- needs a new article | ||||||||||||||||||||||||

30 | Multiplayer game | Does not exist -- maybe needs a new article | Parallel Repetition | unclaimed | ||||||||||||||||||||||

31 | Parallel repetition | Does not exist -- needs a new article; should have counterexamples, mention Raz's theorem, counterexamples for computationally sound protocols | in progress | Justin Holmgren (justin.holmgren@gmail.com) | ||||||||||||||||||||||

32 | Polynomial identity testing | Expansion of what's known for special cases; needs citations; improvement of discussion of its relationship to other areas | unclaimed | |||||||||||||||||||||||

33 | Price of stability | Missing citations | ||||||||||||||||||||||||

34 | Primal-dual approximation | Does not exist -- needs a new article | in progress | evagelia | ||||||||||||||||||||||

35 | Proof complexity | Writing 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 inequality | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

37 | Pseudo-polynomial time | Needs expansion of numerical examples like knapsack or subset sum | in progress | Manish Purohit | I did an edit here, sorry! -Ewin | |||||||||||||||||||||

38 | Raghavendra's theorem | Does 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 | finished | Neal Young | |||||||||||||||||||||

40 | Semidefinite approximation | Listed in semidefinite programming but needs separate article | Semidefinite programming | unclaimed | ||||||||||||||||||||||

41 | Smoothed analysis | Too short -- needs expansion | finished | Sophie Huiberts | ||||||||||||||||||||||

42 | Space complexity | Very short article needs expansion | finished | Ewin | ||||||||||||||||||||||

43 | Spira's theorem | Does not exist -- needs a new article | ||||||||||||||||||||||||

44 | Steinitz Problem/Conjecture | Does not exist. See https://users.renyi.hu/~barany/cikkek/steinitz.pdf | ||||||||||||||||||||||||

45 | Sum-of-squares optimization | Needs 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 exist | Oded Regev | |||||||||||||||||||||||

47 | The method of conditional probabilities | randomized rounding | finished | Neal 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 problem | unclaimed | ||||||||||||||||||||||

49 | Word RAM model of computing | Too short -- needs expansion | unclaimed | |||||||||||||||||||||||

50 | Very sparse; needs more detail, subareas, etc. | |||||||||||||||||||||||||

51 | Sparsest cut problem | Currently a redirect to a short section within https://en.wikipedia.org/wiki/Cut_(graph_theory) — needs a separate article | ||||||||||||||||||||||||

52 | Complexity of Graph Reconstruction | Needs 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...