The reviewed record of science sign in
Pith

arxiv: 2606.13491 · v1 · pith:IZ5JQTT5 · submitted 2026-06-11 · cs.IT · math.IT

Fundamental Limits of Hypergraph Edge Partitioning under Independent Edge Sampling

Javad Maheri , K.K.Krishnan Namboodiri , Petros Elia This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-27 05:26 UTCgrok-4.3pith:IZ5JQTT5record.jsonopen to challenge →

classification cs.IT math.IT
keywords hypergraph edge partitioningvertex footprintfundamental limitsindependent edge samplingconverse boundshypergraph stochastic block modeldistributed computation
0
0 comments X

The pith

For hypergraphs with at least order n N log N edges, no algorithm achieves vertex footprint below about n over N to the power 1/d.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves fundamental lower bounds on the vertex footprint achievable by any hypergraph edge partitioner under independent edge sampling. When the number of hyperedges meets or exceeds roughly n times N times log N, and under a mild size condition on N, the smallest possible maximum vertices per partition is at least 1 over 2 sqrt 2 times n divided by N to the power 1/d, holding with high probability. A matching upper bound is shown by exhibiting a deterministic partitioner that stays within a constant factor of this limit. This scaling applies across dense and sparse regimes and covers many standard hypergraph models used in distributed systems and machine learning.

Core claim

For any n, d, and N at most the binomial of floor of square root of n d over 2 choose d, whenever the hyperedge set X has size at least order n N log N, with probability at least 1 minus 2 over 3 n to the z, every algorithm is forced to a footprint of at least pi star X equals 1 over 2 sqrt 2 times n over N to the 1/d. The paper's partitioner matches this bound up to a small constant factor for every such X, and the result extends to the Degree-Corrected, Mixed-Membership, Hypergraph Stochastic Block, and Latent-Space models.

What carries the argument

The deterministic hypergraph partitioner paired with a new converse that lower-bounds the footprint under independent per-hyperedge sampling.

If this is right

  • The bound holds for both dense hypergraphs and sparse ones whose size is linear in n.
  • The partitioner produces a near-optimal balance of hyperedges across the N partitions.
  • The same scaling limit applies to the Degree-Corrected, Mixed-Membership, Hypergraph Stochastic Block, and geometric kernel models.
  • No algorithm can improve the footprint scaling without violating the edge-count or N-size conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • In distributed computing, this scaling implies that communication or storage costs cannot be reduced below the stated footprint without extra assumptions on edge dependence.
  • The result may guide algorithm design for related problems such as hypergraph coloring or load balancing when similar independence holds.
  • One could test the bound empirically by generating random instances from the covered models and measuring achieved footprints against the formula.

Load-bearing premise

The number of partitions N is at most the binomial coefficient of floor of the square root of n d over 2 choose d.

What would settle it

An explicit hypergraph with roughly n N log N edges, satisfying the N condition, on which some algorithm produces a footprint smaller than n over N to the 1/d by more than a constant factor with probability higher than 2 over 3 n to the z.

read the original abstract

Hypergraph edge partitioning is a central problem in theoretical and applied computer science, with broad impact on distributed computation, communications, optimization, and machine learning. In this setting, one is given a collection of hyperedges -- each consisting of up to $d$ vertices from a ground set of size $n$ -- and seeks to assign these hyperedges across $N$ partitions so as to minimize, for example, the vertex footprint, i.e., the maximum number of vertices that appear in any partition. We here identify the fundamental limits of hypergraph edge partitioning -- optimized over all conceivable algorithms -- for a broad class of probabilistic hypergraph models where each hyperedge may appear independently with \emph{its own} probability; a model sufficiently general to encompass well-known models such as the Degree-Corrected or Mixed-Membership models, the Hypergraph Stochastic Block model, the Latent-Space/Geometric or Kernel Models, and others. By pairing our deterministic partitioner with a new converse, we first show that, for any $n,d$, and under the very mild condition of $N \leq \binom{\lfloor\sqrt{\frac{nd}{2}}\rfloor}{d}$, as long as the hyperedge set $\mathbf{X}$ satisfies $|\mathbf{X}| \gtrsim n N \log N$, then with probability at least $1-2/3n^z$, no algorithm can provide a footprint $\pi_{\mathbf{X}}$ less than $$\pi^{\bigstar}_{\mathbf{X}} = \frac{1}{2\sqrt{2}}\frac{n}{N^{1/d}}. $$ We then show that our hypergraph partitioner comes to within a small constant factor from $\pi^{\bigstar}_{\mathbf{X}}$, for each $\mathbf{X}$. This optimality captures dense and sparse hypergraphs alike (with sizes down to linear in $n$), and it additionally entails a near-optimally balanced allocation of hyperedges across partitions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript claims to identify the fundamental limits of hypergraph edge partitioning under a general independent edge sampling model (encompassing Degree-Corrected, Mixed-Membership, Hypergraph SBM, and geometric models). Under the condition N ≤ binom(⌊√(nd/2)⌋, d), when |X| ≳ n N log N, with probability at least 1-2/(3n^z) no algorithm achieves vertex footprint below π*_X = (1/(2√2)) n / N^{1/d}; the authors' deterministic partitioner matches this lower bound up to a small constant factor for every X, while also ensuring near-balanced allocation across the N partitions. The result is asserted to cover both dense and sparse regimes down to |X| linear in n.

