More Like this

1. An algorithmic hypergraph regularity lemma

   https://doi.org/10.1002/rsa.20739  

   Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias (December 2017, Random Structures & Algorithms)

   Abstract Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended tok‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs. 

   more » « less
2. Definable Regularity Lemmas for NIP Hypergraphs

   https://doi.org/10.1093/qmath/haab011  

   Chernikov, Artem; Starchenko, Sergei (March 2021, The Quarterly Journal of Mathematics)

   null (Ed.)

   Abstract We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and Lov\'asz-Szegedy for graphs of bounded VC-dimension. We also consider the two extremal cases of regularity for stable and distal hypergraphs, improving and generalizing the corresponding results for graphs in the literature. Finally, we consider a related question of the existence of large (approximately) homogeneous definable subsets of NIP hypergraphs and provide some positive results and counterexamples, in particular for graphs definable in the p-adics. 

   more » « less
3. Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions

   https://doi.org/10.1145/3570162  

   Fox, Kyle; Panigrahi, Debmalya; Zhang, Fred (April 2023, ACM Transactions on Algorithms)

   On hypergraphs withmhyperedges andnvertices, wherepdenotes the total size of the hyperedges, we provide the following results:We give an algorithm that runs in\(\widetilde{O}(mn^{2k-2})\)time for finding a minimumk-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimumk-cut problem, fork> 2.We give an algorithm that runs in\(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\)time for finding a minimumk-cut in hypergraphs of constant rankr. This algorithm betters the previous best running times for both the minimum cut and minimumk-cut problems for dense hypergraphs.Both of our algorithms are Monte Carlo, i.e., they return a minimumk-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a genericbranching randomized contractiontechnique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs. 

   more » « less
4. Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

   https://doi.org/10.1002/rsa.20994  

   Nie, Jiaxi; Verstraëte, Jacques (January 2021, Random Structures & Algorithms)

   Abstract In this paper, we consider a randomized greedy algorithm for independent sets inr‐uniformd‐regular hypergraphsGonnvertices with girthg. By analyzing the expected size of the independent sets generated by this algorithm, we show that, whereconverges to 0 asg → ∞for fixeddandr, andf(d, r) is determined by a differential equation. This extends earlier results of Garmarnik and Goldberg for graphs [8]. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely. 

   more » « less
5. Leveraging complexity frameworks to refine theories of engagement: Advancing self‐regulated learning in the age of artificial intelligence

   https://doi.org/10.1111/bjet.13340  

   Hilpert, Jonathan_C; Greene, Jeffrey_A; Bernacki, Matthew (May 2023, British Journal of Educational Technology)

   Abstract Capturing evidence for dynamic changes in self‐regulated learning (SRL) behaviours resulting from interventions is challenging for researchers. In the current study, we identified students who were likely to do poorly in a biology course and those who were likely to do well. Then, we randomly assigned a portion of the students predicted to perform poorly to a science of learning to learn intervention where they were taught SRL study strategies. Learning outcome and log data (257 K events) were collected fromn = 226 students. We used a complex systems framework to model the differences in SRL including the amount, interrelatedness, density and regularity of engagement captured in digital trace data (ie, logs). Differences were compared between students who were predicted to (1) perform poorly (control,n = 48), (2) perform poorly and received intervention (treatment,n = 95) and (3) perform well (not flagged,n = 83). Results indicated that the regularity of students' engagement was predictive of course grade, and that the intervention group exhibited increased regularity in engagement over the control group immediately after the intervention and maintained that increase over the course of the semester. We discuss the implications of these findings in relation to the future of artificial intelligence and potential uses for monitoring student learning in online environments. Practitioner notesWhat is already known about this topicSelf‐regulated learning (SRL) knowledge and skills are strong predictors of postsecondary STEM student success.SRL is a dynamic, temporal process that leads to purposeful student engagement.Methods and metrics for measuring dynamic SRL behaviours in learning contexts are needed.What this paper addsA Markov process for measuring dynamic SRL processes using log data.Evidence that dynamic, interaction‐dominant aspects of SRL predict student achievement.Evidence that SRL processes can be meaningfully impacted through educational intervention.Implications for theory and practiceComplexity approaches inform theory and measurement of dynamic SRL processes.Static representations of dynamic SRL processes are promising learning analytics metrics.Engineered features of LMS usage are valuable contributions to AI models. 

   more » « less