Given a vertex in a (𝑘,𝜑,𝜖)-clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of 𝜑-expanders of size ≈𝑛/𝑘 with outer conductance bounded by 𝜖, can one quickly tell which cluster it belongs to? This is a classical question going back to the expansion testing problem of Goldreich and Ron’11 (the case of 𝑘 =2) that has received a lot of attention in the literature. For 𝑘 =2 a sample of ≈𝑛1/2+𝑂⁢(𝜖/𝜑2) logarithmic length walks from a given vertex approximately determines its cluster membership by the birthday paradox: two vertices whose random walk samples are ’close’ are likely in the same cluster, and otherwise in different clusters. The study of the general case 𝑘 >2 was initiated by Czumaj, Peng and Sohler [STOC’15], and the works of Chiplunkar et al. [FOCS’18], Gluch et al. [SODA’21] showed that ≈poly⁡(𝑘) ⋅𝑛1/2+𝑂⁢(𝜖/𝜑2) random walk samples, and the same query time, suffices for general 𝑘. This matches the 𝑘 =2 result up to polynomial factors in 𝑘, but one notices a conceptual inconsistency: if the birthday paradox is indeed the phenomenon guiding the query complexity here, then the query complexity should decrease, as opposed to increase, with the number of clusters 𝑘! Since clusters have size ≈𝑛/𝑘, we expect to need ≈(𝑛/𝑘)1/2+𝑂⁢(𝜖/𝜑2) random walk samples, which gets smaller when 𝑘 gets larger, and reduces to constant when 𝑘 ≈𝑛. The currently best known query time (of Gluch et al. [SODA’21]), however, increases with 𝑘 due to computationally heavy linear-algebraic post-processing of random walk samples. In this paper we design a novel representation of vertices in a (𝑘,𝜑,𝜖)-clusterable graph by a mixture of samples of logarithmic length walks. This representation not only uses the optimal ≈(𝑛/𝑘)1/2+𝑂⁢(𝜖/𝜑2) number of walks per vertex, but also allows for fast nearest neighbor search: given a collection of 𝑘 vertices representing the clusters, and a query vertex 𝑥, we can find the cluster of 𝑥, using nearly linear time in the representation size of 𝑥. This gives a spectral clustering oracle with query time ≈(𝑛/𝑘)1/2+𝑂⁢(𝜖/𝜑2) and space complexity ≈𝑘 ⋅(𝑛/𝑘)1/2+𝑂⁢(𝜖/𝜑2), matching the birthday paradox bound.

