150813 research outputs found
Sort by
Graph coloring and semidefinite rank
No full textThis paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger et al. (J ACM 45(2):246–265, 1998) give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have rank high enough that the primal solution encodes a coloring. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a k-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if a graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank, since it is known that the uniquely colorable planar graphs are precisely the planar 3-trees. We then modify the semidefinite program to have an objective function with costs, and explore when we can create an objective function such that the optimal dual solution has sufficiently high rank. We show that it is always possible to construct such an objective function given the graph coloring. The construction of the objective function gives rise to heuristics for 4-coloring planar graphs. We enumerated all maximal planar graphs with an induced K 4 of up to 14 vertices; the heuristics successfully found a 4-coloring for 99.75% of them. Our research was motivated by trying to use semidefinite programming to prove the four-color theorem, which states that every planar graph can be colored with four colors. There is an intriguing connection of the Karger–Motwani–Sudan semidefinite program with the Colin de Verdière graph invariant (J Combin. Theory Ser B 50:11-21, 1990) (and a corresponding conjecture of Colin de Verdière), in which matrices that have some similarities to the dual feasible matrices of the semidefinite program must have high rank in the case that graphs are of a certain type; for instance, planar graphs have rank that would imply that the primal solution of the semidefinite program encodes a 4-coloring
An updated version of the global interior ocean biogeochemical data product, GLODAPv2.2020
No full textThe Global Ocean Data Analysis Project (GLODAP) is a synthesis effort providing regular compilations of surface-to-bottom ocean biogeochemical data, with an emphasis on seawater inorganic carbon chemistry and related variables determined through chemical analysis of seawater samples. GLODAPv2.2020 is an update of the previous version, GLODAPv2.2019. The major changes are data from 106 new cruises added, extension of time coverage to 2019, and the inclusion of available (also for historical cruises) discrete fugacity of CO2 (fCO2) values in the merged product files. GLODAPv2.2020 now includes measurements from more than 1.2 million water samples from the global oceans collected on 946 cruises. The data for the 12 GLODAP core variables (salinity, oxygen, nitrate, silicate, phosphate, dissolved inorganic carbon, total alkalinity, pH, CFC-11, CFC-12, CFC-113, and CCl4) have undergone extensive quality control with a focus on systematic evaluation of bias. The data are available in two formats: (i) as submitted by the data originator but updated to WOCE exchange format and (ii) as a merged data product with adjustments applied to minimize bias. These adjustments were derived by comparing the data from the 106 new cruises with the data from the 840 quality-controlled cruises of the GLODAPv2.2019 data product using crossover analysis. Comparisons to empirical algorithm estimates provided additional context for adjustment decisions; this is new to this version. The adjustments are intended to remove potential biases from errors related to measurement, calibration, and data-handling practices without removing known or likely time trends or variations in the variables evaluated. The compiled and adjusted data product is believed to be consistent to better than 0.005 in salinity, 1 % in oxygen, 2 % in nitrate, 2 % in silicate, 2 % in phosphate, 4 µmol kg−1 in dissolved inorganic carbon, 4 µmol kg−1 in total alkalinity, 0.01–0.02 in pH (depending on region), and 5 % in the halogenated transient tracers. The other variables included in the compilation, such as isotopic tracers and discrete fCO2, were not subjected to bias comparison or adjustments
Modeling rational agents with limited capability
No full textIn many scenarios, players exhibit inherent limitations in various aspects of their capability to generate maximally rational play in strategic games. Modeling such capability limitations and elucidating their implications will advance our understanding of the strategic interactions among players. In this thesis, I study two novel settings where players have limited capabilities. I formalize a hierarchy of capabilities and study related equilibrium concepts, computational complexity, solution algorithms, and the impact of varying capabilities on game outcomes.
The first limited-capability setting is limited-perception games. I focus on a class of oneshot limited-perception games. Such games extend simultaneous-move normal-form games by presenting each player with an individualized perception of the true game. Players’ payoffs are determined by the true game hidden from players. The accuracy of a player’s perception is determined by the player’s capability level, with a higher level corresponding to a more accurate perception. I study both capability-oblivious and capability-aware players. A capability-oblivious player does not know they have limited perception and therefore plays the optimal strategy of their perceived game. I present payoff bounds and other predictable behavior of capability-oblivious players in a special class of limited-perception games. A capability-aware player reasons with the set of possible true payoff functions and other players’ perceptions and incentives to maximize their own objective (e.g., the worst-case payoff) based on their limited perception. I present novel formalizations of simultaneousmove equilibria and show the hardness of equilibrium solving. I further present positive results that (i) an approximate equilibrium has a compact, tractable representation; and (ii) a few classes of zero-sum games can be efficiently solved.
The aforementioned efficiently solvable zero-sum games are reduced to solving nonsmooth convex programs. To this end, I present the Trust Region Adversarial Functional Subdifferential (TRAFS) algorithm for constrained optimization of unstructured nonsmooth convex Lipschitz functions. Unlike previous methods that assume a subgradient oracle model, I propose the functional subdifferential, defined as a set of subgradients that simultaneously captures sufficient local information for effective minimization while being easy to compute for a wide range of functions. Intriguingly, the TRAFS design also incorporates game-theoretical thinking. In each iteration, TRAFS solves a zero-sum game between the optimizer and a local approximation of the objective function to guarantee progress. The optimizer has access to step vectors in a local ℓ2 -bounded trust region; the local approximation uses the functional subdifferential. TRAFS finds an approximate solution with an absolute error up to ϵ in O(1/ϵ) or O(\sqrt{1/ϵ}) 1/ϵ iterations depending on whether the objective function is strongly convex, improving the previously best-known bounds of O((1/ϵ)^2) and O(1/ϵ) in these settings. TRAFS makes faster progress if the functional subdifferential satisfies a locally quadratic property; as a corollary, TRAFS achieves linear convergence (i.e., O(log 1/ϵ)) for strongly convex smooth functions. In the numerical experiments, TRAFS solves twice as many problems compared to the second-best method and is on average 39.1x faster on problems solved by both methods.
The second limited-capability setting is limited-strategy games where a player’s capability limits the strategies available to them. I work with a formalization where a player’s strategy space is defined as programs in a Domain-Specific Language (DSL). A player’s capability limits the size of programs available to that player. I focus on characterizing the impact of player capability on game outcomes. I study a new game model called McDncDa derived from network congestion games. I show that it is computationally hard to determine whether an McDncDa instance is capability-positive (i.e., whether increasing a player’s capability level leads to a better payoff). I then study a parameterized special class of McDncDa called MGMG. I show that MGMG is always capability-positive, and it is socially capabilitypositive (i.e., the sum of all players’ payoffs always gets better if every player’s capability level is increased by one) if some resources in the game have increasing returns to scale despite the existence of multiple equilibria.Ph.D
Electrospray Thrusters in Chemical-Electric Multimode Propulsion for Small Satellites
No full textPropulsion for small spacecraft is typically one of two modes, chemical or electric. These modes offer complementary propulsive performance: chemical propulsion provides high thrust and low specific impulse, while electric propulsion provides the inverse. As such, having access to both modes on the same spacecraft (i.e. multimode propulsion) is extremely useful. Unfortunately, the conventional propellants used by chemical and electric thrusters are highly incompatible, making this particularly difficult on small spacecraft that lack the mass, power, and volume to accommodate two separate propulsion systems. However, recent advancements in green monopropellants -- developed as less-toxic alternatives to hydrazine in chemical monopropellant thrusters -- have created a new family of ionic liquids monopropellants, making them the natural propellant for a highly compact form of electric propulsion known as electrospray thrusters. This presents a unique opportunity for a propellant to be shared between two propulsion modes, decreasing required mass and volume to be feasible for small spacecraft. This thesis examines the use of ionic liquid monopropellants in electrospray thrusters for a multimode chemical-electric propulsion system. This thesis focuses particularly on ASCENT, a high-maturity monopropellant with flight heritage in chemical thrusters.
In this work, the performance of ASCENT in the MIT ion Electrospray Propulsion System (iEPS) is extensively characterized. Experimental work includes ion plume diagnostics, indirectly and directly obtained performance estimates, temperature-dependent performance estimates, and extended duration firing behavior. Preliminary studies of similar monopropellants are also conducted to assess their use in a multimode system. To support an upcoming technology demonstration flight, a new multimode-compatible iEPS thruster tank is designed, fabricated, and validated. The integration and operation requirements for this thruster in a flight-ready system are defined. Finally, the mission benefits of an ASCENT multimode system for CubeSats are compared against current commercial options using an Earth observation mission case study.
This work finds that an iEPS thruster with ASCENT propellant has thrust of 9-15 µN, a specific impulse of 600-750 seconds, and a total efficiency of 18-22%, depending on current setpoint. We find that ASCENT is slightly volatile in high vacuum, which causes time-dependent losses in efficiency and specific impulse from gradual propellant evaporation. This volatility may also increase thruster lifetime by mitigating the risk of thruster failure by emitter flooding. This work also identified a modified version of ASCENT, created when the propellant is exposed to iron. This modified version produces a dramatically higher thrust and thrust-to-power compared to standard ASCENT. Additionally, flight-ready configurations of a multimode system are defined for 6U, 12U, and 27U CubeSats. A case study analysis found that the benefits of a chemical-electrospray multimode system are best realized at the 12U scale and above. Overall, this thesis provides critical insights on the performance, integration, and operation of electrospray thrusters with ionic liquid monopropellants. These results can then be used to enable a multimode propulsion system for small satellites.Ph.D
Higher dimensional Fourier quasicrystals from Lee–Yang varieties
No full textIn this paper, we construct Fourier quasicrystals with unit masses in arbitrary dimensions. This generalizes a one-dimensional construction of Kurasov and Sarnak. To do this, we employ a class of complex algebraic varieties avoiding certain regions in C n , which generalize hypersurfaces defined by Lee–Yang polynomials. We show that these are Delone almost periodic sets that have at most finite intersection with every discrete periodic set
Co-Living in Seoul: Addressing Housing Needs and Redefining Rental Market Trends
No full textCo-living emerged as a novel asset class in the mid-2010s, addressing the housing needs of urban residents affected by rising housing costs, increasing urban migration, and the growing prevalence of single-person households. In South Korea, co-living has gained attention as a viable alternative to traditional housing, driven by unique local dynamics, including the decline of the dominant Jeonse system and a significant shortage of housing tailored to single-person households. With a growing preference for monthly rental systems over the Jeonse systems, both local conglomerates and start-ups have capitalized on the opportunity to offer company-operated co-living spaces. As the market grows, major international investors and global co-living providers have also entered, reflecting a unique market environment where institutionalized housing options are expanding alongside a notable shift in rental transaction systems. In this new era of urban housing, co-living is rapidly expanding and gaining popularity. This thesis seeks to answer the following question: What factors have driven the emergence and growth of the co-living market in Seoul, and what is its growth potential? To address this, it starts with an analysis of market drivers, provider strategies, and regulatory developments, followed by projections of market potential and an assessment of potential threats and mitigation strategies for long-term viability of co-living in Seoul. The goal is to offer insights for co-living providers to optimize their spaces and services. The findings suggest that while co-living addresses unmet housing demand, its long-term success depends on balancing operational efficiency with tenant satisfaction. While these strategies are applicable in other cities, they are particularly critical in Seoul, where the Jeonse system remains a strong and historically preferred alternative. In Seoul, co-living serves a dual mission: introducing an innovative housing model and reshaping the paradigm of the Wolse rental housing system. To succeed, co-living operators must clearly articulate their unique value proposition, addressing both the housing needs of urban residents and the broader evolution of the rental market.S.M
Spectral Analysis of Local Atomic Environments
No full textThe representation of local environments is a cornerstone challenge in computational materials science, with profound implications for property prediction and materials discovery. This thesis presents a comprehensive investigation of spectral descriptors constructed from spherical harmonic expansions to represent the geometries of local atomic environments. Systematic computational experiments evaluate the robustness of these descriptors to geometric perturbations and their capacity to differentiate structurally similar configurations. The findings reveal a clear performance hierarchy, with higher-order descriptors offering increased geometric expressivity and reconstruction accuracy in resolving challenging structural cases. This research further examines methods for inverting spectral representations back to atomic coordinates, demonstrating that directly optimizing three-dimensional positions through gradient-based techniques yields markedly better reconstruction accuracy than approaches operating in Fourier space. Dimensionality reduction via latent space embeddings is also explored, showing that essential geometric features can be preserved in significantly compressed representations. Through methodical analysis of descriptor limitations, performance boundaries, and sensitivity to hyperparameters, this work establishes practical benchmarks and implementation guidelines for spectral descriptors. These contributions strengthen the foundation for reliable machine learning models in computational materials science, advancing both the accuracy and efficiency of atomic-scale modeling for materials design and discovery.M.Eng
HapticHearing: A Haptic Feedback System for Complementing Auditory Speech Perception for Mild-to-Moderate Hearing Loss
No full textASSETS ’25, Denver, CO, USAAge-related hearing loss is often caused by cochlear hair cell degradation. This creates a challenge for hearing aids, which rely on sound amplification. Once hearing ability in a specific frequency is lost, amplification alone provides little benefit. Previous haptic systems have tried to solve this with complete sensory substitution, converting audio signals like phonemes to tactile patterns. However, these systems require significant amount of time to learn, and induce high cognitive load in haptic perception. Our system, HapticHearing, takes an alternative approach of leveraging a user’s residual hearing and complementing it with tactile feedback. We present a custom multi-actuator haptic device, designed to translate phonemic information from speech into tactile patterns that are customized to a user’s hearing loss and speech perception abilities. The system consists of a microphone for speech capture, four-band energy envelope extraction with vowel embedding, a custom USB-to-haptic driver PCB, and wearable devices containing eight vibrotactile actuators that deliver personalized tactile feedback based on the user’s audiogram. Psychophysical validation (n=9) showed neck-worn devices achieved better spatial localization (67% vs 53%) while while bracelet and necklace devices had lower detection thresholds than over-ear (thresholds 0.09 vs 0.18)
Report to the President for year ended June 30, 2025, Office of Educational Opportunity Programs
No full textThis report contains the following sections: Office of Educational Opportunity Programs, MIT/Wellesley Upward Bound Program, Enrollment Statistics, Summer Session, Classes and Academic Support, Recreational Workshops, College & Career Advising, School-year Session, Homework Supervision, Academic Advising, Career Advising, Class of 2025, and Postgraduate Involvement
Detecting Errors in Financial Data: A Multi-Agent LLM and Synthetic Data Approach
No full textWith the high volume of activity flowing through financial institutions, detecting potential errors remains a critical challenge. This paper addresses two key areas where errors may occur: business name registrations and transactions within valid accounts. Traditional string-matching methods struggle to accurately identify incorrectly written business names that closely resemble existing ones, while existing error detection models for transaction data often suffer from class imbalance, leading to reduced performance on minority incorrect transaction cases. To address these issues, this paper proposes two novel approaches. First, a hybrid method integrating multi-agent Large Language Models (LLMs) with existing string-matching techniques enhances the detection of incorrect business names by capturing subtle variations beyond conventional edit-distance metrics, improving the recall from 0.815 for the baseline model to 0.987 using the proposed method. Second, an improved tabular data generation method for credit card transactions is introduced, leveraging LLMs and class balancing to generate high-quality synthetic data. Using this data to train error detection systems results in a decrease of the false negative rate from 23.47% to 12.84%. Together, these methods enhance the performance of error detection systems, enabling financial institutions to enhance the experiences of their clients.M.Eng.S.B