The grain boundary network (GBN) of polycrystalline materials changes during grain growth, affecting the material's properties. This research presents the results of fully anisotropic grain growth simulations. We perform simulations using three GB energy functions: an energy function that considers a GB's 5 degrees of freedom, the Read-Shockley model, and isotropic. We analyze the impact of these energy functions on the morphological evolution and various microstructural statistics, such as crystallographic texture and triple junction distribution. The results demonstrate that while individual grain evolution varies with GB energy function, certain microstructural statistics reach similar steady states across different models. In addition, we perform simulations using a diverse set of initial microstructures sampled from the texture hull to investigate their influence on the evolutionary trajectory during grain growth. We find a universal increase in the sharpness of orientation distribution functions (ODFs) and a positive correlation between texture strength and its sharpening rate. Additionally, the evolution of the GBN exhibits an increase in low-angle grain boundaries. Finally, we develop a method for predicting microstructural evolution as an alternative to expensive traditional grain growth simulations. Using the dataset from the previous simulations, we train a diffusion model to reconstruct the morphology of the evolved microstructure and a GBN spectrum predictive model to reconstruct the texture. The alternative method is almost ten times faster at producing an evolved microstructure than a traditional grain growth level set method. Overall, this work enhances our understanding of grain growth and the impact of the GB energy and initial texture on the evolution of the microstructure.

<p dir="ltr">Combinatorial graph theory is an essential tool in the design and analysis of cryptographic primitives such as Memory-Hard Functions (MHFs) and Proofs of Sequential Work (PoSWs). MHFs are used to design egalitarian Proofs of Work and to help protect low-entropy secrets such as user passwords against brute-force attacks in password hashing. A PoSW is a protocol for proving that one spent significant sequential computation work to validate some statement. PoSWs have many applications, including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Prior work has used combinatorial properties of graphs to construct provably secure MHFs and PoSWs. However, some open problems still exist, such as improving security bounds for MHFs, finding approximation algorithms for measuring their memory hardness, and analyzing the post-quantum security of MHFs and PoSWs. This dissertation addresses these challenges in the security analysis of MHFs and PoSWs using combinatorial graph theory. </p><p dir="ltr">We first improve the understanding of the classical security of MHFs in the following ways. (1) We present improved security bounds for MHF candidates such as Argon2i and DRSample under plausible graph-theoretic conjectures. (2) We prove that it is Unique Games-hard to approximate the cumulative pebbling complexity of a directed acyclic graph, which is an important metric to understand the memory-hardness of data-independent MHFs. (3) We provide the first explicit construction of extremely depth-robust graphs with small indegree. Here, (extreme) depth-robustness is a crucial combinatorial tool to construct secure MHFs and PoSWs. (4) We build a new family of graphs that achieves better provable parameters for concrete depth-robustness.</p><p dir="ltr">Second, as we progress toward developing quantum computers, we initiate the post-quantum security analysis of MHFs and PoSWs. Specifically, we make the following contributions. (1) We introduce the parallel reversible pebbling game, which captures additional restrictions in quantum computing. We use combinatorial graph theory as a tool to analyze the space-time complexity and the cumulative pebbling complexity of MHF candidates such as Argon2i and DRSample in a reversible setting, which we call reversible space-time/cumulative pebbling cost, respectively. (2) We prove that the reversible cumulative pebbling cost is never too much larger than the classical cumulative pebbling cost, along with the separation result that, in some instances, the reversible cumulative pebbling cost is asymptotically larger than the classical one. (3) We prove that it is also Unique Games-hard to approximate the reversible cumulative pebbling cost of a directed acyclic graph. (4) Finally, we establish the post-quantum security of a PoSW from Cohen and Pietrzak (EUROCRYPT 2018) in the parallel quantum random oracle model by extending Zhandry's compressed oracle technique (CRYPTO 2019) and utilizing underlying combinatorial techniques of PoSWs.</p>

<p>We survey the problem of covering and partitioning a bipartite graph using vertex-disjoint unions of bicliques. The concept of a vertex-disjoint union of bicliques has been given many names in computer science: it has been termed a blocky matrix in communication complexity,</p> <p>a fat matching in circuit complexity, a bipartite P4-free graph in graph theory, a simple graph in cryptography, and a bicluster in bioinformatics. We aim to unify all of these perspectives, compiling what is known and unknown about the problem, including discussion on upper and lower bounding techniques for the problem, bounds for specific families of graphs, and</p> <p>the hardness of computation of the problem. Along the way, we present a new explicit graph for which the covering and partitioning numbers are different.</p>

No description available.

No description available.

No description available.

