Concepedia

Set Disjointness

Set Disjointness is a fundamental communication problem in which two parties, each holding a subset of a universe, must determine whether their subsets have an empty intersection, serving as a canonical example of a total Boolean function studied in the two-party communication complexity model.

169

Publications

8K

Citations

288

Authors

176

Institutions

Publications per year

2017–2026

19

Parents

Publications

169

Disjointness in ergodic theory, minimal sets, and a problem in diophantine approximation

Harry Furstenberg · Theory of Computing Systems · 1967 · 1K citations

, , +13

A linear-time algorithm for a special case of disjoint set union

Harold N. Gabow, Robert E. Tarjan · Journal of Computer and System Sciences · 1985 · 557 citations

, , +10

On the distributional complexity of disjointness

Alexander Razborov · Theoretical Computer Science · 1992 · 485 citations

, , +10

A class of algorithms which require nonlinear time to maintain disjoint sets

Robert E. Tarjan · Journal of Computer and System Sciences · 1979 · 266 citations

, , +13

Towards polynomial lower bounds for dynamic problems

Mihai Pǎtraşcu · 2010 · 216 citations

, , +15

1–5 of 169

Authors

288

  1. LJ
    Lu Jia-Xi

    Baotou Teachers College, China

    6 publications · 337 citations

    6

    h-index

  2. RE
    Robert E. Tarjan

    Princeton University, United States

    5 publications · 1.1K citations

    5

    h-index

  3. PF
    Péter Frankl

    Centre National de la Recherche Scientifique, France

    5 publications · 100 citations

    5

    h-index

  4. TP
    Toniann Pitassi

    University of Toronto, Canada

    5 publications · 161 citations

    5

    h-index

  5. AT
    Amnon Ta‐Shma

    Tel Aviv University, Israel

    4 publications · 219 citations

    4

    h-index

1–5 of 288

Institutions

176

  1. Princeton University

    Princeton, United States

    7 h-index

    8 publications

    372 citations

  2. Tel Aviv University

    Tel Aviv, Israel

    6 h-index

    6 publications

    231 citations

  3. University of Toronto

    Toronto, Canada

    5 h-index

    11 publications

    421 citations

  4. AT&T (United States)

    Bedminster, United States

    5 h-index

    6 publications

    1.3K citations

  5. IBM Research - Almaden

    San Jose, United States

    5 h-index

    8 publications

    582 citations

  6. Université Paris Cité

    Paris, France

    4 h-index

    8 publications

    105 citations

  7. Alfréd Rényi Institute of Mathematics

    Budapest, Hungary

    4 h-index

    4 publications

    65 citations

  8. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    5 publications

    128 citations

1–8 of 176

Venues

  1. Journal of Combinatorial Theory Series A

    15 publications · 613 citations

    15

    h-index

  2. arXiv (Cornell University)

    Repository · 8 publications · 122 citations

    8

    h-index

  3. SIAM Journal on Computing

    6 publications · 352 citations

    6

    h-index

  4. Theoretical Computer Science

    6 publications · 597 citations

    6

    h-index

  5. Discrete Mathematics

    5 publications · 118 citations

    5

    h-index

1–5