In the graph clustering problem with a planted solution, the input is a graph on 𝑛 vertices partitioned into 𝑘 clusters, and the task is to infer the clusters from graph structure. A standard assumption is that clusters induce well-connected subgraphs (i.e. Ω⁡(1)-expanders), and connections between clusters are sparse (i.e. clusters form 𝜖-sparse cuts). Such a graph defines the clustering uniquely up to ≈𝜖 misclassification rate, and efficient algorithms for achieving this rate are known. While this vanilla version of graph clustering is extremely well studied, in the practice of graph analysis vertices of the graph are typically equipped with labels, or features, that provide additional information on cluster ids of the vertices. For example, each vertex could be equipped with a cluster label that is corrupted independently with probability 𝛿. Using either of the two sources of information separately leads to misclassification rate min⁡{𝜖,𝛿}, but can one combine the two to achieve misclassification rate ≈𝜖⁢𝛿? In this paper, we give an affirmative answer to this question, and furthermore show that such a misclassification rate can be achieved in sublinear time in the number of vertices 𝑛. Our key algorithmic insight is a new observation on “spectrally ambiguous” vertices in a well-clusterable graph. While our sublinear-time classifier achieves the nearly optimal ≈˜𝑂⁡(𝜖⁢𝛿) misclassification rate, the approximate clusters that it outputs do not necessarily induce expanders in the graph 𝐺. In our second result, we give a polynomial-time algorithm for reweighting edges of the input graph from the original (𝑘,𝜖,Ω⁡(1)-clusterable instance to a (𝑘,˜𝑂⁡(𝜖⁢𝛿),Ω⁡(1))-clusterable instance (for constant 𝑘), improving sparsity of cuts nearly optimally and preserving expansion properties of the communities – an algorithm for refining community structure of the input graph.

Let 𝐴 ∈ℤ𝑚×𝑛 be an integer matrix with entries bounded by Δ in absolute value. Cook et al. (1986) have shown that there exists a universal matrix 𝐵 ∈ℤ𝑚′×𝑛 with the following property: For each 𝑏 ∈ℤ𝑚, there exists a 𝑡 ∈ℤ𝑚′ such that the integer hull of the polyhedron 𝑃 ={𝑥 ∈ℝ𝑛 :𝐴⁢𝑥 ≤𝑏} is described by 𝑃𝐼 ={𝑥 ∈ℝ𝑛 :𝐵⁢𝑥 ≤𝑡}. Our main result is that 𝑡 is an affine function of 𝑏 as long as 𝑏 is from a fixed equivalence class of the lattice 𝐷 ⋅ℤ𝑚. Here 𝐷 ∈ℕ is a number that depends on 𝑛 and Δ only. Furthermore, 𝐷 as well as the matrix 𝐵 can be computed in time depending on 𝑛 and Δ only. An application of this result is the solution of an open problem posed by Cslovjecsek et al. (SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems. The main tool of our proof is the classical theory of Chvátal-Gomory cutting planes and the elementary closure of rational polyhedra.

A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of NC0 circuits, and the refutation of pseudorandom CSP instances, leading to improvements to some longstanding lower bounds in the cell-probe/bit-probe models. Here, we improve these lower bounds in certain cases via a more streamlined reduction to XOR refutation, coupled with handling the odd-arity case. Our result can be viewed as a complete derandomization of the state-of-the-art semi-random 𝑘-XOR refutation analysis (Guruswami, Kothari and Manohar, STOC 2022, Hsieh, Kothari and Mohanty, SODA 2023), which complements the derandomization of the even-arity case obtained by Korten et al. As our main technical statement, we show that for any multi-output constant-depth circuit that substantially stretches its input, its output is very likely far from strings sampled from distributions with sufficient independence, and further this can be efficiently certified. Via suitable shifts in perspectives, this gives applications to cell-probe lower bounds and range avoidance algorithms for NC0 circuits.

For a real matrix 𝐀 ∈ℝ𝑑×𝑛 with non-collinear columns, we show that 𝑛 ≤𝑂⁡(𝑑4⁢𝜅𝐀) where 𝜅𝐀 is the circuit imbalance measure of 𝐀. The circuit imbalance measure 𝜅 is a real analogue of Δ-modularity for integer matrices, satisfying 𝜅𝐀 ≤Δ𝐀 for integer 𝐀. The circuit imbalance measure has numerous applications in the context of linear programming (see Ekkbatani, Natura and Végh (2022) for a survey). Our result generalizes the 𝑂⁡(𝑑4⁢Δ𝐀) bound of Averkov and Schymura (2023) for integer matrices and provides the first polynomial bound holding for all parameter ranges on real matrices. To derive our result, similar to the strategy of Geelen, Nelson and Walsh (2021) for Δ-modular matrices, we show that real representable matroids induced by 𝜅-bounded matrices are minor closed and exclude a rank-2 uniform matroid on 𝑂⁡(𝜅) elements as a minor (also known as a line of length 𝑂⁡(𝜅)). As our main technical contribution, we show that any simple rank-𝑑 complex representable matroid which excludes a line of length 𝑙 has at most 𝑂⁡(𝑑4⁢𝑙) elements. This complements the tight bound of (𝑙 −3)⁢(𝑑2) +𝑑 for 𝑙 ≥4, of Geelen, Nelson and Walsh, which holds when the rank 𝑑 is sufficiently large compared to 𝑙 (at least doubly exponential in 𝑙). Our proof of the above relies on an improvement of a Sylvester-Gallai type theorem of Dvir, Saraf and Wigderson (2014). Refining their design matrix technique, we show that for any full dimensional set of 𝑛 points in ℂ𝑑 there always exists a point that lies on at least (1 −4/𝑑)⁢𝑛 many distinct lines (the constant 4 is improved from 12). The excluded minor bound follows by inductively applying this result to find good elements to contract in the matroid, where the improved constant reduces the dependence on 𝑑 from 𝑑12 to 𝑑4. Interestingly, by relying on geometric techniques, our proof avoids the use of any difficult matroid machinery.

In response to current climate considerations, the geotechnical sector is increasingly exploring multiphysical approaches to develop sustainable engineering projects. This thesis focuses on two promising applications that combine the sector's decarbonisation objectives with geomechanical functionality: energy geostructures and biocementation. Multiphysical modelling has played a key role in their development and remains an essential tool to advance innovation adoption.

For energy geostructures, modelling and design frameworks are well established. The remaining challenge is to extend the domain of application beyond its well-known uses, primarily energy pile foundations in balanced climates, and demonstrate their effectiveness in alternative scenarios. In contrast, modelling frameworks for biocementation are often not validated at the large scale. Upscaling also continues to pose challenges, and recommendations for overcoming these are not readily available. These problems obstruct the step towards design principles.

In this setting, the thesis has a twofold objective: (i) to extend the range of applications for energy geostructures by moving beyond conventional considerations and (ii) to move towards developing design approaches for biocementation treatment. By building on existing knowledge and using multiphysical modelling as a central tool, the research offers new insights into the design, optimisation, and application of these technologies and aims to support future sustainable geotechnics.

Numerical analyses are used to look at three different settings for the application of energy geostructures. The potential of energy piles to provide cooling energy in hot-dominated climates is demonstrated through simulations, which show that, despite unbalanced thermal demands, temperatures stabilise over time and respect heat pump limitations. Simulations reveal that geothermal activation of an underground data centre can reduce internal air temperatures, and this effect can be used to optimise ventilation system performance but requires a case-by-case evaluation. Finally, models are used to understand the internal air dynamics of an energy metro station, and recommendations are provided for how such factors can be accounted for in its design. These works demonstrate that through modelling, the technology can be optimised to maximise its impact in providing renewable thermal energy.

The work then demonstrates how multiphysical modelling can aid in achieving standardisation of biocementation. A modelling framework is benchmarked against upscaling experiments to assess its performance. Recommendations for achieving homogeneity in biocementation soil improvement are provided, highlighting the benefits of using high, consistent injection rates and demonstrating the effect of using novel injection geometries. The framework is then adapted to simulate treatments using an ex situ hydrolysis method, revealing a shift in the governing precipitation mechanism from urea hydrolysis to calcium carbonate precipitation kinetics in relation to mixing patterns. Last, the effects of different treatment configurations for slope stabilisation via biocementation are analysed using both limit equilibrium and finite element methods. While biocementation can improve slope stability, its success largely depends on the manner of application. These findings highlight the contribution of modelling in developing effective approaches for biocementation treatment.

The electrochemical reduction of CO2 for producing carbon-neutral fuels and chemicals is a pivotal technology for the future decarbonization of the chemical and energy sectors. Among the various electrolyzer architectures, forward bias bipolar membrane (BPM) systems have emerged as a promising solution, combining high selectivity and CO2 utilization with a pure-water feed, salt-free design. However, performance limitations arising from water transport imbalance, membrane degradation, and kinetics overpotentials at the membrane interface hinder their industrial deployment.

This thesis addresses these challenges through systematic investigations across four key axes. The first part focuses on water transport, using synchrotron-based, operando X-ray tomography and diffusion measurements to analyze water management and hydration dynamics in a commercial BPM-based cell. It reveals that cathode flooding is not a limiting factor at the investigated current densities (up to about 200 mA cmâ 2), as the GDL saturation stays below 10%. Instead, insufficient water supply to the cathode and membrane over-swelling are identified as the dominant challenges for high current density operation.

The second part focuses on degradation mechanisms within the membrane-electrode assembly. Pre- and post-mortem analysis, again by X-ray tomography, reveals the evolution of structural damage. We show that membrane delamination occurs at current densities above 100 mA cmâ 2. To resolve this, a series of semi-porous BPMs with engineered gas-permeable anion exchange layers is designed and investigated. These structures enable enhanced back-transport of recombined CO2 toward the cathode, thereby relieving interfacial pressure buildup at the membrane junction. Among the tested designs, a microporous ionomer-nanoparticle composite layer proves particularly effective in suppressing membrane delamination under up to 200 mA cmâ 2 and reducing anode catalyst layer damage area by up to 90% compared to commercial BPMs.

The third part addresses the kinetic limitations at the BPM junction by integrating metal-oxide catalyst layers (e.g., TiO2, SiO2, IrO2) directly at the membrane interface. Complete catalyst coverage at 20â 30 ÎŒg/cm2 enables up to 100% higher current density at similar iR-corrected voltages, providing a scalable strategy to overcome interfacial limitations.

Finally, the fourth part investigates the role of the catalyst-layer microenvironment and its influence on reaction kinetics in cation-free systems. By designing a fully gas-fed setup with pretreated membranes, the study isolates and evaluates the impact of trace alkali cations migrating across the membrane. Furthermore, the use of anion exchange ionomers with high ion-exchange capacity (IEC) is found to promote beneficial double-layer capacitance and stabilize the catalytic interface over multi-hour operation. The results support a mechanism where both mobile and fixed cations shape the local environment on the silver catalyst surface, thereby enabling stable CO production under pure-water-fed, salt-free conditions.

Altogether, this work presents a comprehensive framework for enhancing the performance of a pure-water fed CO2 electrolyzer with a BPM in forward bias. By coupling advanced diagnostics with targeted material strategies, the thesis contributes to both fundamental understanding and practical design principles to guide the next generation of scalable and durable CO2 electrolysis systems.

The development of soft electronic and optoelectronic systems is essential for the growth and industrial deployment of research fields such as smart textiles and wearables. However, it remains challenging to identify materials that reconcile the required mechanical attributes (e.g. softness and stretchability) with functional metrics essential to develop high-performance devices (e.g. electrical conductivity or photoconductivity). Moreover, it is equally important to find processing routes that can produce such devices at large scale and low-cost while ensuring an accurate arrangement of materials with disparate electronic properties into complex architectures with small feature sizes.

In this thesis, we investigate the thermal drawing technique as a strategy to produce soft, multifunctional electronic and optoelectronic fibers. Originally developed for optical fibers, this process leverages the viscous flow of materials to transform macroscopic assemblies into long fibers while preserving the initial cross-sectional architecture. In particular, this work focuses on implementing the three fundamental pillars of soft optoelectronic devices within thermally drawn fibers: (i) Stretchable and electrically conductive materials serving as electrodes for charge collection and transport: Two composite systems relying on rigid and liquid fillers dispersed in a soft matrix are proposed, and their performance is demonstrated through various types of mechanical sensors. In particular, highly stretchable and conductance-stable electrodes are established in thermally drawn fibers by relying on liquid metal embedded elastomers. (ii) Transparent conductors that simultaneously enable light transmission and charge transport: The introduction of ionogels as a novel materials system in thermally drawn fibers is demonstrated. The versatility of this material enables a fine tuning of its mechanical, electrical and thermal properties to match the targeted attributes for specific applications. In particular, meters-long stretchable fibers encompassing a transparent and conductive core are produced, marking the first implementation of a transparent electrode in thermally drawn fibers. (iii) Stretchable semiconductors functioning as active layers with light-responsive properties: Blends of organic semiconductors with thermoplastic elastomers are envisioned as a facile route to produce soft semiconductors with low processing temperature that can be easily introduced into thermally drawn fibers. Each material system is first studied individually, then integrated into a single soft fiber demonstrating optoelectronic properties. This work paves the way towards the development of complex multi-functional soft fibers to fabricate smart textiles and wearables with advanced electronic and optoelectronic properties.

This thesis presents a comprehensive study on the application of composite magnets in two industrial scenarios: the development of a linear actuator and the enhancement of ski equipment with magnetic attachment systems. In both cases, non-uniform magnetization is employed, specifically in the form of a continuous adaptation of the Halbach array.

In the first application, the thesis explores the replacement of sintered magnets, typically used in permanent magnet motors, with composite magnets to reduce production costs while maintaining performance. The final prototype is functional but delivers a force reduced by 30% compared to the original. The thesis also presents an optimization of the stator's ferrous body, allowing for in-situ winding and further reducing manufacturing costs.

The second application aims to replace the traditional glue used with climbing skins with a flexible composite magnetic strip to enhance user experience. This technology is applied to two cases: cross-country skiing and mountaineering. For the latter, the results are promising but require further development, particularly in achieving sufficient magnetic force. In contrast, the cross-country skiing case result in a working product and to the development of a production line ready to supply the first batch of magnetic skins.

The thesis covers the design and optimization of magnetic patterns, as well as the development of a magnetizer tailored to this application, using finite element analysis and prototyping. For the cross-country case, a cooling system is developed to achieve a production rate that aligns with industrial needs.

The results of the thesis demonstrate the potential of composite magnets and the possibilities offered by unconventional magnetic patterns, paving the way for future advancements in magnetic material technology.

The Marshall Plan was the cornerstone of U.S. Cold War economic and foreign policy. It was a program of technical assistance to set up free trade through European integration, of mutual security to prevent the spread of communism through the Atlantic Alliance, and of information, education, and cultural exchange to promote the American Way of Life. Devoting specific attention to labor affairs to prevent strikes and communist tendencies among workers, Labor Division of the Marshall Plan advocated a transnational workers' housing program, notably in France, Greece, Italy, and Turkey as well as the Allied-controlled Austria and Allied-occupied Germany, for union-sponsored housebuilding and homeownership.

The program was framed around the discourse of non-communism, free labor, and the free world, disseminated jointly with the International Confederation of Free Trade Unions (ICFTU). Providing financial and technical assistance to trade unions for establishing and managing housing cooperatives, training construction labor in housing development and design, and industrializing building trades were key elements of this program, jointly organized with the ICFTU's European Regional Organisation, trade union federations and governments.

Union-sponsored cooperative housing was promoted for industrial workers as a means to assert authority and autonomy in housing provision, to build a home of one's own and a house with a garden, symbolizing upward mobility. This vision promised labor stability through union affiliation and mortgage loans, while advertising domestic ideals of a preindustrial way of life. Built on U.S. New Deal and wartime legacies on union-sponsored housing and advanced by Scandinavian models of non-profit housing associations, the program functioned as a multilateral U.S. Cold War Project, and grafted real-estate dynamics onto public housing, regardless of local policies and housebuilding traditions of the participating countries.

This thesis offers methodological insights to architectural history and theory. First, I survey non-architectural archives of governmental and multilateral organizations and develop my arguments using correspondence, memoranda, reports and "picture files" as well as photographs, press clippings, and a film script, rather than architectural archives and drawings. Second, I explore trade unions as authors of housing development, design and construction, and integrate social history into architectural historiography for a wider understanding of built environment production and its non-architect agents. The thesis also offers new historical findings and theoretical perspectives. First, I introduce the Marshall Plan's workers' housing program, overlooked except some country-specific studies on its involvement in housing and domesticity. Second, I present the U.S. architect-planner Donald Monson and U.S. labor advisors as key actors, along with previously unexamined U.S. housing consultants. Third, I discuss self-help housing as a tool of postwar imperialism in Western Europe, beyond postcolonial frameworks dividing the "global west/north" from the "global east/south," and I propose multilateral imperialism as an alternative to scholarship that interprets cross-cultural exchange through the lens of global governance. Finally, I demonstrate the agency of union-sponsored cooperatives in shifting workers' housing toward a real-estate market through self-acquisition of land and tenant-ownership model.