Relationships between parameters - Combinatorial Parameters

Name: VC Dimension / Effective VC Radius

Parameter 1: VC Dimension

Parameter 2: Effective VC Radius

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Witness: Addressing

Name: Largest Shattered Set / Minimum Largest Order Shattered Set

Parameter 1: Largest Shattered Set

Parameter 2: Minimum Largest Order Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Minimum Largest Order Shattered Set / Largest Strongly Shattered Set

Parameter 1: Minimum Largest Order Shattered Set

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Interpolation degree / Largest Strongly Shattered Set

Parameter 1: Interpolation degree

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Minimum Largest Order Shattered Set / Effective VC Radius

Parameter 1: Minimum Largest Order Shattered Set

Parameter 2: Effective VC Radius

Relationship Type: $P_1\ge P_2$

Variant:

Name: Minimum Largest Order Shattered Set / Interpolation degree

Parameter 1: Minimum Largest Order Shattered Set

Parameter 2: Interpolation degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Best Mistakes / Minimum Largest Order Shattered Set

Parameter 1: Best Mistakes

Parameter 2: Minimum Largest Order Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Effective Range / Yang dimension

Parameter 1: Effective Range

Parameter 2: Yang dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Largest Shattered Set / VC Dimension

Parameter 1: Largest Shattered Set

Parameter 2: VC Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Proper Stable Labeled Sample Compression / co-VC dimension

Parameter 1: Proper Stable Labeled Sample Compression

Parameter 2: co-VC dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Preference-Based Teaching Dimension / No-Clashing Teaching Dimension

Parameter 1: Preference-Based Teaching Dimension

Parameter 2: No-Clashing Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Degeneracy / Minimum Degree

Parameter 1: Degeneracy

Parameter 2: Minimum Degree

Relationship Type: $P_1\ge P_2$

Variant: Monotonic

Name: Maximum Degree / Double Density or Average Degree

Parameter 1: Maximum Degree

Parameter 2: Double Density or Average Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected Maximal Degree / Star number

Parameter 1: Projected Maximal Degree

Parameter 2: Star number

Relationship Type: $P_1 = P_2$

Variant:

Name: Projected Maximal Degree / Maximum Degree

Parameter 1: Projected Maximal Degree

Parameter 2: Maximum Degree

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Densest Subgraph (twice) / Degeneracy

Parameter 1: Densest Subgraph (twice)

Parameter 2: Degeneracy

Relationship Type: $P_1\ge P_2$

Variant:

Name: Maximum Degree / Minimum Degree

Parameter 1: Maximum Degree

Parameter 2: Minimum Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Preference-Based Teaching Dimension / Recursive Teaching Dimension

Parameter 1: Preference-Based Teaching Dimension

Parameter 2: Recursive Teaching Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Relative Hitting Size / Hitting Size

Parameter 1: Relative Hitting Size

Parameter 2: Hitting Size

Relationship Type: $P_1\ge P_2$

Variant: Relative

Name: Monotone Recursive Teaching Dimension / Recursive Teaching Dimension

Parameter 1: Monotone Recursive Teaching Dimension

Parameter 2: Recursive Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Maximum Projected Teaching Set Size / Maximum Teaching Set Size

Parameter 1: Maximum Projected Teaching Set Size

Parameter 2: Maximum Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Star number / Maximum Projected Teaching Set Size

Parameter 1: Star number

Parameter 2: Maximum Projected Teaching Set Size

Relationship Type: $P_1 = P_2$

Variant:

Name: Maximum Projected Teaching Set Size / Minimum Projected Teaching Set Size

Parameter 1: Maximum Projected Teaching Set Size

Parameter 2: Minimum Projected Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: Yang dimension / VC Dimension

Parameter 1: Yang dimension

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Random Equivalence Queries Complexity / VC Dimension

Parameter 1: Random Equivalence Queries Complexity

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Minimum Teaching Set Size / Effective VC Radius

Parameter 1: Minimum Teaching Set Size

Parameter 2: Effective VC Radius

Relationship Type: $P_1\ge P_2$

Variant:

Name: Teaching Dimension / Recursive Teaching Dimension

Parameter 1: Teaching Dimension

Parameter 2: Recursive Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Order Sample Compression / Monotonic Projected Minimum Teaching Set Size

Parameter 1: Order Sample Compression