Significance. If the stated bounds hold, the work supplies information-theoretic benchmarks for a broad class of hypergraph models arising in distributed computation, ML, and network analysis. The explicit pairing of a new converse with a deterministic construction, together with coverage of linear-sized hyperedge sets, constitutes a clear technical contribution.

major comments (1)
  1. [Abstract] Abstract (main converse statement): the lower bound π*_X is claimed only under the additional restriction N ≤ binom(⌊√(nd/2)⌋, d). This binomial bound on N is load-bearing for the optimality result; it arises from the counting/union-bound step that controls the probability a random X is coverable by any collection of N supports each using at most π vertices. The manuscript must either justify why the restriction is fundamental or show that the converse can be extended beyond it, because the central claim of 'fundamental limits' is confined to this regime.
minor comments (2)
  1. [Abstract] Abstract: the failure probability is written '1-2/3n^z'; the notation is ambiguous and should be rendered unambiguously (presumably 1 - 2/(3 n^z)).
  2. [Abstract] Abstract: the achievability result is stated to come 'within a small constant factor' of π*_X; the explicit numerical factor (or its dependence on d) should be supplied so that the gap between lower and upper bounds is fully quantified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful review and for highlighting the importance of the condition on N in the converse. We address the major comment point-by-point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (main converse statement): the lower bound π*_X is claimed only under the additional restriction N ≤ binom(⌊√(nd/2)⌋, d). This binomial bound on N is load-bearing for the optimality result; it arises from the counting/union-bound step that controls the probability a random X is coverable by any collection of N supports each using at most π vertices. The manuscript must either justify why the restriction is fundamental or show that the converse can be extended beyond it, because the central claim of 'fundamental limits' is confined to this regime.

    Authors: The condition N ≤ binom(⌊√(nd/2)⌋, d) is required by the union-bound argument in the converse: it ensures that the number of possible N-tuples of supports of size π is small enough that the probability of covering a random X of size ≳ n N log N is exponentially small. We view the condition as mild rather than fundamental, because it still permits N as large as roughly (√(nd)) choose d, which for constant d and growing n allows super-polynomial (even exponential in d) values of N that cover the regimes of interest in distributed computation and ML. The paper already qualifies the result with this condition and does not claim the bound holds for arbitrarily large N. Extending the converse beyond this regime would require a different proof technique (e.g., beyond simple counting), which we do not currently have and leave as future work. In the revision we will add a short paragraph in the introduction and a footnote in the abstract explicitly motivating the condition as natural for the models considered and clarifying that the fundamental limits are established within this regime. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained against external benchmarks

full rationale

The claimed lower bound on footprint is obtained via a standard converse (union-bound counting argument) under an explicit combinatorial restriction on N that arises from the number of candidate low-footprint partitions; the matching upper bound is realized by an explicit deterministic partitioner. No step reduces by definition to its own inputs, no fitted parameter is relabeled as a prediction, and no load-bearing premise rests solely on a self-citation chain. The result therefore stands as an independent combinatorial statement inside the stated regime.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard combinatorial counting and probabilistic concentration tools without introducing new free parameters or postulated entities.

axioms (1)
  • domain assumption Hyperedges appear independently with their own probabilities (the independent edge sampling model).
    This is the generative model assumed for the hypergraph throughout the analysis.