Social media sites have been perceived as a "common digital town square" in which opinions are exchanged at an unprecedented scale and speed. People not only share their own opinions on controversial issues but also consume news and assimilate opinions shared by friends in their social circles. The process by which individuals update their opinions in a social network is called opinion dynamics. This dissertation focuses on the negative consequences that arise from opinion dynamics, namely unfairness, polarization, and radicalization. We leverage techniques from social network modeling, graph theory, and supervised machine learning to formalize the notions of fairness in opinion dynamics over social networks, diagnose which and when algorithms exacerbate unfairness in networks, and design mitigation algorithms to counter radicalization. In the first project, we formalize two aspects of fairness in opinion dynamics, namely procedural fairness and distributive fairness. Through theoretical analysis and simulations on real-world social networks, we show how the combined effect of homophilous and reinforcing dynamics plays a special role in both types of fairness. In the second project, we study radicalization pathways that lead users from moderate to more extreme content and propose algorithms to mitigate radicalization. In particular, we study and propose the concept of gateway entities, i.e., non-problematic entities that are nevertheless associated with a higher likelihood of future engagement with radicalized content. We show, via a real-world application on Facebook groups, that a simple definition of gateway entities can be leveraged to reduce exposure to radicalized content without adversely impacting user engagement metrics. Through offline experiments, we show that survival analysis-based methods are effective at identifying individuals at risk. In the third project, we study the interplay between algorithms over social networks and fairness in opinion dynamics. We propose a framework that allows us to study the joint effects of algorithms over social networks and the opinion dynamic process. Through extensive simulations, we demonstrate that people-recommender algorithms do not exacerbate procedure unfairness but have a significant impact on distributive fairness, and polarization reduction algorithms have no significant impact on fairness. We close by discussing the limitations of our work and directions for future research.

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For positive integers $n, m$, the double star $S(n,m)$ is the graph consisting of the disjoint union of two stars $K_{1,n}$ and $K_{1,m}$ together with an edge joining their centers. The $k$-color bipartite Ramsey number of $ S(n,m)$, denoted by $r_{bip}(S(n,m);k)$, is the smallest integer $N$ such that, in any $k$-coloring of the edges of the complete bipartite graph $K_{N,N}$, there is a monochromatic copy of $S(n,m)$. The study of bipartite Ramsey numbers was initiated in the early 1970s by Faudree and Schelp and, independently, by Gy\'arf\'as and Lehel. The exact value of $r_{bip}(S(n,m);k)$ is only known for $n=m=1$ and all $k\ge2$. Here we prove that if $k=2$ and $n\ge m$, or $k\ge3$ and $n\ge 2m$, then \[ r_{bip}(S(n,m);k)=kn+1.\] For $k \geq 3$ and $m \leq n < 2m$, we prove that, \[\max\{kn + 1, (2k-4)m+1\} \leq r_{bip}(S(n,m) ; k) \leq \max\left\{ kn + 1, \left[2k - 1 - \frac{1}{2k} - O\left(\frac{1}{k^2}\right)\right]m + 1 \right \},\] where the lower bound is due to DeBiasio, Gy\'arf\'as, Krueger, Ruszink\'o, and S\'ark\"ozy in 2019.

The B-tree is a one of the more popular methods in use today for indexes and inverted files in database management systems. The traditional implementation of a Bâ tree uses many pointers (more than one per key), which can directly affect the performance of the B-tree. A general method of file organization and access (called Dynanic Address Computation) has been described by Cook that can be used to implement B-trees using no pointers. A minimal amount of storage (in addition to the keys) is required. An implementation of Dynamic Address Computation and a B-tree management package is described. Analytical performance measures are derived in an attempt to understand the performance characteristics of the B-tree. It is shown that the additional costs associated with Dynamic Address Computation result in an implementation that is competitive with traditional implementations only for small applications. For very large B-trees, additional work is required to make the performance acceptable. Some examples of possible modifications are discussed. / Master of Science

Dies ist eine aktualisierte Version von einer gesperrten Publikation: 10.18452/14561. Grund der Sperrung: Persönliche Daten vom Deckblatt entfernt / Inhalt der Dissertation ist die Untersuchung der Evolutionsprozesse zufälliger diskreter Strukturen. Solche Evolutionsprozesse lassen sich üblicherweise wie folgt beschreiben. Anfangs beginnt man mit einer sehr einfachen Struktur (z.B. dem Graphen auf n Ecken, der keine Kanten hat) und einer Menge von "Bausteinen'' (z.B. der Kantenmenge des vollständigen Graphen auf n Ecken). Mit zunehmender Zeit werden zufällig mehr und mehr Bausteine eingefügt. Die grundlegende Frage, mit der sich diese Dissertation beschäftigt, ist die folgende: Wie sieht zu einem gegebenen Zeitpunkt die durch den Prozess erzeugte Struktur mit hoher Wahrscheinlichkeit aus? Obwohl das Hauptthema der Dissertation die Evolution zufälliger diskreter Strukturen ist, lassen sich die erzielten Ergebnisse auch unter den folgenden Gesichtspunkten zusammenfassen: Zufällige Greedy-Algorithmen: Es wird ein zufälliger Greedy-Algorithmus untersucht, der für einen gegebenen Graphen H einen zufälligen H-freien Graphen erzeugt. Extremale Ergebnisse: Es wird die Existenz von Graphen mit hoher Taillenweite und hoher chromatischer Zahl bewiesen, wobei bestehende Schranken verbessert werden. Asymptotische Enumeration: Es werden präzise asymptotische Schranken für die Anzahl dreiecksfreier Graphen mit n Ecken und m Kanten bewiesen. "Probabilistische'' Versionen klassischer Sätze: Es wird eine probabilistische Version des Satzes von Sperner bewiesen. / In this thesis, we study the evolution of random discrete structures. Such evolution processes usually fit into the following general framework. Initially (say at time 0), we start with a very simple structure (e.g. a graph on n vertices with no edges) and a set of "building blocks'' (e.g. the set of edges of the complete graph on n vertices). As time increases, we randomly add more and more elements from our set of building blocks. The basic question which we shall investigate is the following: what are the likely properties of the random structure produced by the process at any given time? Although this thesis is concerned with the evolution of random discrete structures, the results obtained can also be summarized according to the following keywords: Random greedy algorithms: we study the output of a random greedy algorithm which, for a given graph H, produces a random H-free graph. Extremal results: improving on previous bounds, we prove the existence of graphs with high girth and high chromatic number. Asymptotic enumeration: we prove sharp asymptotic bounds on the number of triangle-free graphs with n vertices and m edges for a large range of m. Probabilistic versions of "classical'' theorems: we prove a probabilistic version of Sperner's theorem on finite sets.