Parameter 2: Monotonic Projected Minimum Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: Littlestone Dimension / Monotonic Projected Minimum Teaching Set Size

Parameter 1: Littlestone Dimension

Parameter 2: Monotonic Projected Minimum Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: Star number / Proper Ordered Sample Compression

Parameter 1: Star number

Parameter 2: Proper Ordered Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Ordered Sample Compression / Order Sample Compression

Parameter 1: Proper Ordered Sample Compression

Parameter 2: Order Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Ordered Sample Compression / Proper Labeled Sample Compression

Parameter 1: Proper Ordered Sample Compression

Parameter 2: Proper Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Threshold Dimension / VC Dimension

Parameter 1: Threshold Dimension

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Shattering / Log Size

Parameter 1: Log Shattering

Parameter 2: Log Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Shattering / Effective Range

Parameter 1: Log Shattering

Parameter 2: Effective Range

Relationship Type: $P_1 \ge c\log P_2$

Variant:

Name: VC Dimension / Monotone Recursive Teaching Dimension

Parameter 1: VC Dimension

Parameter 2: Monotone Recursive Teaching Dimension

Relationship Type: $P_1 \ge c\sqrt{P_2}$

Variant:

Name: VC Dimension / Log Shattering

Parameter 1: VC Dimension

Parameter 2: Log Shattering

Relationship Type: $P_1 \ge \frac{cP_2}{\log n}$

Variant:

Name: Self-Directed Queries Complexity / Littlestone Dimension

Parameter 1: Self-Directed Queries Complexity

Parameter 2: Littlestone Dimension

Relationship Type: $P_1 \ge \frac{cP_2}{\log n}$

Variant:

Name: Maximum Degree / Degeneracy

Parameter 1: Maximum Degree

Parameter 2: Degeneracy

Relationship Type: $P_1\ge P_2$

Variant:

Name: Teaching Dimension / Maximum Teaching Set Size

Parameter 1: Teaching Dimension

Parameter 2: Maximum Teaching Set Size

Relationship Type: $P_1 = P_2$

Variant:

Name: Maximum Degree / Densest Subgraph (twice)

Parameter 1: Maximum Degree

Parameter 2: Densest Subgraph (twice)

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected Minimum Degree / Minimum Degree

Parameter 1: Projected Minimum Degree

Parameter 2: Minimum Degree

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Distinguishing Range / Membership Query Complexity

Parameter 1: Distinguishing Range

Parameter 2: Membership Query Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive Teaching Dimension / Positive No-Clashing Teaching Dimension

Parameter 1: Positive Teaching Dimension

Parameter 2: Positive No-Clashing Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive Teaching Dimension / Teaching Dimension

Parameter 1: Positive Teaching Dimension

Parameter 2: Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive No-Clashing Teaching Dimension / No-Clashing Teaching Dimension

Parameter 1: Positive No-Clashing Teaching Dimension

Parameter 2: No-Clashing Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive Recursive Teaching Dimension / Recursive Teaching Dimension

Parameter 1: Positive Recursive Teaching Dimension

Parameter 2: Recursive Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive Teaching Dimension / Positive Recursive Teaching Dimension

Parameter 1: Positive Teaching Dimension

Parameter 2: Positive Recursive Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive Recursive Teaching Dimension / Positive No-Clashing Teaching Dimension

Parameter 1: Positive Recursive Teaching Dimension

Parameter 2: Positive No-Clashing Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Effective Range / Distinguishing Range

Parameter 1: Effective Range

Parameter 2: Distinguishing Range

Relationship Type: $P_1\ge P_2$

Variant:

Name: Positive No-Clashing Teaching Dimension / Maximum Positive Degree

Parameter 1: Positive No-Clashing Teaching Dimension

Parameter 2: Maximum Positive Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Littlestone Dimension / Stable Unlabeled Complexity

Parameter 1: Littlestone Dimension

Parameter 2: Stable Unlabeled Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Worst Mistakes / VC Dimension

Parameter 1: Worst Mistakes

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: No-Clashing Teaching Dimension / Densest Subgraph (twice)

Parameter 1: No-Clashing Teaching Dimension

Parameter 2: Densest Subgraph (twice)

Relationship Type: $P_1\ge P_2$

Variant:

Name: Degeneracy / Largest Strongly Shattered Set

