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 | unclaimed | |||||||||||||||||||||||

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

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

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

9 | Decision tree model | Needs to be updated to reflect recent results, especially the "Relationship between different models" section | unclaimed | |||||||||||||||||||||||

10 | Differential privacy | Article is generally poorly written. | unclaimed | |||||||||||||||||||||||

11 | Distribution (property) testing | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

12 | Downward separation | Does not exist — needs a new article | ||||||||||||||||||||||||

13 | Dynamic Programming | Needs citations | unclaimed | |||||||||||||||||||||||

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

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

16 | Frequent item detection ("heavy hitters") | Mentioned in a list of related algorithms in "streaming algorithms"; needs a separate article | Streaming algorithm | unclaimed | ||||||||||||||||||||||

17 | 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 | |||||||||||||||||||||||

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

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

20 | 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 | ||||||||||||||||||||||

21 | Junta problem | Does not exist -- needs a new article | The junta problem | unclaimed | ||||||||||||||||||||||

22 | 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 | ||||||||||||||||||||||

23 | Lattice-based cryptography | finished | Noah Stephens-Davidowitz | |||||||||||||||||||||||

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

25 | Log rank conjecture | Mentioned in "Communication Complexity"; needs a separate article | Communication Complexity | unclaimed | ||||||||||||||||||||||

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

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

28 | Primal-dual approximation | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

29 | 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 | |||||||||||||||||||||||

30 | Prophet inequality | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

31 | Pseudo-polynomial time | Needs 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 | finished | Neal Young | |||||||||||||||||||||

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

34 | Smoothed analysis | Too short -- needs expansion | unclaimed | |||||||||||||||||||||||

35 | Space complexity | Very short article needs expansion | ||||||||||||||||||||||||

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

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

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

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...