pith-pipeline@v0.9.1-grok · 5896 in / 1257 out tokens · 31899 ms · 2026-06-27T05:26:56.618150+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 6 canonical work pages · 1 internal anchor

  1. [1]

    A fast and high quality multilevel scheme for partitioning irregular graphs,

    G. Karypis and V . Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,”SIAM J. Scientific Comput., vol. 20, no. 1, pp. 359–392, 1998

    1998

  2. [2]

    Multi-level direct k-way hypergraph par- titioning with multiple constraints and fixed vertices,

    C. Aykanat, B. B. Cambazoglu, and B. Uc ¸ar, “Multi-level direct k-way hypergraph par- titioning with multiple constraints and fixed vertices,”J. Parallel and Distrib. Comput., vol. 68, no. 5, pp. 609–625, 2008

    2008

  3. [3]

    Finding good approximate vertex and edge partitions is NP-hard,

    T. N. Bui and C. Jones, “Finding good approximate vertex and edge partitions is NP-hard,” Inf. Processing Lett., vol. 42, no. 3, pp. 153–159, 1992

    1992

  4. [4]

    An efficient heuristic procedure for partitioning graphs,

    B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 49, no. 2, pp. 291–307, 1970

    1970

  5. [5]

    Approximate hypergraph partitioning and appli- cations,

    E. Fischer, A. Matsliah, and A. Shapira, “Approximate hypergraph partitioning and appli- cations,”SIAM Journal on Computing, vol. 39, no. 7, pp. 3155–3185, 2010

    2010

  6. [6]

    Minimum cuts and sparsification in hypergraphs,

    C. Chekuri and C. Xu, “Minimum cuts and sparsification in hypergraphs,”SIAM Journal on Computing, vol. 47, pp. 2118–2156, 2018

    2018

  7. [7]

    A hypergraph partitioning model for profile minimization,

    S. Acer, E. Kayaaslan, and C. Aykanat, “A hypergraph partitioning model for profile minimization,”SIAM Journal on Scientific Computing, vol. 41, no. 1, 2019

    2019

  8. [8]

    The Fiedler vector of a Laplacian tensor for hypergraph partitioning,

    Y . Chen, L. Qi, and X. Zhang, “The Fiedler vector of a Laplacian tensor for hypergraph partitioning,”SIAM Journal on Scientific Computing, vol. 39, no. 6, 2017

    2017

  9. [9]

    High- quality hypergraph partitioning,

    S. Schlag, T. Heuer, L. Gottesb ¨uren, Y . Akhremtsev, C. Schulz, and P. Sanders, “High- quality hypergraph partitioning,”ACM J. Exp. Algorithmics, vol. 27, pp. 1–39, 2023

    2023

  10. [10]

    Multilevel hypergraph partitioning: Applications in VLSI domain,

    G. Karypis, R. Aggarwal, V . Kumar, and S. Shekhar, “Multilevel hypergraph partitioning: Applications in VLSI domain,”IEEE Trans. Very Large Scale Integration (VLSI) Syst., vol. 7, no. 1, pp. 69–79, 1999. 43

    1999

  11. [11]

    An improved min-cut algorithm for partitioning VLSI networks,

    B. Krishnamurthy, “An improved min-cut algorithm for partitioning VLSI networks,” IEEE Trans. Comput., vol. C-33, no. 5, pp. 438–446, 1984

    1984

  12. [12]

    Parallel hypergraph partitioning for scientific computing,

    K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and ¨U. V . C ¸ ataly¨urek, “Parallel hypergraph partitioning for scientific computing,” inProc. 20th IEEE Int. Parallel & Distrib. Process. Symp., 2006

    2006

  13. [13]

    Multilevel k-way hypergraph partitioning,

    G. Karypis and V . Kumar, “Multilevel k-way hypergraph partitioning,” inProc. 36th ACM/IEEE Design Automat. Conf. (DAC), 1999, pp. 343–348

    1999

  14. [14]

    Multilevel hypergraph partitioning with vertex weights revisited,

    T. Heuer, N. Maas, and S. Schlag, “Multilevel hypergraph partitioning with vertex weights revisited,” 2021. arXiv: 2102.01378[cs.DS]

    work page arXiv 2021

  15. [15]

    More recent advances in (hyper)graph partitioning,

    ¨U. C ¸ ataly¨urek et al., “More recent advances in (hyper)graph partitioning,”ACM Comput. Surv., vol. 55, no. 12, pp. 1–38, 2023

    2023

  16. [16]

    Hypergraph-partitioning-based decomposition for par- allel sparse-matrix vector multiplication,

    ¨U. V . C ¸ ataly¨urek and C. Aykanat, “Hypergraph-partitioning-based decomposition for par- allel sparse-matrix vector multiplication,”IEEE Trans. Parallel and Distrib. Syst., vol. 10, no. 7, pp. 673–693, 1999

    1999

  17. [17]

    Recent advances in graph partitioning,

    A. Buluc, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, “Recent advances in graph partitioning,”Algorithm Eng., pp. 117–158, 2016

    2016

  18. [18]

    Hypergraph partitioning for sparse matrix-matrix multiplication,

    G. Ballard, A. Druinsky, N. Knight, and O. Schwartz, “Hypergraph partitioning for sparse matrix-matrix multiplication,”ACM Trans. Parallel Comput., vol. 3, no. 3, Dec. 2016

    2016

  19. [19]

    Hypergraph partitioning for multiple communication cost metrics: Model and methods,

    M. Deveci, K. Kaya, B. Uc ¸ar, and ¨U. V . C ¸ ataly¨urek, “Hypergraph partitioning for multiple communication cost metrics: Model and methods,”J. Parallel and Distrib. Computing, vol. 77, pp. 69–83, 2015

    2015

  20. [20]

    UMPa: A Multi-objective, multi-level partitioner for communication minimization,

    ¨U. V . C ¸ ataly¨urek, M. Deveci, K. Kaya, and B. Uc ¸ar, “UMPa: A Multi-objective, multi-level partitioner for communication minimization,”Graph Partitioning and Graph Clustering 2012, Contemporary Math., vol. 588, pp. 53–66, 2013

    2012

  21. [21]

    Blaspart: A deterministic parallel partitioner for balanced large-scale hypergraph partitioning,

    S. Tong, C. Pei, and W. Yu, “Blaspart: A deterministic parallel partitioner for balanced large-scale hypergraph partitioning,” in62nd ACM/IEEE Design Automat. Conf. (DAC), 2025, pp. 1–7

    2025

  22. [22]

    Deterministic parallel hypergraph partitioning,

    L. Gottesb ¨uren and M. Hamann, “Deterministic parallel hypergraph partitioning,” inEuro- Par 2022: Parallel Process.: 28th Int. Conf. Parallel and Distrib. Comput., Springer, 2022, pp. 301–316

    2022

  23. [23]

    A linear-time heuristic for improving network partitions,

    C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for improving network partitions,” in19th Design Automat. Conf., 1982, pp. 175–181. 44

    1982

  24. [24]

    Hypergraph-partitioning-based online joint scheduling of tasks and data,

    Y . Song et al., “Hypergraph-partitioning-based online joint scheduling of tasks and data,” J. Supercomputing, vol. 78, no. 14, pp. 16 088–16 117, 2022

    2022

  25. [25]

    Hypergraph Partitioning on GPU with Distinct Incident Hyperedges and Size Constraints

    M. Ronzani and C. Silvano, “Hypergraph partitioning on GPU with distinct incident hyperedges and size constraints,” 2026. arXiv: 2605.20497[cs.DC]

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  26. [26]

    A parallel algorithm for multilevel k-way hypergraph partitioning,

    A. Trifunovic and W. J. Knottenbelt, “A parallel algorithm for multilevel k-way hypergraph partitioning,” inThird Int. Symp. Parallel and Distrib. Comput./Third Int. Workshop Algo- rithms, Models and Tools for Parallel Comput. Heterogeneous Netw., 2004, pp. 114–121

    2004

  27. [27]

    Scalable shared-memory hypergraph partitioning,

    L. Gottesb ¨uren, T. Heuer, P. Sanders, and S. Schlag, “Scalable shared-memory hypergraph partitioning,” inProc. Symp. on Algorithm Eng. Exp. (ALENEX), 2021, pp. 16–30

    2021

  28. [28]

    Social hash partitioner: A scalable distributed hypergraph partitioner,

    I. Kabiljo, B. Karrer, M. Pundir, S. Pupyrev, and A. Shalita, “Social hash partitioner: A scalable distributed hypergraph partitioner,”Proc. VLDB Endow., vol. 10, no. 11, pp. 1418– 1429, 2017

    2017

  29. [29]

    Bipart: A parallel and deterministic hypergraph partitioner,

    S. Maleki, U. Agarwal, M. Burtscher, and K. Pingali, “Bipart: A parallel and deterministic hypergraph partitioner,” inPPoPP ’21: 26th ACM SIGPLAN Symp. Princ. Practice of Parallel Program., 2021, pp. 161–174

    2021

  30. [30]

    PowerGraph: Distributed graph-parallel computation on natural graphs,

    J. E. Gonzalez, Y . Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed graph-parallel computation on natural graphs,” inOSDI, 2012

    2012

  31. [31]

    Graph edge partitioning via neighborhood heuristic,

    C. Zhang, F. Wei, Q. Liu, Z. G. Tang, and Z. Li, “Graph edge partitioning via neighborhood heuristic,” inProc. ACM SIGKDD Int. Conf. Knowl. Discovery and Data Mining (KDD), 2017, pp. 605–614

    2017

  32. [32]

    2PS: High-quality edge partitioning with two-phase streaming,

    R. Mayer, K. Orujzade, and H.-A. Jacobsen, “2PS: High-quality edge partitioning with two-phase streaming,” 2020. arXiv: 2001.07086[cs.DC]

    work page arXiv 2020

  33. [33]

    Balanced graph edge partition,

    F. Bourse, M. Lelarge, and M. V ojnovi ´c, “Balanced graph edge partition,” inProceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), ACM, 2014, pp. 1456–1465

    2014

  34. [34]

    Distributed edge partitioning for trillion-edge graphs,

    M. Hanai, T. Suzumura, W. J. Tan, E. Liu, G. Theodoropoulos, and W. Cai, “Distributed edge partitioning for trillion-edge graphs,”Proc. VLDB Endow., vol. 12, no. 13, pp. 2379– 2392, 2019

    2019

  35. [35]

    Time-efficient and high-quality graph partitioning for graph dynamic scaling,

    M. Hanai, N. Tziritas, T. Suzumura, W. Cai, and G. Theodoropoulos, “Time-efficient and high-quality graph partitioning for graph dynamic scaling,” 2021. arXiv: 2101.07026 [cs.DC]. 45

    work page arXiv 2021

  36. [36]

    SAT-based optimal hypergraph partitioning with replication,

    M. G. Wrighton and A. M. DeHon, “SAT-based optimal hypergraph partitioning with replication,” inProc. 2006 Asia and South Pacific Design Automat. Conf., 2006, pp. 789– 795

    2006

  37. [37]

    Simulated annealing for edge partitioning,

    H. Mykhailenko, G. Neglia, and F. Huet, “Simulated annealing for edge partitioning,” in 2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), IEEE, 2017, pp. 54–59

    2017

  38. [38]

    Hybrid edge partitioner: Partitioning large power-law graphs under memory constraints,

    R. Mayer and H.-A. Jacobsen, “Hybrid edge partitioner: Partitioning large power-law graphs under memory constraints,” inProceedings of the 2021 International Conference on Management of Data (SIGMOD), ACM, 2021, pp. 1359–1372

    2021

  39. [39]

    Hepart: A balanced hypergraph par- titioning algorithm for big data applications,

    W. Yang, G. Wang, K.-K. R. Choo, and S. Chen, “Hepart: A balanced hypergraph par- titioning algorithm for big data applications,”Future Generation Comput. Syst., vol. 83, pp. 250–268, 2018

    2018

  40. [40]

    Scalable edge partitioning,

    S. Schlag, C. Schulz, D. Seemaier, and D. Strash, “Scalable edge partitioning,”ACM Journal of Experimental Algorithmics, vol. 24, pp. 1–23, 2019

    2019

  41. [41]

    Graph partition method based on finite projective planes,

    O. Kruglov, A. Mastikhina, O. Senkevich, D. Sirotkin, and S. Moiseev, “Graph partition method based on finite projective planes,” 2023. arXiv: 2312.13861[math.CO]

    work page arXiv 2023

  42. [42]

    Hdrf: Stream-based par- titioning for power-law graphs,

    F. Petroni, L. Querzoni, K. Daudjee, S. Kamali, and G. Iacoboni, “Hdrf: Stream-based par- titioning for power-law graphs,” inProceedings of the 24th ACM International Conference on Information and Knowledge Management (CIKM), ACM, 2015, pp. 243–252

    2015

  43. [43]

    Adwise: Adaptive window-based streaming edge partitioning for high- speed graph processing,

    C. Mayer et al., “Adwise: Adaptive window-based streaming edge partitioning for high- speed graph processing,” in2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), IEEE, 2018, pp. 685–695

    2018

  44. [44]

    Cusp: A customizable streaming edge partitioner for distributed graph analytics,

    L. Hoang, R. Dathathri, G. Gill, and K. Pingali, “Cusp: A customizable streaming edge partitioner for distributed graph analytics,” in2019 IEEE International Parallel and Dis- tributed Processing Symposium (IPDPS), IEEE, 2019, pp. 439–450

    2019

  45. [45]

    Boosting vertex- cut partitioning for streaming graphs,

    H. P. Sajjad, A. H. Payberah, F. Rahimian, V . Vlassov, and S. Haridi, “Boosting vertex- cut partitioning for streaming graphs,” in2016 IEEE International Congress on Big Data (BigData Congress), IEEE, 2016, pp. 1–8

    2016

  46. [46]

    Partitioning trillion edge graphs on edge devices,

    A. Chhabra, F. Kurpicz, C. Schulz, D. Schweisgut, and D. Seemaier, “Partitioning trillion edge graphs on edge devices,” in2025 Proceedings of the Conference on Applied and Computational Discrete Algorithms (ACDA), pp. 74–89. 46

  47. [47]

    Buffered Streaming Edge Partitioning,

    A. Chhabra, M. Fonseca Faraj, C. Schulz, and D. Seemaier, “Buffered Streaming Edge Partitioning,” in22nd International Symposium on Experimental Algorithms (SEA 2024), vol. 301, 2024

    2024

  48. [48]

    Streaming balanced graph partitioning algorithms for random graphs,

    I. Stanton, “Streaming balanced graph partitioning algorithms for random graphs,” in Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, 2014, pp. 1287–1301

    2014

  49. [49]

    Open problems in (hyper)graph decomposition,

    D. Ajwani et al., “Open problems in (hyper)graph decomposition,”Leibniz Int. Proc. Inform. (LIPIcs), 2023

    2023

  50. [50]

    Universal and asymptotically optimal data and task allocation in distributed computing,

    J. Maheri, K. K. K. Namboodiri, and P. Elia, “Universal and asymptotically optimal data and task allocation in distributed computing,” 2026. arXiv: 2601.05873[cs.IT]

    work page arXiv 2026

  51. [51]

    Order optimal task allocation in distributed computing via interweaved cliques,

    J. Maheri, K. Namboodiri, and P. Elia, “Order optimal task allocation in distributed computing via interweaved cliques,” in2026 IEEE Int. Symp. Inf. Theory (ISIT), 2026

    2026

  52. [52]

    Fundamental limits of caching,

    M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2856–2867, 2014

    2014

  53. [53]

    Maddah-Ali-Niesen scheme for multi- access coded caching,

    P. N. Muralidhar, D. Katyal, and B. S. Rajan, “Maddah-Ali-Niesen scheme for multi- access coded caching,” in2021 IEEE Inf. Theory Workshop (ITW), 2021, pp. 1–6

    2021

  54. [54]

    Coded caching with shared caches and private caches,

    E. Peter, K. K. K. Namboodiri, and B. S. Rajan, “Coded caching with shared caches and private caches,”IEEE Trans. Commun., vol. 72, no. 8, pp. 4857–4872, 2024

    2024

  55. [55]

    A fundamental tradeoff between com- putation and communication in distributed computing,

    S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “A fundamental tradeoff between com- putation and communication in distributed computing,”IEEE Transactions on Information Theory, vol. 64, no. 1, pp. 109–128, 2018

    2018

  56. [56]

    Fundamental limits of combinatorial multi-access caching,

    F. Brunero and P. Elia, “Fundamental limits of combinatorial multi-access caching,”IEEE Trans. Inf. Theory, vol. 69, no. 2, pp. 1037–1056, 2023

    2023

  57. [57]

    Multi-access distributed computing,

    F. Brunero and P. Elia, “Multi-access distributed computing,”IEEE Trans. Inf. Theory, vol. 70, no. 5, pp. 3385–3398, 2024

    2024

  58. [58]

    Constructing hamiltonian decompositions of complete k-uniform hypergraphs,

    J. Maheri and P. Elia, “Constructing hamiltonian decompositions of complete k-uniform hypergraphs,” in2025 IEEE Int. Symp. Inf. Theory (ISIT), 2025, pp. 1–6

    2025

  59. [59]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal,Probability and computing: randomization and proba- bilistic techniques in algorithms and data analysis. Cambridge university press, 2017

    2017

  60. [60]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, 3rd ed. Wiley, 2008

    2008