Parameter 1: Degeneracy

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Maximum Positive Degree / Largest Strongly Shattered Set

Parameter 1: Maximum Positive Degree

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Littlestone Dimension / 2-Littlestone Dimension

Parameter 1: Littlestone Dimension

Parameter 2: 2-Littlestone Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: 2-Littlestone Dimension / 3-Littlestone Dimension

Parameter 1: 2-Littlestone Dimension

Parameter 2: 3-Littlestone Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Littlestone Dimension / Random Equivalence Queries Complexity

Parameter 1: Littlestone Dimension

Parameter 2: Random Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Distinguishing Range / Log Size

Parameter 1: Distinguishing Range

Parameter 2: Log Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: Maximum Degree / Maximum Positive Degree

Parameter 1: Maximum Degree

Parameter 2: Maximum Positive Degree

Relationship Type: $P_1\ge P_2$

Variant: Relative

Name: VC Dimension / Projected Double Density or Projected Average Degree

Parameter 1: VC Dimension

Parameter 2: Projected Double Density or Projected Average Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected Double Density or Projected Average Degree / Double Density or Average Degree

Parameter 1: Projected Double Density or Projected Average Degree

Parameter 2: Double Density or Average Degree

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Projected Double Density or Projected Average Degree / Projected Minimum Degree

Parameter 1: Projected Double Density or Projected Average Degree

Parameter 2: Projected Minimum Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected Maximal Degree / Projected Minimum Degree

Parameter 1: Projected Maximal Degree

Parameter 2: Projected Minimum Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected Maximal Degree / Projected Double Density or Projected Average Degree

Parameter 1: Projected Maximal Degree

Parameter 2: Projected Double Density or Projected Average Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: No-Clashing Teaching Dimension / Double Density or Average Degree

Parameter 1: No-Clashing Teaching Dimension

Parameter 2: Double Density or Average Degree

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Dual Sign Rank / VC Dimension

Parameter 1: Dual Sign Rank

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: VC Dimension / Dual Sign Rank

Parameter 1: VC Dimension

Parameter 2: Dual Sign Rank

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Sign Rank / Dual Sign Rank

Parameter 1: Sign Rank

Parameter 2: Dual Sign Rank

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected VC Radius / VC Dimension

Parameter 1: Projected VC Radius

Parameter 2: VC Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Projected VC Radius / Effective VC Radius

Parameter 1: Projected VC Radius

Parameter 2: Effective VC Radius

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Projected Strongly Shattered Dimension / VC Dimension

Parameter 1: Projected Strongly Shattered Dimension

Parameter 2: VC Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Projected Strongly Shattered Dimension / Largest Strongly Shattered Set

Parameter 1: Projected Strongly Shattered Dimension

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Maximum Largest Order Shattered Set / VC Dimension

Parameter 1: Maximum Largest Order Shattered Set

Parameter 2: VC Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Maximum Largest Order Shattered Set / Minimum Largest Order Shattered Set

Parameter 1: Maximum Largest Order Shattered Set

Parameter 2: Minimum Largest Order Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Maximum Degree / Largest Strongly Shattered Set

Parameter 1: Maximum Degree

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: Projected Minimum Degree / VC Dimension

Parameter 1: Projected Minimum Degree

Parameter 2: VC Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Maximum Teaching Set Size / Largest Strongly Shattered Set

Parameter 1: Maximum Teaching Set Size

Parameter 2: Largest Strongly Shattered Set

Relationship Type: $P_1\ge P_2$

Variant:

Name: VC Dimension / Densest Subgraph (twice)

Parameter 1: VC Dimension

Parameter 2: Densest Subgraph (twice)

Relationship Type: $P_1\ge P_2$

Variant:

Name: Monotonic Projected Minimum Teaching Set Size / Minimum Projected Teaching Set Size

Parameter 1: Monotonic Projected Minimum Teaching Set Size

Parameter 2: Minimum Projected Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant: Monotonic

Name: Monotonic Projected Minimum Teaching Set Size / Monotonic Minimum Teaching Set Size

Parameter 1: Monotonic Projected Minimum Teaching Set Size

Parameter 2: Monotonic Minimum Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Minimum Projected Teaching Set Size / Minimum Teaching Set Size

Parameter 1: Minimum Projected Teaching Set Size

