Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

The Mantel-Cox Log-Rank Test01:19

The Mantel-Cox Log-Rank Test

579
The Mantel-Cox log-rank test is a widely used statistical method for comparing the survival distributions of two groups. It tests whether a statistically significant difference exists in survival times between the groups without assuming a specific distribution for the survival data, making it a non-parametric test. This flexibility makes the log-rank test particularly valuable in medical research and other fields where the timing of an event, such as death or disease recurrence, is of...
579
Wilcoxon Signed-Ranks Test for Matched Pairs01:09

Wilcoxon Signed-Ranks Test for Matched Pairs

227
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
227
Friedman Two-way Analysis of Variance by Ranks01:21

Friedman Two-way Analysis of Variance by Ranks

308
Friedman's Two-Way Analysis of Variance by Ranks is a nonparametric test designed to identify differences across multiple test attempts when traditional assumptions of normality and equal variances do not apply. Unlike conventional ANOVA, which requires normally distributed data with equal variances, Friedman's test is ideal for ordinal or non-normally distributed data, making it particularly useful for analyzing dependent samples, such as matched subjects over time or repeated measures...
308
Wilcoxon Signed-Ranks Test for Median of Single Population01:14

Wilcoxon Signed-Ranks Test for Median of Single Population

238
The Wilcoxon signed-rank test for the median of a single population is a nonparametric test used to evaluate whether the median of a population differs from a specified value. Unlike parametric tests, it does not require data to follow a normal distribution, making it suitable for non-normal or small samples. The test begins by calculating the difference (d) between each observation and the hypothesized median. The absolute values of these differences are ranked in ascending order, with ties...
238
Wilcoxon Rank-Sum Test01:21

Wilcoxon Rank-Sum Test

353
The Wilcoxon rank-sum test, also known as the Mann-Whitney U test, is a nonparametric test used to determine if there is a significant difference between the distributions of two independent samples. This test is designed specifically for two independent populations and has the following key requirements:
353
Regression Toward the Mean01:52

Regression Toward the Mean

6.5K
Regression toward the mean (“RTM”) is a phenomenon in which extremely high or low values—for example, and individual’s blood pressure at a particular moment—appear closer to a group’s average upon remeasuring. Although this statistical peculiarity is the result of random error and chance, it has been problematic across various medical, scientific, financial and psychological applications. In particular, RTM, if not taken into account, can interfere when...
6.5K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Factorization norms and an inverse theorem for MaxCut.

Mathematische annalen·2026
Same author

Evasive Sets, Covering by Subspaces, and Point-Hyperplane Incidences.

Discrete & computational geometry·2024
Same author

The growth rate of multicolor Ramsey numbers of 3-graphs.

Research in the mathematical sciences·2024
Same author

A Sharp Threshold Phenomenon in String Graphs.

Discrete & computational geometry·2022
Same journal

A better-than-1.6-approximation for prize-collecting TSP.

Mathematical programming·2026
Same journal

A <math><mrow><mfrac><mn>4</mn> <mn>3</mn></mfrac></mrow></math> -approximation for the maximum leaf spanning arborescence problem in DAGs.

Mathematical programming·2026
Same journal

An FPTAS for Connectivity Interdiction.

Mathematical programming·2026
Same journal

A first order method for linear programming parameterized by circuit imbalance.

Mathematical programming·2026
Same journal

Tight lower bounds for block-structured integer programs.

Mathematical programming·2026
Same journal

Accelerated first-order optimization under nonlinear constraints.

Mathematical programming·2026
See all related articles

Related Experiment Video

Updated: Sep 18, 2025

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments
08:12

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

Published on: March 1, 2022

2.6K

Matrix discrepancy and the log-rank conjecture.

Benny Sudakov1, István Tomon2

  • 1ETH Zurich, Zürich, Switzerland.

Mathematical Programming
|June 20, 2025
PubMed
Summary
This summary is machine-generated.

Researchers developed new methods to analyze binary matrices, revealing a significant lower bound on their discrepancy. This finding improves understanding of the log-rank conjecture and communication complexity for Boolean functions.

Keywords:
DiscrepancyLog-rank conjecture

More Related Videos

Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach
04:35

Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach

Published on: July 3, 2020

3.4K
Applying an eMASS Customization Program as a Research Tool to Evaluate Consumer Benefits
08:27

Applying an eMASS Customization Program as a Research Tool to Evaluate Consumer Benefits

Published on: September 27, 2019

7.0K

Related Experiment Videos

Last Updated: Sep 18, 2025

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments
08:12

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

Published on: March 1, 2022

2.6K
Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach
04:35

Development of an Individual-Tree Basal Area Increment Model using a Linear Mixed-Effects Approach

Published on: July 3, 2020

3.4K
Applying an eMASS Customization Program as a Research Tool to Evaluate Consumer Benefits
08:27

Applying an eMASS Customization Program as a Research Tool to Evaluate Consumer Benefits

Published on: September 27, 2019

7.0K

Area of Science:

  • Theoretical Computer Science
  • Linear Algebra
  • Combinatorics

Background:

  • The discrepancy of a binary matrix measures how evenly distributed its 1s are.
  • Understanding matrix discrepancy is crucial for analyzing data structures and computational complexity.
  • Existing bounds on discrepancy often depend on matrix properties like rank.

Purpose of the Study:

  • To establish a lower bound for the discrepancy of binary matrices with a given rank.
  • To improve upper bounds on the log-rank conjecture.
  • To determine the deterministic communication complexity of Boolean functions based on matrix rank.

Main Methods:

  • Utilized semidefinite programming and spectral techniques to analyze matrix properties.
  • Derived a novel lower bound for matrix discrepancy based on its rank and density.
  • Applied discrepancy results to submatrix problems and communication complexity.

Main Results:

  • Proved a lower bound on the discrepancy of an m x n binary matrix M of rank r: disc(M) = Ω(mn) * min(p, p^(1/2)/√r).
  • Showed that any m x n binary matrix of rank at most r contains a submatrix of size (m*2^(-O(√r))) x (n*2^(-O(√r))) that is all-1s or all-0s.
  • Established an upper bound of O(√r) on the deterministic communication complexity of Boolean functions of rank r.

Conclusions:

  • The study provides a significant advancement in understanding the relationship between matrix rank, discrepancy, and communication complexity.
  • The derived bounds offer new insights into the structure of binary matrices and their computational implications.
  • This work contributes to the ongoing efforts to resolve fundamental conjectures in theoretical computer science.