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 | Algorithmic Game Theory | More citations, expansion of list of subtopics and their descriptions, stylistic improvements | unclaimed | |||||||||||||||||||||||

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

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

6 | Dynamic Programming | Needs citations | unclaimed | |||||||||||||||||||||||

7 | Fast matrix multiplication | Mentioned 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 algorithm | unclaimed | ||||||||||||||||||||||

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

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

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

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

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

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

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

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

17 | Word RAM model of computing | Does not exist -- needs a new article | unclaimed | |||||||||||||||||||||||

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

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

20 | Proof complexity | Writing and exposition could use improvement | unclaimed | |||||||||||||||||||||||

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

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

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

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

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

26 | Lattice-based cryptography | in progress | Noah Stephens-Davidowitz | |||||||||||||||||||||||

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

28 | Pseudo-polynomial time | Needs expansion of numerical examples like knapsack or subset sum | ||||||||||||||||||||||||

29 | Randomized rounding | "might be confusing or unclear to some readers" | the method of conditional probabilities, the probabilistic method | finished | Neal Young | |||||||||||||||||||||

30 | The method of conditional probabilities | randomized rounding | finished | Neal Young | ||||||||||||||||||||||

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

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

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

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

Main menu