Parameter 2: Minimum Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Stable Unlabeled Complexity / Unlabeled sample compression

Parameter 1: Stable Unlabeled Complexity

Parameter 2: Unlabeled sample compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Stable Unlabeled Complexity / Stable Labeled Sample Compression

Parameter 1: Stable Unlabeled Complexity

Parameter 2: Stable Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Majority Complexity / Littlestone Dimension

Parameter 1: Majority Complexity

Parameter 2: Littlestone Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Littlestone Dimension / Membership and Equivalence Queries Complexity

Parameter 1: Littlestone Dimension

Parameter 2: Membership and Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Membership and Equivalence Queries Complexity / Partial Equivalence Queries Complexity

Parameter 1: Membership and Equivalence Queries Complexity

Parameter 2: Partial Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Partial Equivalence Queries Complexity / Self-Directed Queries Complexity

Parameter 1: Partial Equivalence Queries Complexity

Parameter 2: Self-Directed Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Yang dimension / co-VC dimension

Parameter 1: Yang dimension

Parameter 2: co-VC dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Unlabeled sample compression / Labeled Sample Compression

Parameter 1: Unlabeled sample compression

Parameter 2: Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: co-VC dimension / Effective VC Radius

Parameter 1: co-VC dimension

Parameter 2: Effective VC Radius

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Size / Size

Parameter 1: Log Size

Parameter 2: Size

Relationship Type: $P_1 \ge c\log P_2$

Variant:

Name: Size / VC Dimension

Parameter 1: Size

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Size / Path Dimension

Parameter 1: Size

Parameter 2: Path Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Threshold Dimension / Path Dimension

Parameter 1: Threshold Dimension

Parameter 2: Path Dimension

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Path Dimension / Threshold Dimension

Parameter 1: Path Dimension

Parameter 2: Threshold Dimension

Relationship Type: $P_1\ge P_2$

Variant: Relative

Name: Oriented Diameter / Threshold Dimension

Parameter 1: Oriented Diameter

Parameter 2: Threshold Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Diameter / Path Dimension

Parameter 1: Diameter

Parameter 2: Path Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Equivalence Queries Complexity / Littlestone Dimension

Parameter 1: Equivalence Queries Complexity

Parameter 2: Littlestone Dimension

Relationship Type: $P_1 = P_2$

Variant:

Name: Recursive Teaching Dimension / Interpolation degree

Parameter 1: Recursive Teaching Dimension

Parameter 2: Interpolation degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: Self-Directed Queries Complexity / Recursive Teaching Dimension

Parameter 1: Self-Directed Queries Complexity

Parameter 2: Recursive Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Best Mistakes / Self-Directed Queries Complexity

Parameter 1: Best Mistakes

Parameter 2: Self-Directed Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Effective Range / VC Dimension

Parameter 1: Effective Range

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Witness: Singletons

Name: Littlestone Dimension / VC Dimension

Parameter 1: Littlestone Dimension

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Witness: Half-intervals

Name: Effective Range / Diameter

Parameter 1: Effective Range

Parameter 2: Diameter

Relationship Type: $P_1\ge P_2$

Variant:

Witness: Singletons

Name: Diameter / Oriented Diameter

Parameter 1: Diameter

Parameter 2: Oriented Diameter

Relationship Type: $P_1\ge P_2$

Variant: Relative

Name: Oriented Diameter / Diameter

Parameter 1: Oriented Diameter

Parameter 2: Diameter

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Recursive Teaching Dimension / Effective VC Radius

Parameter 1: Recursive Teaching Dimension

Parameter 2: Effective VC Radius

Relationship Type: $P_1\ge P_2$

Variant:

Name: Effective Range / Hamming Radius

Parameter 1: Effective Range

Parameter 2: Hamming Radius

Relationship Type: $P_1\ge P_2$

Variant:

Witness: Singletons

Name: Size / Littlestone Dimension

Parameter 1: Size

Parameter 2: Littlestone Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Witness: Singletons

Name: Size / Yang dimension

Parameter 1: Size

Parameter 2: Yang dimension

Relationship Type: $P_1\ge P_2$

Variant:

Witness: Singletons

Name: Effective Range / Log Shattering

Parameter 1: Effective Range

Parameter 2: Log Shattering

Relationship Type: $P_1\ge P_2$

Variant:

Name: Size / Proper Equivalence Queries Complexity

Parameter 1: Size

Parameter 2: Proper Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Shattering / Majority Complexity

Parameter 1: Log Shattering

Parameter 2: Majority Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Labeled Sample Compression / VC Dimension

Parameter 1: Labeled Sample Compression

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Order Sample Compression / Monotone Recursive Teaching Dimension

Parameter 1: Order Sample Compression

Parameter 2: Monotone Recursive Teaching Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Monotone Recursive Teaching Dimension / VC Dimension

Parameter 1: Monotone Recursive Teaching Dimension

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant:

Name: Littlestone Dimension / Worst Mistakes

Parameter 1: Littlestone Dimension

Parameter 2: Worst Mistakes

Relationship Type: $P_1\ge P_2$

Variant:

Name: Worst Mistakes / Best Mistakes

Parameter 1: Worst Mistakes

Parameter 2: Best Mistakes

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Size / Sign Rank

Parameter 1: Log Size

Parameter 2: Sign Rank

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Size / Majority Complexity

Parameter 1: Log Size

Parameter 2: Majority Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Hamming Radius / Oriented Diameter

Parameter 1: Hamming Radius

Parameter 2: Oriented Diameter

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Hamming Radius / Diameter

Parameter 1: Hamming Radius

Parameter 2: Diameter

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Teaching Dimension / Relative Hitting Size

Parameter 1: Teaching Dimension

Parameter 2: Relative Hitting Size

Relationship Type: $P_1 = P_2$

Variant:

Name: Threshold Dimension / Littlestone Dimension

Parameter 1: Threshold Dimension

Parameter 2: Littlestone Dimension

Relationship Type: $P_1 \ge c\log P_2$

Variant:

Name: VC Dimension / Log Size Ratio

Parameter 1: VC Dimension

Parameter 2: Log Size Ratio

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Interpolation degree / Log Size Ratio

Parameter 1: Interpolation degree

Parameter 2: Log Size Ratio

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Projected Membership Queries Complexity / Membership Query Complexity

Parameter 1: Projected Membership Queries Complexity

Parameter 2: Membership Query Complexity

Relationship Type: $P_1\ge P_2$

Variant: P-Monotonic

Name: Projected Membership Queries Complexity / Star number

Parameter 1: Projected Membership Queries Complexity

Parameter 2: Star number

Relationship Type: $P_1\ge P_2$

Variant:

Name: Effective Range / Projected Membership Queries Complexity

Parameter 1: Effective Range

Parameter 2: Projected Membership Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Size / Projected Membership Queries Complexity

Parameter 1: Size

Parameter 2: Projected Membership Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Log Size / Random Proper Equivalence Queries Complexity

Parameter 1: Log Size

Parameter 2: Random Proper Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Equivalence Queries Complexity / Random Proper Equivalence Queries Complexity

Parameter 1: Proper Equivalence Queries Complexity

Parameter 2: Random Proper Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Random Proper Equivalence Queries Complexity / Random Equivalence Queries Complexity

Parameter 1: Random Proper Equivalence Queries Complexity

Parameter 2: Random Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Recursive Teaching Dimension / Monotonic Minimum Teaching Set Size

Parameter 1: Recursive Teaching Dimension

Parameter 2: Monotonic Minimum Teaching Set Size

Relationship Type: $P_1 = P_2$

Variant:

Name: Maximum Teaching Set Size / Relative Hitting Size

Parameter 1: Maximum Teaching Set Size

Parameter 2: Relative Hitting Size

Relationship Type: $P_1 = P_2$

Variant:

Name: Proper Equivalence Queries Complexity / Membership and Proper Equivalence Queries Complexity

Parameter 1: Proper Equivalence Queries Complexity

Parameter 2: Membership and Proper Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Equivalence Queries Complexity / Equivalence Queries Complexity

Parameter 1: Proper Equivalence Queries Complexity

Parameter 2: Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Littlestone Dimension / Occasional One-Sided Getback

Parameter 1: Littlestone Dimension

Parameter 2: Occasional One-Sided Getback

Relationship Type: $P_1\ge P_2$

Variant:

Name: Monotonic Minimum Teaching Set Size / Minimum Teaching Set Size

Parameter 1: Monotonic Minimum Teaching Set Size

Parameter 2: Minimum Teaching Set Size

Relationship Type: $P_1\ge P_2$

Variant: Monotonic

Name: Membership Query Complexity / Relative Hitting Size

Parameter 1: Membership Query Complexity

Parameter 2: Relative Hitting Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: 3-Littlestone Dimension / $k$-Littlestone Dimension ($k\ge3$)

Parameter 1: 3-Littlestone Dimension

Parameter 2: $k$-Littlestone Dimension ($k\ge3$)

Relationship Type: $P_1\ge P_2$

Variant:

Name: Membership Query Complexity / Log Size

Parameter 1: Membership Query Complexity

Parameter 2: Log Size

Relationship Type: $P_1\ge P_2$

Variant:

Name: Membership and Proper Equivalence Queries Complexity / Membership and Equivalence Queries Complexity

Parameter 1: Membership and Proper Equivalence Queries Complexity

Parameter 2: Membership and Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Diameter / Hamming Radius

Parameter 1: Diameter

Parameter 2: Hamming Radius

Relationship Type: $P_1\ge P_2$

Variant:

Name: Oriented Diameter / Hamming Radius

Parameter 1: Oriented Diameter

Parameter 2: Hamming Radius

Relationship Type: $P_1\ge cP_2$

Variant:

Name: Densest Subgraph (twice) / Double Density or Average Degree

Parameter 1: Densest Subgraph (twice)

Parameter 2: Double Density or Average Degree

Relationship Type: $P_1\ge P_2$

Variant: Monotonic

Name: Double Density or Average Degree / Minimum Degree

Parameter 1: Double Density or Average Degree

Parameter 2: Minimum Degree

Relationship Type: $P_1\ge P_2$

Variant:

Name: VC Dimension / Densest Subgraph (twice)

Parameter 1: VC Dimension

Parameter 2: Densest Subgraph (twice)

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Stable Sample Compression / Proper Stable Labeled Sample Compression

Parameter 1: Proper Stable Sample Compression

Parameter 2: Proper Stable Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Unlabeled Sample Compression / Proper Labeled Sample Compression

Parameter 1: Proper Unlabeled Sample Compression

Parameter 2: Proper Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Unlabeled Sample Compression / Unlabeled sample compression

Parameter 1: Proper Unlabeled Sample Compression

Parameter 2: Unlabeled sample compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Stable Sample Compression / Stable Unlabeled Complexity

Parameter 1: Proper Stable Sample Compression

Parameter 2: Stable Unlabeled Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Stable Labeled Sample Compression / Stable Labeled Sample Compression

Parameter 1: Proper Stable Labeled Sample Compression

Parameter 2: Stable Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Stable Labeled Sample Compression / Proper Labeled Sample Compression

Parameter 1: Proper Stable Labeled Sample Compression

Parameter 2: Proper Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Stable Sample Compression / Proper Unlabeled Sample Compression

Parameter 1: Proper Stable Sample Compression

Parameter 2: Proper Unlabeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Stable Labeled Sample Compression / Labeled Sample Compression

Parameter 1: Stable Labeled Sample Compression

Parameter 2: Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Equivalence Queries Complexity / Proper Stable Sample Compression

Parameter 1: Proper Equivalence Queries Complexity

Parameter 2: Proper Stable Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Proper Labeled Sample Compression / Labeled Sample Compression

Parameter 1: Proper Labeled Sample Compression

Parameter 2: Labeled Sample Compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Occasional One-Sided Getback / Best Mistakes

Parameter 1: Occasional One-Sided Getback

Parameter 2: Best Mistakes

Relationship Type: $P_1\ge P_2$

Variant:

Name: Occasional One-Sided Getback / Unlabeled sample compression

Parameter 1: Occasional One-Sided Getback

Parameter 2: Unlabeled sample compression

Relationship Type: $P_1\ge P_2$

Variant:

Name: Membership Query Complexity / Membership and Proper Equivalence Queries Complexity

Parameter 1: Membership Query Complexity

Parameter 2: Membership and Proper Equivalence Queries Complexity

Relationship Type: $P_1\ge P_2$

Variant:

Name: $k$-Littlestone Dimension ($k\ge3$) / VC Dimension

Parameter 1: $k$-Littlestone Dimension ($k\ge3$)

Parameter 2: VC Dimension

Relationship Type: $P_1\ge P_2$

Variant: