BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Drupal iCal API//EN X-WR-CALNAME:Events iCal Start May 2024 X-WR-TIMEZONE:America/New_York BEGIN:VTIMEZONE TZID:America/New_York X-LIC-LOCATION:America/New_York BEGIN:DAYLIGHT TZNAME:EDT TZOFFSETFROM:-0500 TZOFFSETTO:-0400 DTSTART:20260308T070000 END:DAYLIGHT BEGIN:DAYLIGHT TZNAME:EDT TZOFFSETFROM:-0500 TZOFFSETTO:-0400 DTSTART:20250309T070000 END:DAYLIGHT BEGIN:DAYLIGHT TZNAME:EDT TZOFFSETFROM:-0500 TZOFFSETTO:-0400 DTSTART:20240310T070000 END:DAYLIGHT BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20251102T060000 END:STANDARD BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20241103T060000 END:STANDARD BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20231105T060000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:6a5b67604726f DTSTART;TZID=America/New_York:20260720T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260720T120000 LOCATION:Gates and Hillman Centers SUMMARY:Doctoral Thesis Oral Defense - Yige Hong CLASS:PUBLIC DESCRIPTION:Speaker: YIGE HONG\, Ph.D. Candidate\, Computer Science Departm ent\,\nCarnegie Mellon University\n\nTalk Title: Structural methods for la rge stochastic systems\n\nDecision making in large stochastic systems is a central and\nchallenging problem across computer systems\, machine learni ng\, and\noperations research. This thesis studies a wide variety of such\ nsystems that\, despite their diverse problem definitions\, share similar\ nunderlying structures and admit similar fundamental techniques for\nperfo rmance analysis and policy design. We identify two such\nstructures\, each grouping a family of seemingly distinct problems. The\ntwo structures sha re a common spirit: an intractable system can be\napproximated by a simple r\, well-understood one.\n\nThe first part studies the weak-coupling struc ture\, where a system can\nbe approximated by a collection of independent\ , low-dimensional\nsubsystems. We design a control policy on this simple p roxy and\nconvert it into a near-optimal policy for the original\, coupled \nsystem. Applied to stochastic bin packing\, restless bandits\, and\nweak ly-coupled Markov decision processes (WCMDPs)\, this yields\nefficiently c omputable policies that are provably near-optimal at\nscale\, under substa ntially weaker and more easily verifiable\nconditions than were previously required.\n\nThe second part studies the one-dimensional structure\, wher e a key\nquantity of the system can be approximated by a one-dimensional\n process even when the full state is high- or infinite-dimensional.\nApplyi ng this idea to multiserver queues\, we prove new universal\nbounds for th e G/G/n queue\, show that the Gittins policy is\nnear-optimal for G/G/n qu eues with setup times\, and determine the best\nachievable delay together with a near-optimal policy for the\nmultiserver-job model.\n\nThesis Commi ttee:\n\nWeina Wang (Chair)\n\nMor Harchol-Balter\n\nAlan Scheller-Wolf\n\ nJim Dai (Cornell University)\n\nYudong Chen (University of Wisconsin-Madi son)\n\nQiaomin Xie (University of Wisconsin-Madison)\n\nIn-person & Zoom\ n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676048a80 DTSTART;TZID=America/New_York:20260717T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260717T130000 LOCATION:Gates and Hillman Centers SUMMARY:Doctoral Thesis Oral Defense - Christopher Canel CLASS:PUBLIC DESCRIPTION:Speaker: CHRISTOPHER CANEL\, Ph.D. Candidate\, Computer Science \nDepartment\, Carnegie Mellon University\n\nTalk Title: Dual-Endpoint Con gestion Control\n\nCurrent techniques for rate control in computer network s are not\naligned with the policies and considerations of both endpoints in a\nconnection. Historically\, fine-grained rate control has been the\ns ender's responsibility through the Transmission Control Protocol\n(TCP) an d its congestion control algorithm (CCA). However\, the\nreceiver\, either due to conflicting priorities or greater visibility\ninto congestion\, wo uld often be better served by a different rate\nallocation than the sender . A simple example is a many-flow incast in\na datacenter network: each se nder independently seeks to transmit as\nquickly as possible\, while the r eceiver can observe that each flow\nshould converge to a small fraction of the last-hop link rate.\nLikewise\, on the Internet\, each service attemp ts to maximize its own\nthroughput\, whereas a user may desire fairness ac ross services.\n\nTo bridge the gap between endpoint objectives\, we argue for a\ndual-endpoint approach to congestion control that incorporates the \nreceiver into the rate decision as well. Specifically\, we advocate for\ nreceiver-assisted congestion control\, where the receiver provides\nlight weight hints to senders about the rate regime in which they\nshould operat e. Receiver-assisted congestion control differs from\nfully receiver-based techniques because the sender maintains control\nover the packet stream\, and our proposal offers capabilities similar\nto in-network rate control with fewer practical challenges. To\nimplement receiver assistance\, we re visit the well-known technique of\nTCP flow control and show it to be a po werful primitive to enable\nexpressive receiver policies that does not req uire modifications to\nTCP\, the sender's CCA\, or applications.\n\nThis t hesis explores two environments with differing endpoint\nobjectives to sho w that receiver-assisted congestion control gives\nboth endpoints a stake in bandwidth allocation decisions. First\, we\nconsider datacenter incast bursts\, where the receiver’s\nobservability into the traffic pattern en ables dual-endpoint control\nto schedule hundreds or thousands flows into a healthy regime that\nboth improves network utilization and reduces recei ver packet\nprocessing overheads. Second\, we turn to the Internet at larg e and\nshow the expressivity of dual-endpoint control by resolving common\ nchallenges that arise due to conflicting receiver policies regarding\nrat e control granularity\, algorithm\, and optimization metric. \n\nThesis C ommittee:\n\nSrinivasan Seshan (Chair)\n\nJustine Sherry\n\nPeter Steenkis te\n\nNeil Spring (Meta)\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604901e DTSTART;TZID=America/New_York:20260713T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260713T120000 LOCATION:Gates and Hillman Centers SUMMARY:Doctoral Thesis Oral Defense - Kaiyang Zhao CLASS:PUBLIC DESCRIPTION:Speaker: KAIYANG ZHAO\, Ph.D. Candidate\, Computer Science Depa rtment\,\nCarnegie Mellon University\n\nTalk Title: Architecting Memory Ef ficiency in Modern Data Centers\n\nModern datacenter computing faces a cri tical memory bottleneck driven\nby memory-intensive applications\, terabyt e-scale memory capacities\,\nand slowing DRAM technology improvements. The memory bottleneck\nmanifests in multiple dimensions including access perf ormance\,\nhardware costs\, and power consumption.\n\nFirst\, the virtual memory abstraction is under increasing strain\,\nwhere stagnant Translatio n Lookaside Buffer sizes relative to growing\nmemory capacity cause severe and escalating virtual address\ntranslation overheads. Second\, the hardw are costs and power\nconsumption of memory hardware have skyrocketed as DR AM now accounts\nfor nearly 25% of rack power consumption and 50% of a ser ver’s Total\nCost of Ownership. This thesis addresses these challenges t hrough the\nco-design of OS and architectures.\n\nTo reduce the overhead o f virtual memory\, my research targets the\nvirtual address translation ov erhead with two works. Contiguitas\ngroups unmovable allocations in the OS and introduces hardware\nextensions to migrate device I/O pages. By creat ing abundant physical\nmemory contiguity\, it allocates more huge pages\, yielding up to an 18%\nperformance improvement for Meta’s production wor kloads. Learned\nVirtual Memory replaces rigid radix page tables with lear ned page\ntables tailored to application virtual address spaces. LVM balan ces\nthe size\, depth\, and accuracy of learned index\, reducing page walk \noverheads by an average of 44% and achieving a 2-27% execution\nspeedup. To reduce memory cost and power\, my research enables the\npractical depl oyment of tiered CXL memory in datacenters with two\nworks. Pensieve is a three-tier memory system (DRAM\, CXL\, and SSD)\nthat transparently manage s data placement via a single-input\nsingle-output control loop. It levera ges CXL memory as an intermediate\ntier to safely offload 33% of memory wh ile keeping performance\ndegradation under 5%. Equilibria addresses multi- tenant challenges by\nensuring fair sharing of tiered memory and mitigatin g noisy-neighbor\neffects. It provides automatic fair-share determination and thrashing\nmitigation\, boosting performance over the state-of-the-art Linux\nsolution by up to 52% for Meta’s workloads and 1.7x for DCPerf\, a\nrepresentative benchmark for datacenter workloads.\n\nTogether\, these works significantly optimize datacenter memory\nefficiency through a comp rehensive set of architectural and operating\nsystem techniques and lay th e foundation for sustainable memory\nscaling for years to come.\n\nThesis Committee: \n\nDimitrios Skarlatos (Chair)\n\nPhillip Gibbons\n\nTodd Mow ry\n\nKim Keeton (Google)\n\nIn-person and Zoom\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676049557 DTSTART;TZID=America/New_York:20260611T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260611T150000 LOCATION:Gates and Hillman Centers SUMMARY:Doctoral Thesis Oral Defense - Bailey Mark Miller CLASS:PUBLIC DESCRIPTION:Speaker: BAILEY MARK MILLER\, Ph.D. Candidate\, Computer Scienc e\nDepartment\, Carnegie Mellon University\n\nTalk Title: Monte Carlo Meth ods for Linear Elliptic Boundary Value\nProblems\n\nThis thesis develops t he walk on spheres family of Monte Carlo PDE\nsolvers into a practical com putational framework for solving linear\nelliptic boundary value problems. Walk on spheres is effective for the\nsame reason Monte Carlo rendering i s: both recast their governing\nequations—linear elliptic PDEs and light transport—as integral\nequations admitting recursive Monte Carlo estima tors\, and both inherit\nthe geometric scalability and robustness that fol low from sampling\nrather than meshing. Yet where rendering matured over t he past two\ndecades into a ubiquitous\, practical tool\, walk on spheres still lacks\nthe corresponding building blocks: support for first-order li near\nboundary conditions\, generalizations to participating media\, cachi ng\nand reuse schemes for accelerated evaluation\, and differentiable\nvar iants for shape optimization. We take direct inspiration from\nmethods in rendering that provide these capabilities.\n\nWe generalize walk on sphere s to first-order linear boundary\nconditions\, broadening it beyond pure D irichlet problems to the wider\nrange of physically meaningful boundary mo dels\, much as general\nreflectance models did for rendering. We extend th e method to\nparticipating media\, solving linear elliptic boundary value problems\non the same intricate microparticle geometries that volume rende ring\nhandles. We introduce caching and reuse schemes\, in the spirit of\n virtual point lights and irradiance caching\, that produce efficient\nand smooth dense solution estimates. Finally\, we develop differential\nwalk o n spheres\, computing solution derivatives through a nested\nboundary valu e problem that walk on spheres solves recursively\, in\nanalogy to differe ntiable rendering. Together\, these contributions\nelevate walk on spheres from a geometrically capable estimator into a\npractical and extensible f ramework for Monte Carlo PDE simulation\,\nmirroring the developments in M onte Carlo rendering.\n\nThesis Committee:\n\nIoannis Gkioulekas (Chair)\n \nKeenan Crane\n\nNicholas Boffi\n\nRavi Ramamoorthi (University of Califo rnia\, San Diego)\n\nMathieu Desbrun (Inria and École Polytechnique)\n\nI n-person & Zoom\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676049a8f DTSTART;TZID=America/New_York:20260529T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260529T150000 LOCATION:Gates and Hillman Centers SUMMARY:Doctoral Thesis Oral Defense - Alexander Koujianos Goldberg CLASS:PUBLIC DESCRIPTION:Speaker: ALEXANDER KOUJIANOS GOLDBERG\, Ph.D. Candidate\, Compu ter\nScience Department\, Carnegie Mellon University\n\nTalk Title: Improv ing Decision-Making from Distributed Human\nEvaluations\n\nMany consequent ial decisions require decision makers to combine noisy\njudgments from dis tributed human evaluators\, often without access to\nan objective ground t ruth. Scientific peer review and grant funding\nare central examples\, but similar challenges arise in hiring\,\nadmissions\, medical decision-makin g\, online platforms\, and AI\nevaluation. This thesis studies how to unde rstand and mitigate errors\nin distributed human evaluation in order to ma ke better decisions. It\ncombines controlled experiments in real review pr ocesses with\nprincipled algorithms that provide formal guarantees.\n\nThe first part of the thesis uses two large-scale experiments at ML/AI\nconfe rences to study interventions for improving scientific peer\nreview. One e xperiment examines whether meta-evaluation can improve\nreview quality\; t he other studies a live deployment of a\nlarge-language-model assistant fo r paper authors. Together\, they show\nboth the promise and the limits of interventions aimed at improving\nreview processes.\n\nThe second part dev elops algorithms for selection under uncertainty.\nMotivated by the growin g use of lotteries in scientific funding\, we\nformalize the goals behind randomized selection\, show that existing\ndesigns often fail to meet them \, and introduce efficient algorithms\nfor randomized selection with prova ble guarantees.\n\nThe third and final part studies privacy-preserving dat a release for\nevaluation systems. We show how released review\, time-seri es\, and\ngraph data can compromise participant privacy\, and develop mech anisms\nfor sharing useful data while protecting anonymity.\n\nThesis Comm ittee:\n\nGiulia Fanti (Co-Chair)\n\nNihar B. Shah (Co-Chair)\n\nTom Mitch ell\n\nJohn Ioannidis (Stanford University)\n\nIn-person and Zoom\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676049f4d DTSTART;TZID=America/New_York:20260504T090000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260504T110000 LOCATION:Gates and Hillman Centers SUMMARY:Doctoral Thesis Oral Defense - Nicole Feng CLASS:PUBLIC DESCRIPTION:Speaker: NICOLE FENG\, Ph.D. Candidate\, Computer Science Depar tment\,\nCarnegie Mellon University\n\nTalk Title: Algorithms for Generali zed Signed Distance and Winding\nNumbers\n\nIn this talk\, I'll discuss al gorithms for generalized inside/outside\nand signed distance computation. By \"generalized\"\, I mean that these\nalgorithms make geometric inferenc es from imperfect data comprising\nincomplete\, inaccurate\, or ambiguous observations or representations\nof shapes. In other words\, these algorit hms generalize from imperfect\ndata and implicitly approximate the true un derlying curve or surface.\nA theme is that generalization can often be ac hieved by processing\nglobally-defined functions encoding the geometry of interest\, rather\nthan the original\, defective curve or surface. For bot h inside/outside\nand signed distance computation we can unlock further co ntrol over\ngeometry and topology by processing higher-order derivatives o f these\nfunctions. Another theme is that inside/outside and signed distan ce\ncomputation are closely related problems\; towards this end\, I'll\npr ovide a formalization of their relationship that justifies the\ndesign of our algorithms.\n\nThesis Committee: \n\nKeenan Crane (Chair)\n\nNancy Po llard\n\nIoannis Gkioulekas\n\nChris Wojtan (Institute of Science and Tech nology Austria)\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604a35c DTSTART;TZID=America/New_York:20260504T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260504T140000 LOCATION:Newell-Simon Hall SUMMARY:Doctoral Thesis Oral Defense - Arjun Lakshmipathy CLASS:PUBLIC DESCRIPTION:Speaker: ARJUN LAKSHMIPATHY \, Ph.D. Candidate\, Computer Scien ce\nDepartment\, Carnegie Mellon University\n\nTalk Title: Contact Areas f or Dexterous Manipulation and Beyond\n\nHumans use their hands to effortle ssly manipulate objects of\narbitrarily complex geometries and physical pr operties every day\;\nhowever\, adapting these behaviors to dexterous robo ts and virtual\ncharacters is a difficult task. Understanding how humans e xploit\ncontact to perform these manipulations has the potential to greatl y\nadvance progress towards this goal.\n\nUnsurprisingly\, research effort s have analyzed contact in the context\nof dexterous manipulation for deca des. We now have numerous metrics\nfor evaluating grasp quality in terms o f contacts\, sophisticated\nmodels of contact states\, efficient means of computing physically\nsimulated contacts\, and strategies that exploit con tact\ncorrespondences between hands and objects to synthesize grasps and\n manipulations. But the majority of existing works fundamentally\ncharacter ize contact the same way: as points\, lines\, or planes of\ninteraction.\n \nBut contact in the real world is much more complicated. Real bodies\nins tead interface with one another via areas of contact which greatly\nvary w ith the geometries of the contacting surfaces. If we wish to\nmodel the co mplexities of manipulations as they actually occur\, then\nwe must progres s beyond such simplifying assumptions and deal with the\nmessy nature of r eality.\n\nThis thesis aims to do so by presenting foundational frameworks and\nalgorithms for the modeling\, capture\, mutation\, and exploitation of\ncontact areas. Our intention is to establish the foundations necessary \nto elevate contact regions to first-class primitives and demonstrate\nth eir inherent value across a range of practical applications in\ndexterous manipulation and adjacent domains.\n\nFirst\, we introduce three novel con tact area models alongside\noperations supported by each model designed to run on real geometries\nrather than primitive shapes. Next\, using area-b ased primitives\, we\nintroduce: a set of intuitive artist tools for digit ally drafting high\nquality grasps\, a kinematic motion retargeting pipeli ne for dexterous\nmanipulations\, a contact-driven control framework for m ulti-fingered\nhands in physical simulation\, and two practical extensions to\ndifferent domains. We then shift our focus to the real world by\nintr oducing approaches for capturing and reconstructing contact areas\nduring human-object and human-human interactions. Finally\, we present\nan end-to -end system architecture framework for constructing fully\nfunctional robo t systems from contact-rich human demonstrations.\n\nThesis Committee:\n\n Nancy S. Pollard (Chair)\n\nJessica K. Hodgins\n\nKeenan Crane\n\nZackory Erickson\n\nC. Karen Liu (Stanford University)\n\nIn-person and Zoom\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604a8d0 DTSTART;TZID=America/New_York:20260421T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260421T143000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Aditi Nandkishor Kabra CLASS:PUBLIC DESCRIPTION:Speaker: ADITI NANDKISHOR KABRA\, Ph.D. Candidate\nComputer Sci ence Department\nCarnegie Mellon University\n\nTalk Title: Verified Contro l Envelope Synthesis\n\nMany cyber-physical systems\, such as trains\, pla nes\, and self-driving\ncars\, are safety-critical but difficult to reason about. The task of\ndesigning controllers for such systems is complex (th e subject of an\nentire field\, control theory)\, made even more challengi ng by the need\nto ensure correctness over all of the infinitely many poss ible\nscenarios that the system may face. This thesis develops techniques\ nthat let computers automatically synthesize the conditions that define\nc orrect control solutions\, with mathematical guarantees that these\ncondit ions are correct.\n\nSymbolic control envelopes are our representation of the control\nconditions that characterize sets of safe control solutions. They are\nrepresented parametrically in symbols that can be instantiated w ith\nany real-valued input (e.g.\, for a train control envelope\, train\nw eight w). Control envelopes provide a path to designing complex\ncontrolle rs that still have mathematical correctness guarantees by\nallowing separa tion of concerns during controller design. A verified\n(i.e.\, mathematica lly correct) safe control envelope can first\nidentify the set of control solutions that ensure the safety-critical\ncontrol objectives\, and then n on-formal techniques\, e.g.\, machine\nlearning\, can optimize within that envelope for secondary objectives.\n\nThe thesis automates the process of designing symbolic control\nenvelopes by creating the first framework for symbolic control\nenvelope synthesis. The framework takes as input the sh ape of a\ncontrol system\, which indicates what control and environment be haviors\nare physically possible and what the desired control behavior is\ ,\nmaking the synthesis question well-defined. The framework\nautomaticall y identifies the symbolic control conditions indicating\nwhen a given cont rol action is correct\, which is shown to correspond\nto the nondeterminis tic control policies of players in hybrid games\n(games with both continuo us and discrete dynamics).\n\nThis thesis tackles the hybrid game control envelope synthesis problem\nin its full generality\, developing the theory to solve for all of\ndifferential game logic. It introduces a specialized procedure for an\ninteresting subset of problems (time-triggered\, where the controller\nloops with some maximum time latency) that is total comput able under\nsome reasonable assumptions. By strategically using large lang uage\nmodels along with verification\, it provides a general approach to\n sound\, scalable synthesis.\n\nThesis Committee\n\nAndré Platzer (Co-Chai r)\n\nStefan Mitsch (Co-Chair)\n\nEunsuk Kang\n\nArmando Solar-Lezama (Mas sachusetts Institute of Technology)\n\nIn Person and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604ade6 DTSTART;TZID=America/New_York:20260420T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260420T123000 LOCATION:Newell-Simon 1505 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Jonathan Laurent CLASS:PUBLIC DESCRIPTION:Speaker: JONATHAN LAURENT\, Ph.D. Candidate\nComputer Science D epartment\nCarnegie Mellon University\n\nTalk Title: Oracular Programming: A Modular Foundation for Building\nLLM-Enabled Software\n\nLarge Language Models (LLMs) can solve previously intractable tasks\ngiven only natural- language instructions and a few examples\, but they\nremain difficult to s teer and lack a key capability for building\nreliable software at scale: t he modular composition of computations\nunder enforceable contracts. As a result\, they are often embedded in\nlarger software pipelines that use do main knowledge to decompose tasks\nand improve reliability through validat ion and search. Yet the\ncomplexity of writing and maintaining such pipeli nes has so far\nlimited their sophistication.\n\nWe propose oracular prog ramming: a foundational paradigm for\nintegrating traditional\, explicit c omputations with inductive oracles\nsuch as LLMs. It rests on two directin g principles: the full\nseparation of core and search logic (allowing the latter to freely\nevolve without breaking the former)\, and the treatm ent of few-shot\nexamples as grounded and evolvable program components (allowing\ntheir consistency with the rest of the program to be enforced through\nits evolution\, with breakages easily identifiable and repairable ).\nWithin this paradigm\, programmers express high-level problem-solving\ nstrategies as programs with unresolved choice points. These choice\npoint s are resolved at runtime by LLMs\, which generalize from\nuser-provided e xamples of correct and incorrect decisions.\nAn oracular program is comp osed of three orthogonal components:\na strategy that consists of a nond eterministic program with choice\npoints that can be reified into a search tree\, a policy that\nspecifies how to navigate this tree with the help of LLM oracles\, and\na set of demonstrations that describe successful and unsuccessful\ntree navigation scenarios across diverse problem instanc es. Each\ncomponent is expressed in a dedicated language.\n\nWe address th e key programming language design challenges of modularly\ncomposing oracu lar programs and enforcing consistency between their\ncomponents as they e volve. We also demonstrate universal\nself-improvement mechanisms for orac ular programs\, in which training\nand tuning data is automatically extrac ted from successful and\nunsuccessful runs. Finally\, we present Delphyne \, an open-source\nframework for oracular programming based on Python\, an d empirically\nevaluate our approach through several case studies.\n\nThes is Committee\n\nAndré Platzer (Chair)\n\nMarijn Heule\n\nZico Kolter\n\nA rmando Solar-Lezama (Massachusetts Institute of Technology\n\nIn Person an d Zoom Participation.  See announcement. \n\n \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604b374 DTSTART;TZID=America/New_York:20260415T090000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260415T103000 LOCATION:Rescheduled SUMMARY:Doctoral Thesis Oral Defense - Nicole Feng - Talk Rescheduled CLASS:PUBLIC DESCRIPTION:Speaker: NICOLE FENG\, Ph.D. CandidateComputer Science\nDepartm entCarnegie Mellon University\n\nTalk Title: Algorithms for Generalized Si gned Distance and Winding\nNumbers\n\nIn this talk\, I'll discuss algorith ms for generalized inside/outside\ncomputation (via winding numbers) and signed distance computation. By\n\"generalized\"\, I mean that these algor ithms make geometric inferences\nfrom imperfect data comprising incomplete \, inaccurate\, or ambiguous\nobservations or representations of shapes. I n other words\, these\nalgorithms generalize from imperfect data and impli citly approximate\nthe true underlying curve or surface. A theme is that g eneralization\ncan often be achieved by processing globally-defined functi ons\nencoding the geometry of interest\, rather than the original\, defect ive\ncurve or surface. For both inside/outside and signed distance\ncomput ation we can unlock further control over geometry and topology\nby process ing higher-order derivatives of these functions. Another\ntheme is that in side/outside and signed distance computation are\nclosely related problems \; towards this end\, we provide a formalization\nof their relationship th at justifies the design of our algorithms.\n\nThesis Committee\n\nKeenan C rane (Chair)\n\nNancy Pollard\n\nIoannis Gkioulekas\n\nChris Wojtan (Insti tute of Science and Technology Austria)\n\nIn Person and Zoom Participatio n.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604b802 DTSTART;TZID=America/New_York:20260407T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260407T113000 LOCATION:ASA Conference Room\, Gates Hillman 6115 SUMMARY:Doctoral Thesis Oral Defense - Catalina Vajiac CLASS:PUBLIC DESCRIPTION:Speaker: CATALINA VAJIAC\, Ph.D. Candidate\nComputer Science De partment\nCarnegie Mellon University\n\nTalk Title: Detection and Visualiz ation of Human Sex Trafficking in\nOnline Escort Advertisements\n\nHuman t rafficking (HT) for forced sexual exploitation is incredibly\npervasive\, affecting an estimated 6.3 million people at any given\ntime. The majority of victims are advertised online\, mainly through\nonline escort websites \, alongside at-will escorts. Practitioners\nwho want to help these victi ms\, including government organizations\,\ncriminologists\, social workers \, and investigators\, often manually\nscroll through these escort website s to try to find HT leads by\nlooking for known keywords\, geographic move ment\, or other known HT\nsignals indicating a person was advertised again st their will. This\nmanual process is inefficient\, as it requires lots o f time\, and\nineffective\, as traffickers change their patterns and keywo rds over\ntime to avoid detection. In addition\, since the majority of HT cases\nare part of organized crime groups\, practitioners realized a more\ nreliable HT indicator: groups of ads with nearly-identical text that\nadv ertise multiple people\, signaling larger organized activity than\nindivid ual escorts would post. These insights can be leveraged to help\nfacilitat e lead generation for practitioners\, enabling them to act\nmore quickly t o get HT victims out of exploitation.\n\nIn this thesis\, we assist practi tioners in identifying potential HT\ncases by: (1) developing scalable and explainable clustering\nalgorithms based on text for finding and summari zing organized crime\ngroups in escort ad data\, and (2) creating intuitiv e visualization\nmethods for presenting the results of these to practition ers. These\nvisualizations not only help practitioners to better understan d\npotential leads\, but they also facilitate label generation so\ndownstr eam algorithm evaluation can continue even as traffickers\nchange their pa tterns. In addition\, the methods outlined in this\nthesis have real-world impact\; they are currently being integrated by\nindustry practitioners.\ n\nThesis Committee\n\nChristos Faloutsos (Chair)\n\nRayid Ghani\n\nAdam P erer\n\nDuen-Horng Chau (Georgia Institute of Technology) \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604bd46 DTSTART;TZID=America/New_York:20260316T093000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260316T110000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense CLASS:PUBLIC DESCRIPTION:Speaker: MINGKUAN XU\, Ph.D. Candidate\nComputer Science Depart ment\nCarnegie Mellon University\n\nTalk Title: Optimization and Simulatio n of Quantum Circuits\n\nOptimizing and simulating quantum circuits at sca le are critical\nbottlenecks in quantum computing. This thesis delivers a suite of\ntools to improve them.\n\nFor quantum circuit optimization\, we first automate the discovery and\nverification of transformation rules by introducing Equivalence\nCircuit Class (ECC) sets and an efficient generat ion algorithm for\narbitrary gate sets. We then utilize the generated rule s in the\nsuperoptimizer Quartz\, which optimizes circuits using a cost-ba sed\nbacktracking search. Compared to previous rule-based methods\, Quartz \nsuccessfully escapes local minima through exhaustive search. To\nfurther improve efficiency and avoid the exponential runtime penalties\nof pure s earch\, we introduce QALM. This hybrid optimizer combines\nexhaustive sear ch with rule-based rewriting. By interleaving bounded\nsearch-based explor ation with greedy rule-based exploitation\, QALM\nescapes local minima dyn amically. It outperforms existing search-based\noptimizers in optimization quality and matches reinforcement learning\nmethods without the training overhead.\n\nWhile the prior two approaches aim for global optimization\, this\nproblem is intrinsically QMA-hard\, creating a bottleneck for large\ nprograms. To circumvent this issue and scale up\, we introduce OAC\, a\nc ut-and-meld circuit optimization algorithm. OAC cuts a circuit into\nsubci rcuits\, applies an existing oracle optimizer independently\, and\nseamles sly melds the results. This approach operates with a linear\nnumber of ora cle calls while attaining local optimality. Empirical\nevaluation shows th at OAC improves the efficiency of state-of-the-art\noptimizers by over an order of magnitude while enhancing overall\nquality.\n\nBeyond physical ex ecution\, the scalable simulation of quantum circuits\non classical hardwa re presents another major challenge. We present\nAtlas\, a distributed GPU -based simulator that hierarchically\npartitions circuits to exploit data parallelism while minimizing\ncommunication. By using integer linear progr amming to allocate\nstructurally related gates to nearby GPUs and dynamic programming for\nkernel scheduling\, Atlas runs over 2x faster than prior\ nstate-of-the-art GPU simulators.\n\nTogether\, these frameworks provide a robust toolchain\, improving both\nthe execution of quantum circuits on p hysical devices and their\nscalable classical simulation. \n\nThesis Comm ittee\n\nZhihao Jia (Co-Chair)\n\nUmut A. Acar (Co-Chair)\n\nRyan O'Donne ll\n\nYongshan Ding (Yale University)\n\nIn Person and Zoom Participation.   See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604c30f DTSTART;TZID=America/New_York:20260217T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260217T133000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral - Jiaming (Andy) Zou CLASS:PUBLIC DESCRIPTION:Speaker: JIAMING (ANDY) ZOU\, Ph.D. CandidateComputer Science\n DepartmentCarnegie Mellon University\n\nTalk Title: Improving Safety and S ecurity of Generative Models\n\nRecent advances in large language and mult imodal models have enabled\npowerful new applications\, but they also rais e critical challenges in\nsafety\, robustness\, and alignment. This thesis studies these\nchallenges through three complementary research directions . First\, we\nshow that current alignment methods remain brittle by develo ping\nadversarial attacks that reliably bypass safeguards across text\,\nm ultimodal\, and embodied systems\, demonstrating that alignment alone\ndoe s not guarantee robustness. Second\, we introduce evaluation\nframeworks a nd benchmarks that systematically measure safety failures\nin modern AI sy stems\, revealing widespread vulnerabilities in deployed\nmodels and agent s. Third\, we propose methods to improve alignment and\ncontrol\, includin g representation-level interventions\, circuit\nbreakers\, and safety pret raining\, which significantly reduce attack\nsuccess while preserving mode l capability. Together\, these\ncontributions advance our understanding of AI safety risks and provide\npractical tools for building safer and more trustworthy AI systems.\n\nThesis Committee\n\nZico Kolter (Co-chair)\n\nM att Fredrikson (Co-chair)\n\nGraham Neubig\n\nNicholas Carlini (Anthropic) \n\nIn Person and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604c738 DTSTART;TZID=America/New_York:20260130T123000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260130T140000 LOCATION:Newell-Simon 3002 SUMMARY:Doctoral Thesis Oral Defense - Caspar Oesterheld CLASS:PUBLIC DESCRIPTION:Speaker: CASPAR OESTERHELD\, Ph.D. Candidate\nComputer Science Department\nCarnegie Mellon University\n\nTalk Title: New foundational ide as in cooperative AI\n\nMy doctoral research addresses two fundamental obs tacles to beneficial\noutcomes from strategic interactions between multipl e parties:\nstrategic incentives against cooperation (as in the Prisoner's \nDilemma) and the multiplicity of strategic solutions (sometimes called\n the equilibrium selection problem). As AI systems are increasingly\ninvolv ed in consequential decision making processes on behalf of human\nprincipa ls\, understanding how to achieve desirable outcomes in\nmulti-agent AI se ttings becomes critical. My research leverages unique\nfeatures of AI syst ems -- including their transparency\,\nreproducibility\, and malleability -- to develop novel game-theoretic\napproaches that enable better\, more c ooperative outcomes.\n\n    \n\nThree primary research directions form the core of this dissertation.\nFirst\, the concept of safe (Pareto) impro vements provides a rigorous\nframework for improving outcomes without reso lving equilibrium\nselection problems. Unlike traditional solution concept s\, safe Pareto\nimprovements make qualitative assumptions about pairs of games rather\nthan individual games. This sometimes allows us to prefer pl aying one\ngame over another\, without any judgment about how each of the\ nindividual games is played. Second\, my research on so-called\nNewcomb-li ke decision problems takes inspiration from philosophical\nbranches of dec ision theory concerning\, for example\, how one should\nreason when intera cting with a copy of oneself. I investigate how\ncooperation can be achiev ed when different parties deploy similar AI\nsystems. Third\, the concept of program equilibrium explores how the\nuse of mutually transparent decis ion-making algorithms can allow for\ncooperation.\n\nThesis Committee\n\nV incent Conitzer (Chair)\n\nTuomas Sandholm\n\nFei Fang\n\nStuart Russell ( University of California\, Berkeley)\n\nBen Levinstein (University of Illi nois Urbana-Champaign / Anthropic) \n\n \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604cc1a DTSTART;TZID=America/New_York:20260123T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20260123T150000 LOCATION:Newell-Simon Hall SUMMARY:Doctoral Thesis Oral Defense - William Zhang CLASS:PUBLIC DESCRIPTION:Speaker: WILLIAM ZHANG\, Ph.D. Candidate\, Computer Science Dep artment\,\nCarnegie Mellon University\n\nTalk Title: On Holistic Database Optimization via Leveraging\nSimilarity Across Actions\, Workloads\, Confi gurations\, and Scenarios\n\nModern database management systems (DBMSs) ha ve evolved to support\nincreasingly sophisticated data-intensive applicati ons\, at the cost of\nsubstantial complexity to configure them for two rea sons. First\, DBMSs\nexpose a vast configuration space with trillions of p ossibilities that\nencompass system knobs\, physical design (e.g.\, indexe s)\, and query\noptions\, amongst others. Second\, these applications are constantly\nevolving with changes in data access patterns\, query types\, load\nintensities\, hardware\, and data distributions that necessitate\nco ntinuous re-optimization.\n\nTo address these challenges\, decades of auto nomous DBMS optimization\nresearch have produced specialized tuning tools to assist human\noperators. Deploying these tools involves a complex multi -step\nworkflow where an operator (1) observes the DBMS’s behavior\, (2) \nselects tools based on the objectives and their expertise\, (3)\nconfigu res them with an isolated environment\, (4) orchestrates their\nexecution to obtain recommendations\, and (5) reviews those\nrecommendations before deployment. This cumbersome process results in\nsuboptimal configurations and slow adaptation to evolving\napplications’ workloads due to isolated specialized tools\,\ninefficient reuse of prior tuning knowledge\, and th e fallible human\nfactor.\n\nIn this dissertation\, we present techniques for addressing those\nlimitations with similarity to enable holistic datab ase optimization.\nFirst\, we present a holistic tuning tool that optimize s multiple DBMS\naspects simultaneously by using action similarity to orga nize actions\ninto neighborhoods conducive to exploration. We then present a\nframework that assists tuners in adapting to environment changes by\nl everaging workload and configuration similarity to re-mix historical\nknow ledge. Lastly\, we present a system that transforms the\nhuman-centric tun ing workflow into an agentic process by using\nscenario similarity to link the deployment context with semantic tool\ninterfaces to optimize the dep loyment.\n\nThe techniques and associated similarity definitions presented in this\ndissertation enable agentic holistic DBMS optimization over a\nd eployment’s lifetime\, improving the deployment’s performance and\nred ucing time taken to adapt to changes in upstream user applications.\n\nThe sis Committee:\n\nAndrew Pavlo (Chair)\n\nJignesh Patel\n\nVincent Conitze r\n\nImmanuel Trummer (Cornell)\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604d13e DTSTART;TZID=America/New_York:20251222T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251222T113000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 SUMMARY:Doctoral Thesis Oral Defense - Nuno Sabino CLASS:PUBLIC DESCRIPTION:Speaker: NUNO SABINO\, Ph.D. Candidate\nComputer Science Depart ment\nCarnegie Mellon University\n\nTalk Title: Improving Code-Injection V ulnerability Detection and\nConfirmation in JS Programs\n\nJavaScript appl ications face serious security risks\, including\nclient-side DOM-based Cr oss-Site Scripting (DOM-XSS) and server-side\narbitrary command injection (ACI) and arbitrary code execution (ACE).\nExploiting these vulnerabilitie s can lead to severe consequences\,\nincluding unauthorized access to sens itive data and even full server\ncompromise.\n\nDynamic taint analysis (DT A) tools have been used to identify how\nattacker-controlled input\, such as a URL\, may reach sensitive\nfunctions that lead to arbitrary code exec ution. Such propagations of\nattacker information\, termed potential flows \,can be good indicators of\nvulnerabilities. However\, existing approache s struggle to (1) generate\nconcrete inputs that exercise these flows due to limited path\nexploration\, and (2) automatically confirm vulnerabiliti es\, because\ninputs must satisfy program constraints while also triggerin g the\nintended side effects. This thesis leverages program analysis\ntech niques to address these challenges\, with tailored approaches for\nthe dis tinct requirements of server and client code.\n\nClient-side analysis is c omplicated by program behaviors dependent on\nuser interactions and URL GE T parameters. To overcome this\, we\ndeveloped a fuzzer to interact with t he target web page and we employ\ndynamic symbolic execution (DSE) to synt hesize GET parameters\nsatisfying program constraints. Relative to our rep lication of prior\nwork DOMsday\, the fuzzer alone identifies 15% more vul nerabilities in\na dataset of 44\,480 popular pages\, and the combination of fuzzing and\nDSE iden tifies 43% more vulnerabilities than DOMsday.\n\n On the server-side\, DTA-based tools miss ACI and ACE that require\ninputs with complex structure. We develop a novel type- and\nstructure-aware fuz zing technique to explore Node.js packages\, and an\nenumerator to synthes ize syntactically valid payloads for ACE\nvulnerabilities. Extending NodeM edic with these components led to\nfinding 1.7x more vulnerabilities. Fina lly\, we find that\nnon-exploitable potential flows can still indicate rea l\nvulnerabilities\, but exploitation may imply extra steps\, such as\nbyp assing sanitization or extending attacker capabilities. We\nintroduce an e xploitability metric designed to indicate proximity to\nan exploitable pat h\, and use it to guide fuzzing and confirmation\ntowards paths that are m ore likely automatically exploitable.\nIntegrating this in NodeMedic-FINE results in 1% more confirmed flows\,\nwhile saving 28% of the baseline con firmation time.\n\nThesis Committee\n\nLimin Jia (Chair)\n\nLujo Bauer\n\n Ruben Martins\n\nPedro Adão (Advisor\, Instituto Superior Técnico)\n\nRu i Maranhão (Advisor\, Faculdade de Engenharia da Universidade do\nPorto)\ n\nJosé Fragoso (Instituto Superior Técnico)\n\nCristian-Alexandru Staic u (CISPA Helmholtz Center for Information\nSecurity) \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604d656 DTSTART;TZID=America/New_York:20251215T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251215T143000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Wan Shen Lim CLASS:PUBLIC DESCRIPTION:Speaker: WAN SHEN LIM\, Ph.D. Candidate\, Computer Science Depa rtment\,\nCarnegie Mellon University\n\nTalk Title: Database Gyms: Towards Autonomous Database Tuning\n\nDatabase management systems (DBMSs) are the foundation of modern\ndata-intensive applications. But as more features a re developed to\nsupport new workloads\, they become increasingly complex and difficult\nto configure. Thus\, researchers have invested decades of e ffort into\nautonomous DBMS configuration. Recent advances in machine lear ning\n(ML) have produced tools that outperform unassisted experts in\nreal -world deployments. However\, these tools are advisory and require\nhuman expertise for deployment into database tuning pipelines.\n\nUsing these to ols involves a multi-step process where a human operator\n(1) determines a n optimization objective\, (2) selects a suitable tool\,\n(3) sets up the DBMS\, (4) runs a workload to collect telemetry\, (5)\nuses the telemetry to calibrate the tool\, and (6) operates the tool to\nobtain recommendatio ns\, which the operator must then review and apply.\nThese ad-hoc pipeline s require significant human effort to set up\,\nextend\, and deploy. Moreo ver\, interface differences make tools\ndifficult to compose and interchan ge. Thus\, despite the demonstrated\nability of database tuning tools to i mprove performance and lower\ncosts\, the expertise required to operate th em limits their adoption.\n\nThis dissertation presents the database gym\, an integrated framework\nthat systematizes and automates the DBMS configu ration pipeline.\nUnlike prior research that focused on improving tool eff ectiveness\nwith ML\, the gym targets deployment and operational challenge s by\nproviding reusable\, interoperable\, and interchangeable components that\nsimplify tool development and integration.\n\nThe gym’s design ref lects the observation that the bottleneck in\ndatabase tuning has shifted from developing better algorithms for\ntools to acquiring the training dat a needed to operate them. We\ndemonstrate how the gym's architecture accel erates and adapts\ntool-based database tuning pipelines through the system atic generation\nand utilization of training data\, enabling the augmentat ion and\norchestration of tools with end-to-end knowledge. For example\, i t\nreduces step-level overhead by skipping redundant computation during\nt elemetry generation\, thus reducing the tuning pipeline's latency. It\nals o eliminates pipeline-level repetition by reusing training data to\nadapt a tool's calibrated models across new software versions and\nhardware envi ronments. Such optimizations are enabled by the gym’s\nholistic control over the entire tuning process.\n\nThesis Committee\n\nAndrew Pavlo (Chair )\n\nJignesh Patel\n\nDavid Andersen\n\nLin Ma (University of Michigan)\n\ nIn Person and Zoom Participation. See announcement. \n\n \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604dbb2 DTSTART;TZID=America/New_York:20251205T123000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251205T140000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Honghao Lin CLASS:PUBLIC DESCRIPTION:Speaker: HONGHAO LIN\, Ph.D. Candidate\nComputer Science Depart ment\nCarnegie Mellon University\n\nTalk Title: Algorithms for Massive Dat a: Optimal Bounds\, Adversarial\nRobustness\, and Data-Driven Insights\n\n With the rapid growth of massive datasets in areas such as machine\nlearni ng and numerical linear algebra\, classical algorithms are often\nno longe r feasible. In this thesis\, we develop provably efficient\nalgorithms for various problems in these settings\, such as the\nstreaming and distribut ed model. Our contributions span three\ndirections:\n\nOptimal Bounds.  W e introduce a general technique for lifting\ndimension lower bounds for re al-valued linear sketches to polynomially\nbounded integer inputs. This le ads to the first optimal sketching\nlower bounds for discrete data streams in fundamental problems such as\nfrequency moment approximation\, operato r norm estimation\, and\ncompressed sensing. Beyond this\, we also establi sh nearly-optimal\nbounds for a variety of streaming and sketching tasks\, including\nℓ p subspace sketches for constant dimension d\, ℓ p re gression\nin the arbitrary-partition distributed model\, and graph problem s such\nas approximating the minimum cut and constructing cut sparsifiers in\nbalanced directed graphs.Adversarial Robustness.  While most\nstreami ng algorithms are studied in static worst-case models\, many\npractical sc enarios involve adaptive adversaries who generate inputs\nbased on previou s outputs. We present the first adaptive attack\nagainst linear sketches f or ℓ p-estimation over turnstile integer\nstreams. Specifically\, we sh ow that any linear streaming algorithm\nwith sketching matrix A ∈ ℤrxn can be broken using only poly(r log\nn) queries\, with high constant prob ability. This result highlights\nfundamental limits of robustness in adapt ive streaming. Furthermore\,\nwe will next introduce our recent work on an adversarially robust F2\nestimation algorithm\, based on a non-linear ske tch\, that achieves\npolylogarithmic space in turnstile streams.Learning-b ased\nAlgorithms.  Classical algorithms guarantee correctness in the wors t\ncase but often ignore structure in real-world data\, while machine\nlea rning methods leverage structure but typically lack guarantees. We\ndesign learning-based algorithms that incorporate machine learning\npredictions to adapt to input distributions\, achieving faster\nruntimes\, reduced spa ce\, or improved accuracy. Crucially\, these\nalgorithms retain rigorous w orst-case guarantees even when the\npredictions are imperfect\, bridging t he gap between theory and\ndata-driven practice.  \n\nThesis Committee\n \nDavid P. Woodruff (Chair)\n\nYang P. Liu\n\nRichard Peng\n\nJelani Nelso n (University of California\, Berkeley)\n\nIn Person and Zoom Participatio n.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604e1e5 DTSTART;TZID=America/New_York:20251120T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251120T130000 LOCATION:ASA Conference Room\, Gates HIllman 6115 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Joseph Reeves CLASS:PUBLIC DESCRIPTION:Speaker: JOSEPH REEVES\, Ph.D. Candidate\nComputer Science Depa rtment\nCarnegie Mellon University\n\nTalk Title: Cardinality Constraints in Boolean Satisfiability Solving\n\nAutomated reasoning is a branch of ar tificial intelligence that uses\nsearch engines called solvers to find sol utions for problems\nformulated in mathematics and logic. Automated reason ing has been\napplied across a wide range of domains from hardware and sof tware\nverification to mathematical discovery. To solve a diverse set of\n problems\, these tools make use of low-level reasoning\, namely the\nconfl ict-driven clause learning algorithm\, which is made possible by\nfirst en coding a problem into low-level logic.\n\nEncoding is pivotal to the succe ss of a solver. High-level constraints\nare transformed into low-level log ic via abstractions\, and using a\nsuboptimal set of abstractions might in crease a solver’s runtime by\nfactors of a hundred. In this thesis\, we focus on one type of\nhigh-level constraint: cardinality constraints. Card inality\nconstraints appear in any problem that requires counting\, for ex ample\,\n\"synthesize a quantum circuit with at most k swap gates\"\, or  \"each\nvalue from 1 to 9 may appear at most once in every row of a Sudok u\npuzzle\". It is standard practice to make users encode these\nconstrain ts before passing them as input to an off-the-shelf solver.\n\nWe propose an extended input format that includes cardinality\nconstraints. This allo ws us to move questions of encoding out of the\nhands of the user and into the domain of the solver. We present\nseveral techniques that leverage th e structural information provided\nby this new input format to automatical ly generate more effective\ncardinality constraint encodings.  Furthermor e\, we developed a new\nsolver that employs cardinality-specific reasoning to quickly find\nsolutions for problems from hardware synthesis and discr ete\nmathematics\n\nThesis Committee\n\nRandal Bryant (Co-chair)\n\nMarijn Heule (Co-chair)\n\nRuben Martins\n\nArmin Biere (University of Freiburg) \n\nIn Person and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604e6ba DTSTART;TZID=America/New_York:20251120T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251120T153000 LOCATION:ASA Conference Room\, Gates Hillman 6115 SUMMARY:Doctoral Thesis Oral Defense - Emre Yolcu CLASS:PUBLIC DESCRIPTION:Speaker: EMRE YOLCU\, Ph.D. Candidate\nComputer Science Departm ent\nCarnegie Mellon University\n\nTalk Title: Proof Complexity of Resolut ion-Based Systems: Lower\nBounds\, Simulations\, and Applications to SAT S olving\n\nThe satisfiability problem for propositional logic (SAT) has bee n a\ncentral topic in computer science for many decades. It is arguably th e\ncanonical NP-complete problem: reductions from many other problems in\n NP to SAT are often straightforward. As a consequence\, a reasonable\nstra tegy when trying to solve a problem in NP is to reduce it to SAT\nand to t ry to solve the resulting SAT problem instead. This strategy\nturns out to be surprisingly effective thanks to the effectiveness of\nimplementations of heuristic algorithms for SAT\, commonly known as SAT\nsolvers. Those s olvers are expected to output proofs to certify their\nanswers\, and in th is sense they are proof search algorithms. Proof\ncomplexity\, the branch of computational complexity that studies the\nlengths of proofs in proposi tional proof systems\, offers a way to\nanalyze the performance of SAT sol vers.\n\nThis thesis explores the interplay between SAT solving and proof\ ncomplexity. On the theoretical side\, we investigate the power of weak\,\ nresolution-based proof systems that incorporate restricted forms of\nthe extension rule often used in SAT solvers. We provide a complete\ncharacter ization of their relative strengths. In particular\, we\npresent a general recipe for constructing formulas that yield\nexponential separation resul ts\, showing that none of these systems\nsubsumes another in expressivity. We also establish new exponential\nlower bounds for some of those systems \, pinpointing the inherent\nlimitations of various clause addition rules. The key insights for\nthose separations come from the notion of an effect ive simulation. We\nleverage these insights to better understand the compl exity of proof\nsearch: for example\, we show that even a seemingly weaker system like\nregular resolution can effectively simulate general resoluti on\, which\nhas the corollary that significantly faster algorithms for fin ding\nregular resolution proofs would also speed up general resolution pro of\nsearch.\n\nOn the practical side\, we demonstrate how advances in SAT solving can\naid in mathematical discovery. We develop an automated approa ch to the\nCollatz conjecture\, a notorious open problem in number theory\ , by\nencoding it as a search for a termination proof in a rewriting syste m.\nWe show how the Collatz function can be expressed as a string\nrewriti ng system that terminates if and only if the conjecture holds\,\nand we us e state-of-the-art automated reasoning tools to verify\npartial results.  \n\nThesis Committee\n\nMarijn Heule (Chair)\n\nJeremy Avigad\n\nRyan O'Do nnell\n\nSam Buss (University of California San Diego) \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604ec4b DTSTART;TZID=America/New_York:20251118T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251118T133000 LOCATION:ASA Conference Room\, Gates Hillman 6115 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Benjamin Stoler CLASS:PUBLIC DESCRIPTION:Speaker: BENJAMIN STOLER\, Ph.D. Candidate\, Computer Science\n Department\, Carnegie Mellon University\n\nTalk Title: Towards Robust Auto nomous Driving and Social Robot\nNavigation via Enhanced Data Utilization\ n\nAutonomous robots—including self-driving vehicles\, sidewalk delivery \nrobots\, and more—must navigate among humans in a safe and\nsocially-c ompliant manner. Current approaches for building and\nevaluating such auto nomous systems rely on data-driven techniques\;\nhowever\, a generalizatio n gap emerges\, as methods trained in these\ntraditional paradigms are una ble to cope with unexpected real-world\nscenarios. Therefore\, this thesis aims to develop improved\nmethodologies and evaluation settings to increa se and assess\nrobustness in autonomous navigation against these challenge s\, along\ntwo key pillars of enhanced data utilization.\n\nFirst\, we int roduce scenario characterization and repartitioning\nschemes\, for robustn ess against out-of-distribution safety-relevant\nand corner case scenarios . We create a hierarchical characterization\nmethod which leverages counte rfactual probes to find hidden\nsafety-relevant scenarios in large dataset s. We then address the\ninduced generalization gap by incorporating the ch aracterizations into\ndownstream trajectory prediction models' inductive b iases. To promote\ngreater interpretability and generalizability\, we fact orize scenarios\ninto disentangled contexts\, creating compositionally nov el test sets.\nWe then use modular architectures and auxiliary signals to implicitly\nreason over and adapt to these settings.\n\nSecond\, we design targeted scenario modification approaches\, to expose\nand address failur e cases and weaknesses of naive autonomy methods.\nFor robustness against perception errors affecting downstream motion\nprediction\, we construct a framework for converting top-down\npedestrian trajectory datasets into a more challenging first-person\nview perspective. We then develop a correct ion module to account for\nthe resulting errors\, trained end-to-end with trajectory prediction\napproaches. For robustness against adversarial\, sa fety-critical\nscenarios\, we develop a reactive\, skill-based adversary p olicy which\nleverages a learned\, multi-faceted criticality objective to perturb\nexisting scenarios. We then train ego policies in a closed-loop m anner\nagainst these generated scenarios\, demonstrating improved downstre am\nego performance. Finally\, we process and annotate unlabeled and\nunde rutilized data sources\, to learn human-like behavior from\nreal-world cra sh videos. We use these learned behavior models to\nfurther increase the r ealism of adversarially perturbed scenarios\, as\nwell as the efficacy of closed-loop ego training.\n\nThesis Committee\n\nJean Oh (Chair)\n\nSebast ian Scherer\n\nReid Simmons\n\nJonathan Francis (Bosch Center for Artifici al Intelligence)\n\nIn Person and Zoom Participation.  See announcement.  \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604f1af DTSTART;TZID=America/New_York:20251111T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251111T120000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 SUMMARY:Doctoral Thesis Proposal - Andy Zou CLASS:PUBLIC DESCRIPTION:Speaker: ANDY ZOU\, Ph.D. Student\, Computer Science Department \,\nCarnegie Mellon University\n\nTalk Title: Improving Security and Safet y of Generative Models\n\nGenerative models now mediate information access \, software\ndevelopment\, and mission critical workflows\, yet their secu rity and\nsafety properties lag their rapid deployment. This thesis develo ps a\ncomprehensive approach to improving the safety of aligned language a nd\nagentic systems. \n\nFirst\, we show that alignment fine tuning leave s structural\nvulnerabilities: the Greedy Coordinate Gradient attack learn s\nuniversal and transferable suffixes that trigger harmful behaviors\nacr oss open source models\, achieving high transfer rates to\nproprietary mod els and revealing shared non-robust features in model\nrepresentations. Se cond\, we advance security measurements that span\nstandardized and live e valuation. HarmBench establishes reproducible\nstatic robustness benchmark s\, while the Gray Swan Arena and the\nresulting Agent Red Teaming benchma rk capture human\, adaptive\nadversaries whose discoveries continually ref resh static tests.\nTogether they demonstrate the fragility of current age nts and provide\na continuous feed of vulnerabilities. Third\, we introduc e\nRepresentation Engineering (RepE)\, a new class of approaches that\npro be and control population-level representations encoding\nsafety-relevant concepts. \n\nWe apply RepE methods to safety-critical concepts such as h onesty and\nharmfulness. In particular\, we present Circuit Breaking\, an alignment\nalgorithm which suppresses harmful thought processes in the\nre presentation space to combat adversarial misuse. Looking forward\, we\nwil l continue scaling the capabilities of automated red teaming agents\nand d evelop environments that allow for co-evolution of attacker and\ndefense a gents. For mitigation at the model representation level\, we\nplan to exte nd RepE monitoring to contextual policy violations. We\nbelieve that treat ing safety as a property of training\, evaluation\,\nand internal computat ion yields principled mechanisms for securing\ngenerative systems.\n\nThes is Committee\n\nMatt Fredrikson (Co-Chair)\n\nZico Kolter (Co-Chair)\n\nGr aham Neubig\n\nNicholas Carlini (Anthropic)\n\nAdditional Information \n\ n \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604f69d DTSTART;TZID=America/New_York:20251105T133000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251105T150000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Anup Agarwal CLASS:PUBLIC DESCRIPTION:Speaker: ANUP AGARWAL\, Ph.D. Candidate\nComputer Science Depar tment\nCarnegie Mellon University\n\nTalk Title: Designing Network Control Algorithms with Performance\nGuarantees\n\nControl algorithms are ubiquit ous in networked systems—from\ncongestion control and load balancing to scheduling and caching.\nDespite their performance-critical nature\, these algorithms are\ndesigned using human intuition and heuristics\, and they frequently\nexhibit poor or unpredictable performance. This thesis envisio ns a\nmethodology for designing controllers with formally verified\nperfo rmance guarantees. We focus on congestion control algorithms\n(CCAs)—a d omain that continues to experience repeated failures\ndespite decades of r esearch.\n\nTwo main reasons make congestion control hard. First\, CCAs op erate in\ndiverse and noisy environments (e.g.\, cellular links\, policers \,\ntoken-bucket filters\, operating system jitter). Second\, they operate \nunder uncertainty—they lack direct visibility into the state of the\nn etwork or the flows they compete with. Recent work showed that we can\nmod el networks as non-deterministic\, non-stochastic automatons to\ncapture a wide range of real-world phenomena and formally verify\ncontroller perfor mance on such environments. We seek to design CCAs\nthat pass such verific ation checks. However\, this does not scale out\nof the box.\n\nWe find th at the key to making it tractable is to formally reason\nabout uncertainty in the state of the network and other flows. This\nthesis contributes two abstractions—beliefs and contracts—that\nenable such reasoning and re veal new structure in CCAs that simplifies\ntheir design and analysis. Bel iefs formalize what a CCA can infer\nabout latent network state from its o bservations. Contracts formalize\nhow flows coordinate with each other to share the network. Since flows\ncannot directly communicate\, they implici tly encode information in\nobservable congestion signals (e.g.\, delay or loss). Contracts\nformalize these communications mechanisms. Building on t hese\nabstractions\, we develop CCmatic\, a tool that automatically\nsynth esizes CCAs with verified performance guarantees. Our\nabstractions and to ols allow us to discover previously unknown\ntradeoffs\, design new CCAs t hat are on the Pareto-frontier\, and\nprovably guarantee performance even under challenging network\nconditions.\n\nThesis Committee\n\nSrinivasan S eshan (Chair)\n\nVyas Sekar\n\nJustine Sherry\n\nPhilip Brighten Godfrey ( University of Illinois Urbana-Champaign)\n\nVenkat Arun (University of Tex as at Austin)\n\nIn Person and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67604fbaa DTSTART;TZID=America/New_York:20251023T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20251023T153000 LOCATION:Newell-Simon 4305 SUMMARY:Doctoral Thesis Oral Defense - Costin Bădescu CLASS:PUBLIC DESCRIPTION:Speaker: COSTIN BĂDESCU\, Ph.D. Candidate\nComputer Science De partment\nCarnegie Mellon University\n\nTalk Title: Improved bounds for st ate certification\, separability\ntesting\, and shadow tomography\n\nWe pr esent improved sample complexity bounds for three fundamental\nquantum inf ormation tasks: state certification\, separability testing\,\nand shadow t omography. Given measurement access to n identical copies\nof an unknown q uantum state 𝜌\, we consider:\n\ni. State Certification: The task of ve rifying 𝜌 is equal to a\nreference state sigma or at least ε-far in tr ace distance.  We\npresent a testing algorithm for state certification th at uses O(d/\nε2) copies of 𝜌.\n\nii. Separability Testing: For a bipa rtite state 𝜌 on a\nd2-dimensional system\, we prove a lower bound of  𝛺(d2/ε2) copies\nare necessary to distinguish separability from being ε-far in trace\ndistance from the set of all separable states.\n\niii. S hadow Tomography: The problem of estimating the expectation\nvalues tr( 𝜌Ai) for m observables Ai\,...\,Am  to +/-ε accuracy. We\npresent an algorithm that accomplishes this with O(log2(m)\nlog(d)/ε4) copies\, wh ich simultaneously achieves the best known\ndependence on each parameter m \, d\, and ε.\n\nThesis Committee\n\nRyan O'Donnell (Chair)\n\nAayush Jai n\n\nDavid Woodruff\n\nJohn Wright (University of California\, Berkeley)  \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676050033 DTSTART;TZID=America/New_York:20250829T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250829T113000 LOCATION:Traffic21 Classroom and Zoom SUMMARY:Doctoral Thesis Oral Defense - Nirav Atre CLASS:PUBLIC DESCRIPTION:Speaker: NIRAV ATRE\, Ph.D. Candidate\nComputer Science Departm ent\nCarnegie Mellon University\n\nTalk Title: Refining Classical Abstract ions of Network Subsystems\n\nWe reason about computer systems via models of their behavior —\nwhether implicit mental models\, or explicit mathem atical models. These\nmodels are the linchpins of our decision-making abil ity\, e.g.\, in\nformulating service-level agreements (SLAs)\, or tenderin g performance\nclaims. Unfortunately\, a growing disconnect between how sy stems are\nmodeled and how they are actually deployed has engendered a cla ss of\nproblems I call model incongruity: circumstances where a model's\np rediction deviates significantly from real-world behavior. Model\nincongru ities are highly pervasive in modern systems\, resulting in\nexpensive per formance anomalies\, scalability bottlenecks\, and security\nvulnerabiliti es.\n\nIn this thesis\, we argue that many incongruities observed in pract ice\ntoday are not a fundamental limitation of our modeling capabilities\, \nbut rather artifacts of using the wrong models. We show that: (a)\nassum ptions centrally underpinning contemporary models of network\nsubsystems h ave drifted far from deployment realities\; (b) these\nassumptions are fre quently violated in the field\, subverting the\noperator's expectations ab out key metrics in highly unexpected ways\;\nand\, (c) making modest model refinements not only yields designs with\nstate-of-the-art performance\, attack resilience\, and scalability\, but\nalso enables us to make rigorou s mathematical guarantees about the\nresulting system's behavior.\n\nWe ex emplify this point using case studies of three ubiquitous network\nsubsyst ems. First\, I will describe \"delayed hits\"\, an incongruity\narising in high-performance caching systems which breaks the textbook\ncaching princ iple that maximizing cache hit-rate also minimizes\nlatency\, and causes e very existing caching algorithm to make\nlatency-suboptimal decisions\; in this context\, I will introduce\nMinimum-AggregateDelay (MAD)\, a turnkey augmentation to existing\nalgorithms that makes them aware of delayed hit s\, yielding 5-35% lower\nrequest latencies. Second\, I will describe \"al gorithmic complexity\nattacks\" (ACAs)\, a highly potent class of Denial-o f-Service attacks\narising from transient workload incongruity\; in this c ontext\, I will\nintroduce SurgeProtector\, an adversarial scheduling fram ework that\nprovably protects network dataplanes against ACAs\, resulting in 90-99%\nreduction in harm for the same volume of attack traffic. Finall y\, I\nwill describe BBQ\, a system borne out of addressing design incongr uity\nin hardware packet schedulers which\, for the first time\, makes it\ nfeasible to deploy packet scheduling at line-rate on modern switches\nand SmartNICs.  \n\nThesis Committee\n\nJustine Sherry (Chair)\n\nVyas Seka r \n\nWeina Wang \n\nBrighten Godfrey (University of Illinois Urbana-Cha mpaign)\n\nIn Person and Zoom Participation. See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760505ee DTSTART;TZID=America/New_York:20250828T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250828T120000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Joshua Williams CLASS:PUBLIC DESCRIPTION:Speaker: JOSHUA NATHANIEL WILLIAMS\, Ph.D. Candidate\nComputer Science Department\nCarnegie Mellon University\n\nTalk Title: Understandin g Representations of Humans in Generative\nImage Modeling Through Discrete Counterfactual Prompt Optimization\n\nText-to-image (T2I) models are wide ly used generative systems\, making\nit essential to understand how they r epresent human subjects.\nComparing generated images across carefully desi gned prompts can\nreveal representational patterns\, some of which reflect harmful biases\nrequiring intervention. Existing approaches often rely on fixed prompt\ntemplates or identity categories\, which are useful for ben chmarking\nbut risk blind spots shaped by researchers’ assumptions.\n\nT his thesis introduces methods grounded in counterfactual and\ncontrastive analysis to uncover representational asymmetries and harms\nbeyond predefi ned categories. We show that effective explanations for\nclassifiers must account for the underlying data distribution\; without\nthis\, analyses ri sk spurious conclusions. To address this\, we adapt\nthe graphical model u nderlying counterfactual explainability and\npropose a new distribution-aw are metric.\n\nBuilding on these insights\, we further develop distributio nally\ninformed approaches to prompt optimization in T2I settings. Our\nfr amework incorporates multiobjective optimization across language\nmodels w ith distinct tokenizers and embeddings\, enabling richer\nexploration of r epresentational behaviors. Finally\, we present an\nunsupervised strategy for surfacing candidate prompts that reveal\npreviously undocumented asymm etries. By linking the linguistic\npatterns of generative models to their visual outputs\, we advance\nmethods for diagnosing biases and targeting s pecific representational\nbehaviors in training and evaluation.  \n\nThe sis Committee\n\nZico Kolter (Chair)\n\nHoda Heidari\n\nAditi Raghunathan\ n\nSarah Laszlo (Visa)\n\nIn Person and Zoom Participation.  See announce ment.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676050a78 DTSTART;TZID=America/New_York:20250826T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250826T143000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 SUMMARY:Doctoral Thesis Oral Defense - Hojin Park CLASS:PUBLIC DESCRIPTION:Speaker: HOJIN PARK\, Ph.D. Candidate\nComputer Science Departm ent\nCarnegie Mellon University\n\nTalk Title: Cost-Efficient Storage and Caching in Public Clouds\n\nAs modern data-intensive workloads increasingl y migrate to the public\ncloud\, managing the resulting costs has emerged as a pressing\nchallenge despite the operational simplicity and elasticity that cloud\nenvironments offer. Although many efforts in cost optimizatio n have\nfocused on computation\, storage-related costs have received\ncomp aratively less attention despite being a significant portion of\ntotal clo ud spending. In particular\, two categories dominate\nstorage-related cost s in public cloud: the cost of deploying and\noperating storage clusters i n the cloud\, and the cost of accessing\ndata across geographically distri buted regions or clouds. These\nchallenges cannot be effectively addressed by existing optimization\ntechniques developed for on-premise environment s\, since they often\noverlook the unique characteristics of public clouds \, including\nelastic resource provisioning\, diverse cost-performance tra de-offs\,\nand dynamic and unique access patterns found in cloud object st orage\nworkloads.\n\nThis dissertation addresses these challenges by propo sing a\ncost-efficient approach to designing storage and caching systems t hat\nare cloud-aware\, elastic\, and adaptive to workload behavior. It\nin troduces three systems that target key aspects of cloud storage cost\nopti mization. First\, Mimir reduces the cost of the deployment of\nstorage clu sters by automatically selecting cost-effective\ncombinations of virtual m achines and block storage types\, based on\nprofiling workload characteris tics and benchmarking available resource\noptions. Second\, Macaron reduce s cross-region and cross-cloud data\naccess costs by auto-configuring a ca che with a tiered storage\narchitecture that leverages low-cost object sto rage and dynamically\nresizes the cache based on workload changes. Third\, Macaron+ builds on\nMacaron by introducing a cost-aware prefetching techn ique that\nanalyzes object-level access patterns to reduce latency in work loads\nwith high cold miss ratios\, while preserving cost-efficiency.\nTog ether\, these systems demonstrate that by tailoring automated\nresource se lection\, adaptive configuration\, and predictive techniques\nto the chara cteristics of the public cloud\, it is possible to\nsignificantly reduce t he cost of storing and accessing data.\n\nThesis Committee\n\nGeorge Amvro siadis (Co-chair)\n\nGregory R. Ganger (Co-chair)\n\nJignesh M. Patel\n\nC arlo Curino (Microsoft Research) \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676050fc7 DTSTART;TZID=America/New_York:20250807T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250807T123000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Madhusudan Reddy Pittu CLASS:PUBLIC DESCRIPTION:Speaker: MADHUSUDHAN REDDY PITTU\, Ph.D. Candidate\, Ph.D. Prog ram in\nAlgorithms\, Combinatorics and Optimization\, Computer Science\nDe partment\, Carnegie Mellon University\n\nTalk Title: Fairness\, Diversity\ , Explainability\, and Robustness for\nAlgorithmic Decision-Making\n\nThis thesis investigates foundational algorithmic challenges that\narise when embedding fairness\, diversity\, explainability\, and\nrobustness into com putational decision-making. As machine learning\nsystems\, resource alloca tion mechanisms\, and data analysis pipelines\nincreasingly influence crit ical decisions\, it is essential that these\nsystems uphold not only effic iency and accuracy but also ethical and\nstructural guarantees. However\, enforcing these principles introduces\ncomplex trade-offs and computationa l difficulties.\n\nWe address five core problems that capture different fa cets of\nalgorithmic decision-making under structural and informational\nc onstraints: (1) determinant maximization under matroid constraints\,\nmode ling the selection of diverse and representative subsets\; (2)\napproximat ion of the weighted Nash Social Welfare objective\, a\nfairness-centric fo rmulation in indivisible resource allocation\; (3)\nconstrained subspace a pproximation\, which enforces group-level\nrepresentation in data summariz ation\; (4) explainable clustering\,\nwhich trades off interpretability an d clustering quality using\ndecision trees with axis-aligned threshold cut s\; and (5) combinatorial\noptimization using comparison oracles\, which e nables robust\ndecision-making in uncertain or preference-driven environme nts.\n\nEach of these problems introduces structural constraints that\ncha llenge conventional algorithmic techniques. We develop new\nframeworks tha t combine combinatorial methods\, convex and non-convex\nrelaxations\, con vex geometry\, and probabilistic methods. The resulting\nalgorithms offer improved approximation guarantees\, shed light on key\ntrade-offs between fairness\, interpretability\, and performance\, and\nsupport the developme nt of more equitable\, interpretable\, diverse\, and\nreliable algorithmic systems. These contributions have broad\nimplications in machine learning \, economics\, data summarization\, and\nhuman-in-the-loop decision-making .\n\nThesis Committee\n\nDavid P. Woodruff (Co-Chair)\n\nAnupam Gupta (Co- chair)\n\nPrasad Tetali\n\nMohit Singh (Georgia Institute of Technology)\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760514a5 DTSTART;TZID=America/New_York:20250729T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250729T143000 LOCATION:McWilliam Classroom\, Gates Hillman 4304 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Jun-Ting Hsieh CLASS:PUBLIC DESCRIPTION:Speaker: JUN-TING HSIEH\, Ph.D. Candidate\nComputer Science Dep artment\nCarnegie Mellon University\n\nTalk Title: Algorithms and Explicit Constructions via Spectral\nTechniques\n\nSpectral methods have become ub iquitous in computer science. By\nanalyzing the eigenvalues and eigenvecto rs of matrices naturally\nassociated with a graph\, such as its adjacency matrix\, one can extract\nuseful information about the graph's structure. Such methods have\nyielded the best-known results for a wide range of foun dational\nproblems.\n\nIn this talk\, we apply this \"spectral lens\" to p rove new results in\ngraph theory\, design algorithms\, and construct expl icit vertex\nexpanders.\n\nIn the first part of this talk\, we present alg orithms for both\nrefuting semi random constraint satisfaction problems an d recovering\nsolutions in planted ones\, both utilizing spectral informat ion of the\nunderlying hypergraph. Moreover\, we give algorithms to find l arge\nindependent sets in spectral expanders.\n\nIn the second part of thi s talk\, we introduce the tripartite line\nproduct to construct constant-d egree vertex expanders. First\, we\nobtain explicit unique-neighbor expand ers by instantiating the product\nusing Ramanujan graphs – the optimal s pectral expanders. Then\, by\nreplacing Ramanujan graphs with the incidenc e graphs of Ramanujan\ncubical complexes\, we obtain the first explicit lo ssless vertex\nexpanders. \n\nThesis Committee\n\nPravesh K. Kothari (Cha ir\, Carnegie Mellon University/Princeton\nUniversity) \n\nRyan O'Donnell \n\nJason Li\n\nVenkatesan Guruswami (University of California\, Berkeley) \n\nDavid Steurer (ETH Zürich)\n\nIn Person and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676051914 DTSTART;TZID=America/New_York:20250729T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250729T123000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Arjun Teh CLASS:PUBLIC DESCRIPTION:Speaker: ARJUN TEH\, Ph.D. Candidate\nComputer Science Departme nt\nCarnegie Mellon University\n\nTalk Title: Computational Lens Design\n\ nContemporary lens design\, therefore\, presents a multifaceted\noptimizat ion challenge. A typical compound lens system is\ncharacterized by both co ntinuous parameters\, such as surface shape and\nthicknesses\, and discret e choices\, such as the number of elements and\ntypes of material. This mi xed discrete-continuous parameter space\ncreates a complex design landscap e where the performance of the lens\nis highly sensitive to all of the cho ices of parameters. This design\nspace has been historically hard for desi gners to navigate\,\nnecessitating assistance from theoretical and computa tional tools that\nhelp guide the search for performant designs. Yet\, eve n with these\ntools\, design remains time consuming and requires a great d eal of\ndesigner input. In parallel\, the graphics community has developed \nmethods for differentiable rendering\, which enable gradient-based\nopti mization of image based tasks. These methods have been\nsuccessfully appli ed to a variety of problems and are a great\ncandidate for application to lens design. However\, there are key\ndifferences in lens design from gene ral rendering that make directly\napplying these methods to lens design ch allenging.\n\nThe purpose of this thesis is to develop methods that levera ge ideas\nand techniques from differentiable rendering to address the chal lenges\nof lens design\, by developing a set of theoretical and computatio nal\ntools tailored to the unique requirements of lens design. Firstly\, w e\nbuild a method for calculating the unbiased gradient of light\nthroughp ut with respect to lens parameters\, enabling the optimization\nof lens sp eed. Secondly\, we devise Markov chain Monte Carlo (MCMC)\nmethod that com bines gradient-based optimization of continuous\nparameters with discrete mutations that change the number of elements\nin a lens system. Lastly\, w e derive a constant memory method for\ncalculating gradients of ray paths through gradient-index (GRIN)\nmaterials allowing for optimization of GRIN lenses\n\nThesis Committee\n\nIoannis Gkioulekas (Co-chair)\n\nMatthew O' Toole (Co-chair)\n\nJames McCann\n\nBernd Bickel (ETH Zürich)\n\nIn Perso n and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676051dea DTSTART;TZID=America/New_York:20250718T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250718T153000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Jeff Xu CLASS:PUBLIC DESCRIPTION:Speaker: JEFF XU\, Ph.D. Candidate\nComputer Science Department \nCarnegie Mellon University\n\nTalk Title: Spectral Techniques for Averag e-Case Complexity and Beyond\n\nIn recent years\, algorithmic challenges a cross diverse areas including\nstatistical physics\, machine learning and cryptography have centered\naround statistical inference problems\, i.e.\, computational problems\nwith average-case inputs. For many of these probl ems\, the best-known\nefficient algorithms are often suboptimal\, giving r ise to information\nvs. computation gaps\, discrepancies between what is t heoretically\npossible given the amount of information and what can be att ained via\nefficient algorithms. One fundamental question is how we can pr ovide\nrigorous evidence of hardness to show that such gaps are\ninsurmoun table for efficient computation. \n\nIn this talk\, I will demonstrate th at many of these questions boil\ndown to the study of random matrices that have entries being\npolynomials of the underlying input. More concretely\ , I will highlight\nthe recent advances in the past few years that lead to a significantly\nmore refined understanding of these ostensibly complicat ed matrices\,\nand some intriguing questions around them that still remain after\nyears of attacks.  The sharper understanding of these matrices\nu ltimately allows us to provide rigorous evidence via the lens of the\nSum- of-Squares (SoS) algorithms\, a hierarchy of semidefinite\nprogrammings. U nlike several other popular models in the average-case\nsetting (eg. low-d egree polynomials/statistical-query/ overlap-gap).\nSum-of-Squares algorit hms are known to capture various optimal\nalgorithms in both the average a nd worst-case setting\, and therefore\nprovide one of the strongest form o f hardness in average-case\ncomplexity.\n\nThesis Committee\n\nPravesh K. Kothari (Chair )\n\nAayush Jain\n\nRyan O’Donnell\n\nMadhur Tulsiani (To yota Technical Institute at Chicago /  University\nof Chicago)\n\nIn Pers on and Zoom Participation.  See announcement. \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676052283 DTSTART;TZID=America/New_York:20250718T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250718T113000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Long Pham CLASS:PUBLIC DESCRIPTION:Speaker: LONG PHAM\, Ph.D. Candidate\nComputer Science Departme nt\nCarnegie Mellon University\n\nTalk Title: Hybrid Resource-Bound Analys es of Programs\n\nResource-bound analysis aims to infer symbolic bounds of worst-case\nresource usage (e.g.\, running time and memory) of programs.\ nApplications of resource analysis include job scheduling and\nprevention of side-channel attacks. Different resource-analysis\ntechniques have comp lementary strengths and weaknesses. (Automatic)\nstatic resource analysis\ , which analyzes the source code of programs\,\nis sound: if it successful ly infers a cost bound\, it is guaranteed to\nbe a valid bound. However\, due to the undecidability of resource\nanalysis in general\, every static analysis technique is incomplete:\nthere exists a program that the analysi s technique cannot handle.\nMeanwhile\, data-driven analysis\, which stati stically analyzes cost\nmeasurements obtained by running programs on many inputs\, can infer a\ncandidate cost bound for any program. However\, it d oes not guarantee\nsoundness of inference results.\n\nTo overcome limitati ons of individual analysis techniques\, this thesis\ndevelops hybrid resou rce analysis\, which integrates two complementary\nanalysis techniques via a user-adjustable interface. The user first\nspecifies which analysis tec hniques should analyze which code\nfragments and quantities. Hybrid analys is then performs its\nconstituent analysis techniques on their respective code fragments and\nquantities. Finally\, their inference results are comb ined into an\noverall cost bound. Hybrid resource analysis retains the str engths of\nconstituent analyses while mitigating their respective weakness es.\n\nThe thesis introduces two hybrid-resource-analysis techniques: Hybr id\nAARA and resource decomposition. They adopt distinct designs of an\nin terface between constituent analyses\, posing a trade-off in the\nflexibil ity of hybrid analysis. Hybrid AARA integrates static resource\nanalysis-- -Automatic Amortized Resource Analysis (AARA)---with\ndata-driven resource analysis via a type-based interface. On the other\nhand\, resource decomp osition integrates different pairs of static\,\ndata-driven\, and interact ive resource analyses via a\nnumeric-variable-based interface.\n\nIn addit ion to hybrid resource analysis\, I discuss theoretical results\nof resour ce analysis: (i) the undecidability of resource analysis\; and\n(ii) the p olynomial-time completeness of Conventional AARA. I also\ndescribe newly d eveloped Bayesian data-driven resource analysis\, which\nstatistically inf ers cost bounds by Bayesian inference. Finally\, I\npresent the optimizati on of probabilistic program-input generators by\na genetic algorithm\, sho wing that its output generator is more\neffective in triggering high compu tational cost than randomly\ngenerated inputs.\n\nThesis Committee\n\nJan Hoffmann (Chair)\n\nFeras Saad\n\nMatt Fredrikson\n\nFrancois Pottier (Inr ia\, Paris)\n\nIn Person and Zoom Participation.  See announcement. \n\n  \n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676052862 DTSTART;TZID=America/New_York:20250703T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250703T160000 LOCATION:Reddy Conference Room\, Gates HIllman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Brian Hu Zhang CLASS:PUBLIC DESCRIPTION:Speaker: BRIAN HU ZHANG\, Ph.D. Candidate\, Computer Science De partment\,\nCarnegie Mellon University\n\nTalk Title: New Solution Concept s and Algorithms for Equilibrium\nComputation and Learning in Extensive-Fo rm Games and Beyond\n\nComputational game theory has led to significant br eakthroughs in AI\ndating back to the start of AI as a discipline. For exa mple\, it has\nbeen instrumental in enabling superhuman AI from recreation al games\nsuch as two-player zero-sum games chess\, go\, and heads-up poke r to\nmultiplayer games such as six-player poker and Hanabi\, and even in\ ngames involving human language such as Diplomacy. It has also\nempowered a growing range of non-recreational applications\, such as\ntrading\, mach ine learning robustness and safety\, negotiation\, conflict\nresolution\, mechanism (e.g.\, auction) design\, information design\,\nsecurity\, polit ical campaigning\, and self-driving cars. \n\nThis thesis pushes the boun dary on computational game theory\,\nespecially in imperfect-information s equential (extensive-form) games\,\nwhich are most prevalent in practical applications both in zero-sum\ngames and beyond. We will present new theor etical concepts and\nframeworks\, state-of-the-art and often provably opti mal algorithms for\ncomputing and learning equilibria\, and new ways to ap ply such\nalgorithms to real-world problems\, including problems in econom ics\nsuch as mechanism and information design. We will also draw\nconnecti ons to the broader literature on optimization\, yielding new\nand more eff icient algorithms for solving variational inequalities.\n\nThesis Committe e\n\nTuomas Sandholm (Chair)\n\nVincent Conitzer\n\nJ. Zico Kolter\n\nKevi n Leyton-Brown (University of British Columbia)\n\nIn Person and Zoom Part icipation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676052ce0 DTSTART;TZID=America/New_York:20250702T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250702T170000 LOCATION:Reddy Conference Room\, Gates HIllman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Sara McAllister CLASS:PUBLIC DESCRIPTION:Speaker: SARA McALLISTER\, Ph.D. Candidate\, Computer Science\n Department\, Carnegie Mellon University\n\nTalk Title: Toward Sustainable Datacenters through Efficient Data\nRetrieval\n\nDatacenters are projected to account for 33% of the global carbon\nemissions by 2050. As datacenter s increasingly rely on renewable\nenergy for power\, the majority of datac enter emissions will be\nembodied — emissions from lifecycle stages incl uding acquiring raw\nmaterials\, manufacturing\, transportation\, and disp osal. To reach the\nambitious emission reduction goals set by both compani es and\ngovernments\, datacenters need to reduce emissions throughout thei r\noperations\, including (and particularly relevant for this thesis) the\ nstorage system. Unfortunately\, while data storage and retrieval\nsystems are large contributors to embodied emissions\, reducing their\nembodied e missions have largely been overlooked.\n\nThis dissertation addresses how to reduce emissions in data retrieval\nfor large-scale storage systems. Th ese storage systems can reduce\ntheir carbon footprint by enabling storage devices to have longer\nlifetimes and use denser media. However\, storage hardware's IO limits\ncombined with software's unnecessary additional IO often severely\nrestrict emission reductions\, or at worse cause increased emissions.\nThus\, this thesis focuses on reducing IO in several parts of the\nstorage stack to enable efficient and sustainable data retrieval.\n\ nFirst\, this dissertation addresses the sustainability of flash\ncaching\ , a critical layer in datacenter storage systems that is\nlimited by flash write endurance. This improvement results from two\ncaching systems: Kang aroo and FairyWREN. Together\, these caches\ndramatically reduce writes by over 28x\, allowing flash devices to use\ndenser flash for longer lifetim es\, ultimately reducing emissions.\nThen\, this thesis discusses enable m ore sustainable bulk storage\,\nwhere bandwidth limitations prevent deploy ment of denser HDDs.\nDeclarative IO\, a new interface for distributed sto rage\, empowers the\nstorage system to eliminate duplicate IO accesses in maintenance tasks\nthrough exposing the time- and order-flexibility in mai ntenance tasks.\nThis work enables deployment of larger HDDs\, further red ucing\nemissions from storage systems.\n\nThesis Committee\n\nGregory R. G anger (Co-Chair)\n\nNathan Beckmann (Co-Chair)\n\nGeorge Amvrosiadis\n\nDa niel Berger (Microsoft Azure/University of Washington)\n\nMargo Seltzer (U niversity of British Columbia)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676053247 DTSTART;TZID=America/New_York:20250702T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250702T160000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Siddharth Prasad CLASS:PUBLIC DESCRIPTION:Speaker: SIDDHARTH PRASAD\, Ph.D. Candidate\, Computer Science\ nDepartment\, Carnegie Mellon University\n\nTalk Title: Mechanism Design a nd Integer Programming in the Data Age\n\nThis thesis focuses on improving computational and economic aspects of\nmechanism design\, and on improvin g critical components of integer\nprogramming algorithms. Various marketpl aces in the world today\, from\nspectrum allocation to strategic sourcing to display advertisements to\nfinancial exchanges and more\, benefit from carefully engineered rules\nto govern the efficient exchange of items. Mec hanism design offers a\nprincipled way to design the rules to such market- based systems in\norder to implement desired market outcomes subject to st rategic\nself-interested participants. It is the prominent approach to man y\nmarket design problems and has been deployed in the real world with\nhi gh impact. On the computational front\, integer programming is the\ngo-to method for solving discrete optimization problems that arise in\nmarket de sign applications and beyond.\n\nWithin mechanism design\, our focus is on the design of better\nmechanisms that take advantage of any and all infor mation available to\nthe mechanism designer. Our new mechanisms provably g eneralize and\nimprove the state of the art\, and significantly expand the scope of\nwhat forms of information can be expressed and used to boost\np erformance. We apply our advances in mechanism design to\ncombinatorial ma rkets where bidders have complex\, combinatorial\npreferences over a rich space of outcomes. Here\, our new combinatorial\nauctions directly improve over existing designs that have been used to\nconduct high-stakes auction s around the world.\n\nWithin integer programming\, our focus is on the th eory and practice of\ncutting planes\, which are one of the most critical components of\ninteger programming solvers. We invent new cutting planes t hat deliver\nstrong theoretical and practical performance\, and develop a\ ncomprehensive generalization theory for data-driven parameter\nconfigurat ion within the branch-and-cut algorithm. \n\nIn both areas\, we fundament ally advance the classical state of\nknowledge and introduce new data-driv en perspectives\, all in support\nof the thesis that high performance—e. g.\, revenue\, social welfare\,\nrun-time\, memory\, etc.—in marketplace s can only be fully realized by\na synergy of approaches in mechanism desi gn\, integer programming\, and\nmachine learning.\n\nThesis Committee\n\nM aria-Florina Balcan (Co-Chair)\n\nTuomas Sandholm (Co-Chair)\n\nGérard Co rnuéjols\n\nCraig Boutilier (Google)\n\nPeter Cramton (University of Mary land)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760537b7 DTSTART;TZID=America/New_York:20250527T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250527T140000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Suhas Jayaram Subramanya CLASS:PUBLIC DESCRIPTION:Speaker: SUHAS JAYARAM SUBRAMANYA\, Ph.D. Candidate\, Computer Science\nDepartment\, Carnegie Mellon University\n\nTalk Title: Efficient and Responsive Job-Resource Co-adaptivity for\nDeep Learning Workloads in Large Heterogeneous GPU Clusters\n\nExisting cluster schedulers face many limitations in scheduling\nadaptive deep learning training jobs on large h eterogeneous GPU\nclusters – many are not heterogeneity-aware\, few are\ nadaptivity-aware\, and none scale to large clusters without sacrificing\n allocation fidelity or cluster efficiency. Emerging clusters further\ncomp licate this problem with larger\, more heterogeneous resources\nrunning m ore increasingly diverse jobs with more dimensions of\nadaptivity.\n\nThis thesis develops new scheduling approaches and algorithms that can\n(1) sc ale to emerging clusters with hundreds of thousands of GPUs and\nmany GPU types\, (2) quickly optimize high-fidelity allocations for\nadaptive DL tr aining jobs with low scheduler overhead\, and (3)\nefficiently adapt to ch anging cluster conditions to improve goodput on\nthe limited GPU resources .\n\nWe first introduce Sia — a round-based scheduler that efficiently\n optimizes adaptive jobs in a heterogeneous cluster with many GPU\ntypes. S ia uses GPU resources judiciously to gather information on\njob-GPU fit-le vels using a mix of online and offline profiling\, and\ncontinuously co-op timizes the GPU resources allocated to jobs and\ntheir execution parameter s at runtime to maximize cluster-wide\ntraining progress. Using job traces derived from real-world data\ncenters\, we find that Sia ’s allocations are fair and efficient\, and\nare quickly computed using an efficient for mulation\, even for 1000-GPU\nclusters.\n\nSecond\, we introduce continual optimization — a new paradigm that\nexplicitly models the slow evolutio n of resource-allocation problems\nat scale to reduce solver runtime for q uick responses to changes in\njobs or resources. We then introduce COpter\ , our approach to continual\noptimization that (a) efficiently updates the optimization problems\nfor job and resource changes using a differential interface\, (b)\nimplements a factorization-free warm-started LP solver to benefit from\nslowly-evolving nature of the allocations\, and (c) impleme nts\nlightweight heuristics to recover feasible integral solutions with\nn egligible quality loss. In our evaluations\, COpter speeds up Sia\nschedu ler policy by a few orders of magnitude on clusters with tens of\nthousand s of GPUs without sacrificing job completion times and\nmakespan.\n\nThird \, COpter is easily applied to resource-allocation problems in\nother doma ins (e.g. shard load-balancing\, WAN traffic engineering) and\nwe see 57 − 83 × reductions in solver runtimes.\n\nThesis Committee\n\nGregory Ga nger (Chair) Zhihao Jia Virginia Smith Amar Phanishayee\n(Meta Platforms I nc.)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676053d3d DTSTART;TZID=America/New_York:20250520T090000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250520T110000 LOCATION:Reddy Conference Room\, Gates HIllman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Mingjie Sun CLASS:PUBLIC DESCRIPTION:Speaker: MINGJIE SUN\, Ph.D. Candidate\, Computer Science Depar tment\,\nCarnegie Mellon University\n\nTalk Title: Hidden Properties of La rge Language Models\n\nLarge Language Models (LLMs) are deep learning mode ls trained to\nunderstand and generate natural language. Over the course o f my PhD\,\nthese models have profoundly transformed the field of machine\ nlearning. Despite their remarkable success\, most of our interactions\nwi th LLMs remain largely black-box\, leaving key questions about their\ninte rnal mechanisms and behaviors under-explored.\n\nThis thesis investigates previously overlooked hidden properties of\nLLMs across three dimensions: internal weight structure\, activation\npatterns\, and output behaviors. F irst\, we demonstrate that the weight\nspace of LLMs is intrinsically spar se and present a principled pruning\napproach capable of extracting effici ent sparse subnetworks directly\nfrom pre-trained models. Next\, we reveal the existence of structured\nactivation outliers in LLMs\, which we call \"massive activations\".\nThese activations\, despite their rarity\, are e xceptionally high in\ntheir magnitudes. We establish their strong connecti on to the\nself-attention mechanism and propose a novel attention formulat ion\nthat mitigates these extreme outliers. Finally\, we characterize the\ nidiosyncrasies of LLM outputs\, showing that generations from different\n models can be distinguished with remarkably high accuracies. We\nfurther i dentify the specific signatures that underlie these\ndifferences. Collecti vely\, these findings provide an alternative\nperspective on modern founda tion models. \n\nThesis Committee\n\nJ. Zico Kolter (Chair)\n\nGraham Neu big\n\nAditi Raghunathan\n\nKaiming He (Massachusetts Institute of Technol ogy)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760541fd DTSTART;TZID=America/New_York:20250515T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250515T160000 LOCATION:Gates Hillman 6501 SUMMARY:Doctoral Thesis Oral Defense - Meng-Chieh (Jeremy) Lee CLASS:PUBLIC DESCRIPTION:Speaker: MENG-CHIEH (JEREMY) LEE\, Ph.D. Candidate\, Computer S cience\nDepartment\, Carnegie Mellon University\n\nTalk Title: Explainable Mining of Graphs and Time Series: Algorithms\nand Applications\n\nGiven a social network graph\, how can we predict connections between\nusers and determine whether they are based on shared hobbies or common\nfriends? Giv en a database containing molecular graphs\, how can we\ndetermine whether the graphs inhibit HIV replication based on\nsubstructures they frequently share? Similarly\, in time series data\nfrom EEG recording\, how can we i dentify seizures and explain why they\nare considered abnormal? Although r ecent machine learning methods have\nshown improved performance\, many rem ain black-box models\, making\nexplainability challenging. This leads us t o explainable artificial\nintelligence (XAI)\, which offers valuable insig hts through its\nexplanations and is more practical for deployment in real -world\napplications.\n\nIn this thesis\, we focus on developing explainab le machine learning\nmethods tailored for graphs and time series. Each met hod we propose is\neither inherently explainable\, or designed to automati cally provide\ndata analysis or justification for its decisions. In each p art\, we\npresent effective and general algorithms\, and explore a broad r ange of\napplications.\n\nThesis Committee\n\nChristos Faloutsos (Co-chair )\n\nLeman Akoglu (Co-chair)\n\nGeoffrey Gordon\n\nNina Mishra (Amazon)\n\ nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676054669 DTSTART;TZID=America/New_York:20250512T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250512T123000 LOCATION:Gates Hillman 8102 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Dorian Yao Chan CLASS:PUBLIC DESCRIPTION:Speaker: DORIAN YAO CHAN\, Ph.D. Candidate\, Computer Science\n Department\, Carnegie Mellon University\n\nTalk Title: Holographic Display s for Computer Vision\n\nArtificial illumination is ubiquitous in real vis ion systems. By\ncoding extra information from a controlled light source i nto the\nimages captured by a camera\, so-called \"active sensing\" approa ches\nrobustly capture depth\, reflectance and other visual cues crucial t o\ntasks in robotics\, manufacturing\, consumer products and more. However \,\nactive sensors struggle with well-known challenges that limit their\np racticality in modern applications — available power limits range\nand o utdoor performance\, slow speed precludes dynamic scenes and\ndefocused st ructured illumination reduces effective resolution. \n\nTo tackle these c hallenges\, this thesis explores using holographic\ndisplays. Holographic displays have recently seen significant\nattention in the augmented and vi rtual reality (AR/VR) literature. By\nsimply illuminating a spatial-light modulator (SLM) with laser light\,\nsuch devices can simultaneously provid e accommodation cues and\nglasses-free vision correction all in a compact form factor\, key\ncapabilities that are currently missing in modern AR/VR architectures.\n\nIn our work\, we analyze how they can potentially be ad apted as sources\nof active illumination. First\, we show how holographic displays can be\nused to build light redistributive projectors that allow for smarter\nenergy usage in active sensing\, enabling time-of-flight sens ors with\nfar-improved dynamic range. Next\, we demonstrate how this light \nredistribution\, when combined with the underlying fast speed of modern\ nSLMs\, allows for far faster projector systems\, allowing for new types\n of triangulation light curtains. Finally\, we test how the inherent\ncoher ent propagation of holographic systems can be used to program\nmeaningful content at multiple projector depths\, enabling new user\ninterfaces and d epth-sensing methodologies.\n\nOverall\, this defense advances the state-o f-the-art in active sensing\nby demonstrating new ways in which light can be shaped and\nconcentrated via holographic illumination systems. These ab ilities\nunlock vision systems with increased robustness and newfound\ncap abilities. \n\nThesis Committee\n\nMatthew O’Toole (Chair)\n\nIoannis G kioulekas\n\nAswin Sankaranarayanan\n\nMohit Gupta (University of Wisconsi n–Madison)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676054bc0 DTSTART;TZID=America/New_York:20250501T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250501T150000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Justin Raizes CLASS:PUBLIC DESCRIPTION:Speaker: JUSTIN RAIZES\, Ph.D. Candidate\, Computer Science Dep artment\,\nCarnegie Mellon University\n\nTalk Title: Quantum Approaches to Verifiable Deletion\n\nIntriguingly\, the laws of physics allow protocols executed by quantum\ncomputers to realize security guarantees that are im possible for\nclassical computers. One of these new possibilities is the a bility to\ntemporarily send ciphertexts to a user\, then later verify that the\nencoded message has been destroyed in an information-theoretic sense .\nBroadbent and Islam (TQC) introduced this notion\, called certified\nde letion\, in the context of encryption. However\, there are many more\nscen arios in which verifiable deletion is useful. For example\, a\nsoftware re ntal company might want to temporarily send their software\nto a user\, th en request that the user destroys the copy at the end of\nthe rental perio d. In this thesis\, we expand the realm of certified\ndeletion to cryptogr aphic primitives beyond just encryption. We define\nand construct the foll owing objects with certified deletion:\n\nObfuscation with Certified Delet ion allows a company to lend a program\nto a user\, allowing them to evalu ate it as they wish. Then\, when the\nuser no longer wish to rent the prog ram\, they can destroy it and prove\nto the issuer that they are no longer able to evaluate the program.\nObfuscation with certified deletion also e nables several new\napplications such as certifiably deletable secret keys .Secret Sharing\nwith Certified Deletion allows a user to distribute share s of a secret\nto several parties. In the event of a data breach\, the use r can\nrequest that the affected party deletes their shares\, rendering th em\nuseless for stealing the secret.Signatures with Certified Deniability\ nallow a signer to endorse a statement in a single message. After the\nrec eiver has verified the signature\, they can destroy it and prove to\nthe s igner that they are no longer able to provide convincing evidence\n- of an y kind - that the signer endorsed this statement. We also show\nhow to con struct the related primitive of NIZKs with certified\ndeniability.Certifie d deniability is a new\, more comprehensive\nparadigm for certified deleti on that rules out additional attacks not\nexplicitly considered by prior d efinitions.\n\nTo build these primitives\, we develop new techniques for v erifying the\ndeletion of information while still allowing access to the i nformation\nunder appropriate conditions.\n\nThesis Committee\n\nVipul Goy al (Chair)\n\nAayush Jain\n\nElaine Shi\n\nGiulio Malavolta (Bocconi Unive rsity)\n\n \n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676055131 DTSTART;TZID=America/New_York:20250429T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250429T150000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Mingxun Zhou CLASS:PUBLIC DESCRIPTION:Speaker: MINGXUN ZHOU\, Ph.D. Candidate\, Computer Science Depa rtment\,\nCarnegie Mellon University\n\nTalk Title: Practical Private Info rmation Retrieval and Searching with\nSublinear Cost\n\nIn this thesis\, w e investigate Private Information Retrieval (PIR)\, a\ncryptographic proto col that enables clients to access information from\na database without re vealing their queries to the server. As a\nfundamental building block for privacy-preserving applications\, PIR\nhas been extensively studied in bot h theory and practice for\ndecades. \n\nHowever\, practical implementatio ns have been limited to small-scale\nuse cases due to the linear computati on barrier of PIR\, which requires\nthe server to process the entire datab ase for each query. The seminal\nworks of Beimel\, Ishai\, and Malkin (Cry pto 2000) and Corrigan-Gibbs\nand Kogan (Eurocrypt 2022) introduced Prepro cessing PIR to overcome\nthis barrier. While theoretically efficient\, pre vious\nconstructions remained impractical due to their reliance on expens ive\ncryptographic operations. \n\nTo address this limitation\, we propos e two new PIR schemes: Piano and\nQuarter-PIR. Both achieve sublinear serv er computation and\ncommunication while remaining efficient in practice. T hese\nconstructions transform the practical PIR landscape by providing nea r\nreal-time responses for databases with billions of entries\,\nwhile ma intaining reasonable communication and storage\nrequirements. \n\nFurther more\, we demonstrate the practical utility of our PIR schemes\nthrough an important application – private information searching. We\ndevelop Pacm ann\, a new private approximate nearest neighbor search\nalgorithm that de livers both high search quality and fast response\ntimes for databases wit h hundreds of millions of records. \n\nOur work makes a significant step toward bridging the gap between\ntheory and practice in PIR research. Thes e contributions not only\nadvance the state of the art in PIR designs\, bu t also open new avenues\nfor developing privacy-preserving applications in real-world and\nlarge-scale settings.\n\nThesis Committee\n\nElaine Shi ( Co-Chair)\n\nGiulia Fanti (Co-Chair)\n\nBryan Parno\n\nDavid J. Wu (Univer sity of Texas at Austin)\n\nIn Person and Zoom Participation.  See announ cement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760557db DTSTART;TZID=America/New_York:20250428T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250428T170000 LOCATION:Gates Hillman 8102 and Zoom SUMMARY:Doctoral Thesis Oral - Yi Zhou CLASS:PUBLIC DESCRIPTION:Speaker: YI ZHOU\, Ph.D. Candidate\, Computer Science Departmen t\,\nCarnegie Mellon University\n\nTalk Title: Towards Scalable Automated Program Verification for System\nSoftware\n\nAutomated Program Verificatio n (APV) provides formal guarantees about\nsoftware while promising strong automation in the verification\nprocess. APV has already seen preliminary successes in system software\n(e.g.\, file systems\, network protocols)\, extending beyond academic\nprototypes to industrial applications. However\ , the scalability of APV\nbecomes an issue as we move towards more complex systems\, where\nautomation failures start to show up. Such failures ofte n require\ntedious manual fixes\, breaking the pledge of automation in APV . Worse\nyet\, since program verification is fundamentally undecidable\,\n automation failures are inherently inevitable. \n\nNevertheless\, that do es not mean APV is hopeless beyond small-scale\nsystems. In this thesis\, we organize the discussion around the\ndevelopment stages of APV: (1) crea ting proofs\, (2) reusing proofs\,\n(3) debugging proofs\, and (4) stabili zing proofs. We argue that\,\ndespite the undecidable nature of program ve rification in theory\, we\ncan overcome the scalability challenges that ar ise in practice\, due to\nthe recurrent patterns in APV programming and re asoning. \n\nSpecifically\, we make empirical observations on the common motifs in\nAPV\, and then design formal methods to leverage them for autom ation.\nUsing large-scale verified systems as case studies\, we show this\ ncombination of formal and empirical methods leads to practical\nimprovem ents in APV for system software.   \n\nThesis Committee \n\nBryan Parn o (Chair)\n\nMarijn Heule\n\nRuben Martins\n\nJon Howell (VMware Research / University of Washington)\n\nIn Person and Zoom Participation.  See ann ouncement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676055ce3 DTSTART;TZID=America/New_York:20250415T133000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250415T153000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Runtian Zhai CLASS:PUBLIC DESCRIPTION:Speaker: RUNTIAN ZHAI\, Ph.D. Candidate\, Computer Science Depa rtment\,\nCarnegie Mellon University\n\nTalk Title: Contextures: The Mecha nism of Representation Learning\n\nThis thesis establishes the contexture theory to mathematically\ncharacterize the mechanism of representation lea rning\, also known as\npretraining. Despite the remarkable empirical succe ss of foundation\nmodels\, it is not very clear what representations they learn\, and why\nthese representations are useful for various disparate do wnstream\ntasks. A scientific understanding of representation learning is\ ncritical\, especially at this point when scaling up the model size is\npr oducing diminishing returns\, and designing new pretraining methods\nis im perative for further progress. Prior work treated different\nrepresentatio n learning methods quite differently\, whereas the\ncontexture theory prov ides a unified framework for delineating the\nrepresentations these method s learn. \n\nThe central argument is that a representation is learned fro m the\nassociation between the input X and a context variable A. We prove\ nthat if an encoder captures the maximum information of this\nassociation\ , in which case we say that the encoder learns the\ncontexture\, then it w ill be optimal on the class of tasks that are\ncompatible with the context . We also show that a context is the most\nuseful when the association bet ween X and A is neither too strong nor\ntoo weak. The important implicatio n of the contexture theory is that\nincreasing the model size alone will a chieve diminishing returns\, and\nfurther advancements require better cont exts. We demonstrate that lots\nof existing pretraining objectives can lea rn the contexture\, including\nsupervised learning\, self-supervised learn ing\, generative models\, etc.\nBased on that\, we introduce two general o bjectives---SVME and KISE\,\nfor learning the contexture. We also show how to mix multiple contexts\ntogether\, which is an effortless way to create better contexts from\nexisting ones. Then\, we prove statistical learning bounds for\nrepresentation learning\, and extend the framework to spectra lly\ntransformed kernel regression for semi-supervised learning. Finally\, \nwe discuss the effect of the data distribution shift from pretraining\nt o the downstream task.  \n\nThesis Committee\n\nPradeep Ravikumar (Co-Ch air)\n\nZico Kolter (Co-Chair)\n\nAndrej Risteski\n\nYuandong Tian (Meta)\ n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760561ce DTSTART;TZID=America/New_York:20250411T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250411T130000 LOCATION:Traffic21 Classroom and Zoom SUMMARY:Doctoral Thesis Oral Defense - Magdalen Dobson Manohar CLASS:PUBLIC DESCRIPTION:Speaker: MAGDALEN DOBSON MANOHAR\, Ph.D. Candidate\, Computer S cience\nDepartment\, Carnegie Mellon University\n\nTalk Title: New Techniq ues for Parallelism and Concurrency in Nearest\nNeighbor Search\n\nNearest neighbor search in both high and low dimensions is an\nimportant problem in the field of computer science and beyond. In this\nthesis\, we extend t he capabilities of nearest neighbor search\nalgorithms to meet modern dema nds\, including support for billion-scale\nindices\, parallelism and concu rrency on machines with hundreds of\ncores\, efficient updates\, and exten sions to related geometric problems\nsuch as range search. We progress tow ards this goal by introducing the\nzd-tree\, a data structure for low-dime nsional nearest neighbor search\nwith provable guarantees on the work and span of search\, build\, and\nupdate\, a scalable parallel build\, and the ability to perform\nbatch-dynamic updates in parallel.\n\nBuilding on the zd-tree\, we also present the CLEANN-Tree (for\nConcurrent Linearizable E fficient Augmented Nearest Neighbor Search\nTree)\, a generalization of th e zd-tree which supports concurrent\nqueries and updates utilizing version ed pointers and lock-free locks.\nIn high dimensions\, we introduce techni ques to make existing nearest\nneighbor search algorithms lock-free\, dete rministic\, and scalable to\nbillion-size datasets. We apply these techniq ues to four existing\ngraph-based nearest neighbor search algorithms in a library called\nParlayANN. Building off our work in ParlayANN\, we extend the search\nalgorithms for graph-based nearest neighbor indices to the rel ated but\nrelatively under-studied problem of range search in high dimensi ons\,\nmaking significant gains over a naive baseline. \n\nThesis Committ ee\n\nGuy E. Blelloch (Chair)\n\nPhillip B. Gibbons\n\nAndrew Pavlo\n\nHar sha Vardhan Simhadri (Microsoft Azure)\n\nMatthijs Douze (Meta AI Research )\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676056647 DTSTART;TZID=America/New_York:20250409T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250409T140000 LOCATION:Gordon Bell Conference Room\, Gates Hillman 5117 SUMMARY:Doctoral Thesis Oral Defense - Eric Mark Sturzinger CLASS:PUBLIC DESCRIPTION:Speaker: ERIC MARK STURZINGER\, Ph.D. Candidate\, Computer Scie nce\nDepartment\, Carnegie Mellon University\n\nTalk Title: Survival-Criti cal Machine Learning\n\nAutonomous systems must be able to survive in adve rsarial or hostile\nenvironments where threats evolve and morph.  Under c onditions in\nwhich a class of adversarial agents is novel but rare\, thes e systems\nmust rapidly learn and adapt.  We introduce Survival-Critical Machine\nLearning (SCML)\, a new ML paradigm that defines how autonomous s ystems\nthat rely on machine learning can negotiate such adversarial\nenvi ronments.  Inspired by the ability of a biological entity's\nimmune syste m to develop defenses against new viruses\, SCML systems\nleverage the wor kflow of Live Learning to iteratively improve ML\nmodels for threat detect ion.\n\nBeyond the conceptualization of SCML\, the main contributions of t his\ndissertation are an analytical model\, a prototype implementation\, a nd\nexperimental results of the SCML design tradeoff space.  We evaluate\ nthe impact on survivability of the various design parameters and\ndemonst rate the intimate relationship between SCML and Live\nLearning.  Notably\ , we evaluate the impact of the availability of\nfinite countermeasures (C Ms)\, the CM deployment threshold\, the number\nof deployed systems\, and the average threat arrival rate\, among\nothers\, on the probability of su rvival of a given mission duration. \nAdditionally\, we model SCML as a M arkov Decision Process (MDP) to\ndemonstrate how it can be analyzed within existing\, well-understood ML\nframeworks such as MDPs and Reinforcement Learning (RL).\n\nOur experimental results confirm that learning can indee d improve\nsurvivability in an SCML system.  It further shows that the CM \ndeployment threshold and the number of available CMs have a\nsignificant impact on survivability.  Allowing flexibility in the CM\ndeployment thr eshold during the mission enhances such survivability\nunder most conditio ns.  Similarly\, Live Learning improves the\nprobability of mission succe ss by increasing the likelihood of\naccurately classifying actual threats (true positives) and decreasing\nthe likelihood of wasting CMs on non-thre ats (false positives).  By\ndefining an SCML MDP\, we also show how an SC ML system can optimally\nadjust its CM deployment threshold as a function of state\, defined by\nthe number of remaining CMs and the time until miss ion completion.\n\nThesis Committee\n\nMahadev Satyanarayanan (Chair)\n\nP admanabhan Pillai\n\nJeff Schneider\n\nRashmi Vinayak\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676056b0e DTSTART;TZID=America/New_York:20250331T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250331T160000 LOCATION:Gates Hillman 8102 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Mihir Kiran Bala CLASS:PUBLIC DESCRIPTION:Speaker: MIHIR KIRAN BALA\, Ph.D. Candidate\, Computer Science\ nDepartment\, Carnegie Mellon University\n\nTalk Title: Towards Fully-Auto nomous Ultra-Light Drones\n\nAutonomous drones have emerged as an exciting new technology which\ncould revolutionize infrastructure inspection\, mil itary\nreconnaissance\, and police surveillance. However\, the vast majori ty of\ntoday’s platforms are heavy\, costly\, and difficult to operate. This\nrestricts them from use in many mission settings\, such as in densel y\npopulated environments\, where government regulation forbids autonomous \noperation of heavy drones near people. Much of this weight comes from\nt he onboard compute resources required for these drones to run the\ncritica l computer vision algorithms that provide situational\nawareness. \n\nIn this thesis oral\, I show how autonomy can be induced on lightweight\ndron es using edge computing\, offloading high compute jobs to a\nnetwork-proxi mal server. I demonstrate how this technique can lead to\nautonomous aircr aft that fly much closer to the FAAs regulatory limits\nat acceptable perf ormance cost. I also reveal a new operating system\ndesigned to unify the disparate landscape of drones under a single\,\neasy-to-program API. I sho w how this can be leveraged to create\nheterogeneous collaborative drone s warms on commercial off-the-shelf\nhardware. \n\nThesis Committee\n\nMaha dev Satyanarayanan (Chair)\n\nDavid O’Hallaron\n\nJeff Schneider\n\nPadm anabhan Pillai\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676056f39 DTSTART;TZID=America/New_York:20250331T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250331T140000 LOCATION:Blelloch-Skees Conference Room\, Gates Hillman 8115 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Asher James Trockman CLASS:PUBLIC DESCRIPTION:Speaker: ASHER JAMES TROCKMAN\, Ph.D. Candidate\, Computer Scie nce\nDepartment\, Carnegie Mellon University\n\nTalk Title: Mimetic Initia lization for Deep Neural Networks\n\nWhile neural network weights are typi cally initialized randomly from\nunivariate distributions\, pre-trained we ights often have\nvisually-discernible multivariate structure. We propose a technique\ncalled \"mimetic initialization\" that aims to replicate su ch\nstructures when initializing convolutional networks (CNNs)\,\nTransfor mers\, and State Space Models (SSMs). For CNNs\, we handcraft a\nclass of multivariate Gaussian distributions to initialize filters for\ndepthwise c onvolutional layers\; for Transformers\, we initialize the\nquery and key weights for self-attention layers such that their\nproduct approximates th e identity\; and for SSMs\, we initialize layers\nto approximate simple li near attention. Mimetic initialization\nsubstantially reduces training t ime and increases final accuracy on\nvarious common small-scale benchmarks .  \n\nOur technique enables us to almost close the gap between untraine d and\npre-trained Vision Transformers on small datasets like CIFAR-10\,\n achieving up to a 6% gain in accuracy through initialization alone.\nFor c onvolutional networks like ConvMixer and ConvNeXt\, we observe\nimprovemen ts in accuracy and reductions in training time\, even when\nconvolutional filters are frozen (untrained) after initialization. For\nSSMs\, mimetic  initialization substantially improves generalization\nabilities on synth etic language tasks like copying and associative\nrecall. Overall\, our fi ndings suggest that the benefits of\npre-training can be separated into tw o components: serving as a good\ninitialization and storing transferable k nowledge\, with the former\nbeing simple enough to (at least partially) ca pture by hand in\nclosed-form.  \n\nThesis Committee\n\nZico Kolter (Cha ir)\n\nAlbert Gu\n\nAditi Raghunathan\n\nSébastien Bubeck (OpenAI)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760573fe DTSTART;TZID=America/New_York:20250319T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250319T160000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Adithya Abraham Philip CLASS:PUBLIC DESCRIPTION:Speaker: ADITHYA ABRAHAM PHILIP\, Ph.D. Candidate\, Computer Sc ience\nDepartment\, Carnegie Mellon University\n\nTalk Title: Accurately P arameterizing Internet Performance Testing for\nRealistic Evaluations\n\nT he performance of Internet services — be it file download\ncompletion ti mes\, video quality\, or lag-free video conferencing — is\nheavily influ enced by network parameters. These include the bottleneck\nbandwidth\, pac ket loss\, network delays\, and how fairly the bottleneck\nlink is shared with other services. However\, current techniques to\nevaluate service per formance display three major issues: (a) testing\npredominantly in setting s representing the \"edge\" of the Internet\, and\nnot the core\; (b) an o veremphasis on the role of Congestion Control\nAlgorithms (CCAs) in determ ining application performance\; (c) testing\nin settings that do not neces sarily reflect where congestion occurs on\nthe Internet today. The goal of this thesis is to improve the state of\nthe art in testing for a more rea listic evaluation of Internet service\nperformance. We achieve this by cha nging measurement methodology to\ntest in more diverse network conditions\ , evaluate deployed Internet\nservices as opposed to just their underlying CCAs\, and identify more\nrealistic network parameters for evaluations.  \n\nWe first examine the changes in CCA behavior when evaluated in\nsettin gs representing the core of the Internet as opposed to the edge.\nWe find that the change to core Internet speeds and flow counts\ndramatically alte rs fairness outcomes\, and challenges long-standing\nassumptions about CCA behavior. This highlights the need to run\nInternet evaluations in more d iverse settings. \n\nWe then build Prudentia\, an Internet fairness watch dog\, to understand\nhow fairly two Internet services can share a bottlene ck link. In\naddition to discovering extreme unfairness on the Internet to day\, we\ngain key insights into improving current testing methodology — (a)\nThe most and least fair services both use variants of the same CCA\, \nhighlighting the need to test services in addition to CCAs\; (b)\nnetwor k settings can drastically affect even service-level fairness\noutcomes\, necessitating their careful selection. \n\nIn the final part of this thes is\, we leverage end-to-end measurements\nfrom a leading video-streaming s ervice to identify the prevalent\nnetwork conditions experienced by its us ers. Based on these\nmeasurements\, we recommend guidelines for parameteri zing future\nInternet evaluations so that their results are more relevant and\nreliable indicators of real-world CCA and service performance. \n\nT hesis Committee\n\nJustine Sherry (Chair)\n\nSrinivasan Seshan\n\nTheophil us A. Benson\n\nRenata Teixeira (Netflix)\n\nIn Person and Zoom Participat ion.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605795a DTSTART;TZID=America/New_York:20250311T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20250311T173000 LOCATION:Newell-Simon 3305 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Ananya Ashish Joshi CLASS:PUBLIC DESCRIPTION:Speaker: ANANYA ASHISH JOSHI\, Ph.D. Candidate\, Computer Scien ce\nDepartment\, Carnegie Mellon University\n\nTalk Title: Event Monitorin g in Modern Public Health Data Streams\n\nGrowing volumes of public health -related data render standard\ntechniques for syndromic surveillance (desi gned for smaller data\nvolumes) obsolete. My thesis presents a practical a pproach for experts\nto monitor large-scale aggregate public health data. These novel big\ndata monitoring methods identify data corresponding to qu ality issues\nor changes in disease dynamics and are simple\, scalable\,\n generalizable\, and shown to be accurate in real-world settings based\non human-labeled data. When paired with custom user interfaces\, these\nmetho ds have led to a 53-fold increase in monitoring efficiency for\ndata exper ts at the Delphi Group at Carnegie Mellon University.\nExperts can now det ect over 200 noteworthy data issues from 15 million\nnew data points each week. The output of this thesis' monitoring\napproach can directly support public health surveillance\, especially\nat the state or national level\, and increase the utility of public\nhealth data modernization efforts for data-driven decision-making.  \n\nThesis Committee\n\nRoni Rosenfeld (C o-Chair)\n\nBryan Wilder (Co-Chair)\n\nRayid Ghani\n\nMatthew Biggerstaff (Centers for Disease Control and Prevention)\n\nIn Person and Zoom Partici pation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676057d59 DTSTART;TZID=America/New_York:20241202T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20241202T120000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Justin Alexander Whitehouse CLASS:PUBLIC DESCRIPTION:Speaker: JUSTIN ALEXANDER WHITEHOUSE\, Ph.D. Candidate \, Compu ter\nScience Department\, Carnegie Mellon University\n\nTalk Title: Modern Martingale Methods: Theory and Applications\n\nMartingale concentration i s at the heart of sequential statistical\ninference. Due to their time-uni form concentration of measure\nproperties\, martingales allow researchers to perform inference on\nhighly correlated data as it is adaptively collec ted over time. Many\nstate-of-the-art results in areas such as differentia l privacy\,\nmulti-armed bandit optimization\, causal inference\, and onli ne learning\nboil down to (a) finding an appropriate\, problem-dependent m artingale\nand (b) carefully bounding its growth. Despite the important ro les\nmartingales and time-uniform concentration of measure play in modern\ nstatistical tasks\, applications of martingale concentration are\ntypical ly ad-hoc. Often\, poorly chosen martingale concentration\ninequalities ar e applied\, which results in suboptimal\, even vacuous\nrates in sequentia l estimation problems. \n\nThe focus of this thesis is twofold. In the fi rst part of this thesis\,\nwe provide simple yet powerful frameworks for c onstructing\ntime-uniform martingale concentration inequalities in univari ate\,\nmultivariate\, and even sometimes infinite-dimensional settings. Th e\ninequalities contained herein can be applied to processes with both\nli ght-tailed and heavy-tailed increments\, and follow from simple\ngeometric arguments. The second part of this thesis is focused on\napplying marting ale methods and time-uniform martingale concentration\nto practically rele vant data science tasks. In particular\, we show\nthat\, by appropriately applying martingale concentration\, one can\nobtain salient improvements o ver the state-of-the-art in both\ndifferentially private machine learning and kernel bandit optimization\ntasks. In sum\, the hope is to give a read er a start to finish view of\nhow to derive and apply time-uniform marting ale concentration in\nmodern statistical research. \n\nThesis Committee\n \nZhiwei Steven Wu (Co-Chair)\n\nAaditya Ramdas (Co-Chair)\n\nAarti Singh\ n\nCsaba Szepesvari (University of Alberta)\n\nEmilie Kaufmann (Universit é de Lille)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676058242 DTSTART;TZID=America/New_York:20240923T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240923T140000 URL:https://csd.cmu.edu/calendar/doctoral-thesis-oral-defense-shuqi-dai LOCATION:Gates Hillman 8102 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Shuqi Dai CLASS:PUBLIC DESCRIPTION:Speaker: SHUQI DAI\, Ph.D. Candidate \, Computer Science Depart ment\,\nCarnegie Mellon University\n\nTalk Title: Towards Artificial Music ians: Empowering Individual Music\nExpression In Composition\, Performance \, and Synthesis Through Machine\nLearning\n\nRecent advances in music tec hnology and generative AI have\nrevolutionized music creation\, transformi ng how we interact with music\nin various aspects of life. However\, achie ving high musicality and\ncustomizing music to individual preferences rema in significant\nchallenges. This thesis addresses five fundamental proble ms in\ncurrent AI-driven music understanding and creation: (1) multimodal\ nmusic representation\, (2) highly complex and logical music structure\,\n (3) stylistic and personalization controls\, (4) data scarcity and\ncopyri ght\, and (5) ethical concerns. This work integrates music\ndomain knowle dge with machine learning to effectively overcome\nthese obstacles\, by focusing on a practical application: creating\nvirtual musicians or \"re-c reating\" existing musicians.\n\nFirst\, guided by music expertise\, I int roduce novel algorithms that\nanalyze music data to identify and explore p rinciples underlying music\nexpression\, with a focus on music repetition and structure hierarchy.\nNext\, these principles are applied across three levels of music\ncreation: symbolic composition\, expressive performance control\, and\naudio synthesis. For symbolic composition\, both statistica l machine\nlearning and deep learning techniques are employed to compose\n melodies\, harmonies\, and bass lines that imitate specific music styles\n given examples. Expressive performance control\, highly crucial in\nmusic creativity but often ignored\, is realized through diffusion\nmodels that generate timing\, pitch\, dynamics\, and singing techniques.\nAudio synthe sis is demonstrated through singing synthesis\, which\ninvolves generating vocals from scratch and transferring vocal\ntimbres\, including zero-shot and cross-domain synthesis and conversion\nof unseen speech reference. Th ese approaches converge to model music\nexpression across multimodal music representations.\n\nThis thesis emphasizes individual music preference an d stylistic\nmodeling\, offering various controls for composition\, perfor mance\, and\nsynthesis. In symbolic composition\, controls range from micr o-level\nelements such as rhythm patterns and melodic contour\, to macro-l evel\nfeatures like song style\, structure\, and harmony. In singing\nperf ormance and synthesis\, controls include language\, style genre\, and\nsin ging techniques\, with zero-shot capabilities to customize specific\nvocal timbres.\n\nExperiments validate the effectiveness of the models\, demons trating\ncompetitive performance to human music. Ethical and legal\nconcer ns are also discussed. Finally\, I highlight potential\napplications for advancing these technologies in areas like music\ntherapy\, education\, hu man-computer interactive performance systems\,\nand the development of wor ld music theory.\n\nThesis Committee\n\nRoger B. Dannenberg (Chair)\n\nChr is Donahue\n\nJunyan Zhu\n\nJulius O. Smith (Stanford University)\n\nGus G uangyu Xia (Mohamed bin Zayed University of Artificial\nIntelligence)\n\nI n Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b6760588a4 DTSTART;TZID=America/New_York:20240906T154500 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240906T174500 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-elisaweta-masserova LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Thesis Oral Defense - Elisaweta Masserova CLASS:PUBLIC DESCRIPTION:Speaker: ELISAWETA MASSEROVA\, Ph.D. Candidate\, Computer Scien ce\nDepartment\, Carnegie Mellon University\n\nTalk Title: Distributed Cry ptography as a Service\n\nToday’s world is undeniably data-driven. The e xplosion of the\nInternet has generated vast volumes of data\, and the adv ent of machine\nlearning has unlocked captivating applications that thrive on this\ndata. In such a world\, it is evident that the ability to store\ ,\ntransmit\, and process data securely is paramount. Distributing trust\n is one of the fundamental cryptographic principles that enable such\nsecur ity\, and it is at the core of key cryptographic tools such as\nmulti-part y computation (MPC) and randomness generation. As the demand\nfor secure a nd reliable cryptographic solutions grows\, there is\nincreasing interest in offering such distributed protocols as a\nservice. \n\nThese services are typically expected to run continuously for long\nperiods of time\, req uiring significant resource commitments from all\nparticipating parties. O ne approach to mitigate this issue is to\ndesign distributed cryptographic protocols that are stateless. With\nsuch protocols\, parties can contribu te to the execution of a\ndistributed cryptographic protocol by participat ing only for a short\ntime\, without committing to a long-term computation . \n\nIn this work\, we study such mostly stateless protocols. We start b y\nintroducing a blockchain-based MPC protocol which does not require\npar ties to be online at the same time and requires no interaction\nbetween th e participants. We construct this protocol in the blockchain\nmodel and un der the assumption of what we call Conditional Storage and\nRetrieval (CSa R) systems. In our next step\, we eliminate the CSaR\nrequirement and desi gn a stateless MPC protocol without relying on\nthis assumption. \n\nMore concretely\, we focus on the recently introduced You Only Speak\nOnce (YO SO) paradigm. In this model participating parties are allowed\nto send onl y a single message\; i.e.\, they speak only once. We improve\nthe state of the art in YOSO MPC by designing a protocol with better\ncommunication co mplexity than the currently known solutions. Then\, we\nfocus on improving the efficiency of special-purpose YOSO MPC\nprotocols. Specifically\, we consider the task of distributed\nrandomness generation\, and design a sui te of protocols\, each balancing\ndifferent trade-offs in terms of underly ing assumptions\, efficiency\,\nand corruption threshold.\n\nThesis Commit tee \n\nBryan Parno (Co-chair)\n\nVipul Goyal (Co-chair)\n\nElaine Shi\n\ nAntigoni Polychroniadou (J.P. Morgan AI Research)\n\nTal Rabin (Universit y of Pennsylvania  / Amazon Web Services)\n\nIn Person and Zoom Participa tion.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676058d97 DTSTART;TZID=America/New_York:20240823T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240823T140000 URL:https://csd.cmu.edu/calendar/doctoral-thesis-oral-defense-daniel-linkit -wong LOCATION:Panther Hollow Conference Room\, Mehrabian Collaborative Innovatio n\nCenter 4th Floor SUMMARY:Doctoral Thesis Oral Defense - Daniel Lin-Kit Wong CLASS:PUBLIC DESCRIPTION:Speaker: DANIEL LIN-KIT WONG\, Ph.D. Candidate\, Computer Scien ce\nDepartment\, Carnegie Mellon University\n\nTalk Title: Machine Learnin g for Flash Caching in Bulk Storage Systems\n\nFlash caches are used to re duce peak backend load for\nthroughput-constrained data center services\, reducing the total number\nof backend servers required. Bulk storage syst ems are a large-scale\nexample\, backed by high-capacity but low-throughpu t hard disks\, and\nuse flash caches to provide a cost-effective storage layer underlying\neverything from blobstores to data warehouses. \n\nHow ever\, flash caches must manage their limited write endurance and\nlimit  the flash write rate to avoid premature wear-out. They do so\nvia admissio n policies that filter cache insertions and maximize the\nworkload-reduct ion value of each write. \n\nI evaluate and demonstrate potential uses of ML in place of\ntraditional heuristic cache management policies for flas h caches in\nbulk storage systems. The most successful elements of my res earch are\nembodied in a flash cache system called Baleen\, which uses\nc oordinated ML admission and prefetching to reduce peak backend load.\nAft er learning painful lessons with early ML policy attempts\, I\nexploit a new cache residency model (episodes) to guide model\ntraining. I focus on optimizing an end-to-end metric (Disk-head Time)\nthat measures backend load more accurately than IO or byte miss rate.\nEvaluation using 7-day M eta traces from 7 storage clusters shows\nBaleen reducing Peak Disk-head Time (and backend hard disks required)\nby 12% over state-of-the-art poli cies for a fixed flash write rate. \n\nI present a TCO (total cost of ow nership) formula quantifying\nthe costs of additional flash writes agains t reductions in Peak\nDisk-head Time in terms of flash drives and hard di sks needed.\nBaleen-TCO chooses optimal flash write rates and reduces est imated\nTCO by 17%. \n\nWorkloads change over time\, requiring that cache s adapt to\nmaintain performance. I present a strategy for peak load\nred uction that adapts selectivity to load levels. I evaluated\nworkload drif t and its impact on ML policy performance on 30-day Meta\ntraces. \n\nBa leen is the result of substantial exploration and experimentation\nwith ML  for caching. I present lessons learned from additional\nstrategies consi dered and explain why they saw limited success on our\nworkloads. These  include improvements for ML eviction and more\nadvanced ML models. Code an d traces are available\n\nThesis Committee\n\nGregory R. Ganger (Chair)\n\ nNathan Beckmann\n\nDavid G. Andersen\n\nDaniel S. Berger (Microsoft Resea rch / University of Washington)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605928f DTSTART;TZID=America/New_York:20240822T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240822T170000 URL:https://csd.cmu.edu/calendar/doctoral-thesis-oral-defense-juncheng-yang LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Doctoral Thesis Oral Defense - Juncheng Yang CLASS:PUBLIC DESCRIPTION:Speaker: JUNCHENG YANG\, Ph.D. Candidate\, Computer Science Dep artment\,\nCarnegie Mellon University\n\nTalk Title: Designing Efficient a nd Scalable Cache Management Systems\n\nSoftware caches have been widely d eployed at scale in today's\ncomputing infrastructure to improve data acce ss latency and\nthroughput. These caches consume PBs of DRAM at many compa nies\, which\nnecessitates high efficiency --- achieving the same miss rat io with\nless DRAM consumption. Meanwhile\, modern servers have hundreds o f\ncores\, making scalability a critical requirement for designing\nsoftwa re caches. This thesis explores different approaches to\nimproving the eff iciency and scalability of software caches. \n\nThis thesis has two parts . The first part focuses on system designs\nthat allow caches to store mor e objects in the cache to achieve a low\nmiss ratio. In this part\, I will describe three works. First\, I will\ndiscuss what key-value cache worklo ads at Twitter look like using a\nlarge-scale workload analysis. Second\, drawing on insights from the\nworkload study\, I will describe the design of Segcache\, a TTL-indexed\nsegment-structured key-value cache that quick ly removes expired\nobjects\, provides tiny object metadata\, and enables close-to-linear\nscalability. Third\, I will present C2DN to demonstrate a \nfault-tolerant CDN cache cluster using erasure coding for low-overhead\n redundancy. \n\nThe second part focuses on algorithms that allow the cach e to store\nmore useful objects in the cache\, which is also critical for cache\nefficiency. First\, I will investigate the design of a low-overhead \nlearned cache. Existing caches using machine learning often incur\nsigni ficant storage and computation overheads. I will show that\nlearning on th e group level amortizes overheads and accumulates more\ninformation for be tter learning. While GL-Cache is faster than\nexisting learned caches\, it is still more complex compared to simple\nheuristics. In the following ch apter\, I will discuss two techniques\,\nlazy promotion and quick demotion \, which enable us to design simple\nyet effective eviction algorithms. In the third chapter\, I will\ndiscuss an example using the two techniques\, S3-FIFO\, a new eviction\nalgorithm only composed of FIFO queues. In the last chapter\, I will\npresent SIEVE\, a new eviction algorithm that uses one queue to achieve\nlazy promotion and quick demotion. SIEVE is simpler than LRU\, but\nachieves state-of-the-art efficiency and scalability.\n\nT hesis Committee: \n\nRashmi Vinayak (Chair)\n\nGreg Ganger\n\nPhillip Gib bons\n\nVijay Chidambaram (University of Texas at Austin)\n\nIon Stoica (U niversity of California\, Berkeley)\n\n \n\nn Person and Zoom Participati on.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605977c DTSTART;TZID=America/New_York:20240807T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240807T120000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-travis-hance LOCATION:Reddy Conference Room\, Gates HIllman 4405 and Zoom SUMMARY:Thesis Oral Defense - Travis Hance CLASS:PUBLIC DESCRIPTION:Speaker: TRAVIS HANCE\, Ph.D. Candidate\, Computer Science Depa rtment\,\nCarnegie Mellon University\n\nTalk Title: Verifying Concurrent S ystems Code\n\nConcurrent software is notoriously difficult to write corre ctly\, so to\nincrease confidence in it\, it is often desirable to apply f ormal\nverification techniques. One technique that is especially promising \nfor verifying concurrent software is concurrent separation logic\n(CSL)\ , which uses reasoning principles based on resource ownership.\nHowever\, even with CSL\, verifying complex systems at scale (e.g.\,\nthose with 100 0s of lines of code) remains challenging. The reasons it\nremains challeng ing include:\n\nThe manual proof effort required by many existing CSL fram eworks.The\ninherent complexity of the target systems. Sophisticated syste ms may\nhave custom\, low-level synchronization logic\, which may be deepl y\nintertwined with domain logic\, in the interest of performance.\n\nWe p osit that a promising way to overcome (1) is\, rather than using\nCSL dire ctly\, to use an ownership type system such as Rust's\, taking\nadvantage of its sophisticated but efficient type-checking algorithms.\nTo demonstra te this\, we develop a full methodology\, from theory to\nimplementation\, based around this core idea\, showing that we can\nrecover the rich reaso ning principles of CSL in this setting. In\nparticular\, we show that this methodology is rich enough to support\nthe verification of inherently com plex systems as in (2).\n\nThesis Committee:\n\nBryan Parno (Chair)\n\nDav e Andersen\n\nFrank Pfenning\n\nDerek Dreyer (Max Planck Institute for Sof tware Systems) \n\nIn Person and Zoom Participation.  See announcement.\ n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b676059bd5 DTSTART;TZID=America/New_York:20240731T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240731T170000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-mikhail-khodak SUMMARY:Thesis Oral Defense - Mikhail Khodak CLASS:PUBLIC DESCRIPTION:Speaker: MIKHAIL KHODAK\, Ph.D. Candidate\, Computer Science De partment\,\nCarnegie Mellon University\n\nTalk Title: The Learning of Algo rithms and Architectures\n\nHow should we design the algorithms we run and the architectures we\nlearn? Several high-impact areas of computing have begun to automate\nthese procedures using machine learning (ML)\, reducing the need for\nhuman effort by using our expanding amount of data and comp ute. We use\nideas from ML\, algorithm design\, and optimization to advanc e our\nunderstanding of these areas of data-driven computing—meta-learni ng\,\nalgorithms with predictions\, and architecture search—and to\ntran slate the resulting methodologies into state-of-the-art\nimplementations.\ n\nIn meta-learning\, which uses ML itself to improve ML algorithms by\nle arning across many learning tasks\, we introduce ARUBA\, a framework\nfor designing and analyzing meta-learning methods. Our analysis yields\nthe fi rst guarantees for gradient-based meta-learning\, showing how\nsuch method s improve performance based upon quantifiable measures of\nsimilarity betw een learning tasks. We use ARUBA to extend the\npractical impact of meta-l earning to new areas of ML\, including to\nlearning with partial feedback and to federated learning.We build upon\nthe success of ARUBA by taking it s core approach—the optimization of\nsurrogate loss functions approximat ing algorithmic objectives—and\nextending it beyond learning algorithms to show learning guarantees\nfor algorithms with predictions\, which are a lgorithms that take\nadvantage of learned predictions about their instance s\; in particular\,\nwe show the first learning-theoretic guarantees for p redictions that\ndepend on the instance the algorithm is run on\, a crucia l property for\npractical applications. We apply our framework while intro ducing\nalgorithms with predictions to new areas such as scientific comput ing\,\nwhere we design learning algorithms that\, under natural structural \nassumptions\, can learn to make instance-optimal predictions.Lastly\, we \naddress the problem of finding neural network architectures to train\non specific learning tasks\, or architecture search\, where we make\nprogres s towards understanding the optimization and generalization\nproperties of weight-sharing\, a dominant heuristic used throughout the\nfield. We then extend weight-sharing to design new search spaces based\naround neural op erations that allow for the automated discovery of\ntruly novel architectu res from data\; the culmination of this effort is\nDASH\, a method that ef ficiently finds architectures that outperform\nhuman expert-designed neura l architectures on the majority of diverse\ntasks we test.\n\nThesis Commi ttee:\n\nMaria-Florina Balcan (Co-Chair)\n\nAmeet Talwalkar (Co-Chair)\n\n Tom Mitchell\n\nPeter Bartlett (University of California\, Berkeley)\n\nPi otr Indyk (Massachusetts Institute of Technology)\n\nAlexander Smola (Boso n AI)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605a0a9 DTSTART;TZID=America/New_York:20240729T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240729T160000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-jatin-arora LOCATION:Gates Hillman 8102 and Zoom SUMMARY:Thesis Oral Defense - Jatin Arora CLASS:PUBLIC DESCRIPTION:Speaker: JATIN ARORA\, Ph.D. Candidate\, Computer Science Depar tment\,\nCarnegie Mellon University\n\nTalk Title: Provably Efficient Cosc heduling of Computation and Data\nthrough Disentanglement\n\nBecause of it s many desirable properties\, such as its ability to\ncontrol effects and thus potentially disastrous race conditions\,\nfunctional programming offe rs a viable approach to programming modern\nmulticore computers. This has  led to  the past decade several\nparallel functional languages\, typica lly based on dialects of ML and\nHaskell\, have been developed. These lang uages\, however\, have\ntraditionally underperformed compared to procedura l languages (such as\nC and Java).The primary reason for this underperform ance has been the\nlack of scalable memory management techniques capable of matching the\nincreased demand of memory in parallel execution.\n\nIn t his thesis\, we propose provably efficient techniques for memory\nmanageme nt of parallel functional programs. The key idea behind our\ntechniques is to coschedule the parallel computation with its data\,\nenabling the memo ry manager to exploit the disentanglement\nhypothesis---the idea that para llel tasks of a program largely execute\nindependently and avoid side-effe cting data that may be accessed by\nothers--for efficiency. We implement t hese techniques in the MPL\ncompiler for parallel ML and our experimental results show that the\ntechniques can marry the safety benefits of functio nal programming\nwith performance.\n\nThesis Committee:\n\nUmut A. Acar (C hair)\n\nGuy E. Blelloch\n\nRobert Harper\n\nRustan Leino (Amazon)\n\n \n \nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605a4d6 DTSTART;TZID=America/New_York:20240729T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240729T120000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-yue-niu LOCATION:Gates HIllman 8102 SUMMARY:Thesis Oral Defense - Yue Niu CLASS:PUBLIC DESCRIPTION:Speaker: YUE NIU\, Ph.D. Candidate\, Computer Science Departmen t\,\nCarnegie Mellon University\n\nTalk Title: Cost-sensitive Programming\ , Verification\, and Semantics\n\nComputational cost is a fundamental aspe ct of the behavior of computer\nprograms. However\, existing program verif ication techniques do not\nsimultaneously provide both faithful representa tion of cost structure\nand a way to reason about the pure functional mean ing of\ncost-instrumented programs. \n\nThis thesis introduces a logical framework for integrating\ncost-sensitive and functional program verificat ion and semantics by\nmeans of the internal modal type theory of presheaf categories\, an\napproach to programming language semantics first introduc ed by\nSterling and Harper in the context of program modules and data\nabs traction. I demonstrate that a range of common algorithms can be\nformulat ed and formally verified to meet both their functional and\ncost specifica tions within the framework. Lastly\, I extend the logical\nframework and u se it as a metalanguage for studying the cost semantics\nof programming la nguages\, culminating in an internal cost-sensitive\ncomputational adequac y theorem for PCF that relates the denotational\nand operational cost sema ntics in the style of Plotkin. \n\nThesis Committee: \n\nRobert Harper ( Chair)\n\nJan Hoffmann\n\nSteve Brookes\n\nJon Sterling (University of Cam bridge)\n\nNeel Krishnaswami (University of Cambridge)\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605a908 DTSTART;TZID=America/New_York:20240726T090000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240726T110000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-ranysha-ware LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Thesis Oral Defense - Ranysha Ware CLASS:PUBLIC DESCRIPTION:Speaker: RANYSHA WARE\, Ph.D. Candidate\, Computer Science Depa rtment\,\nCarnegie Mellon University\n\nTalk Title: Battle for Bandwidth: On The Deployability of New\nCongestion Control Algorithms\n\nThe Internet has become the central source of information and\ncommunication in modern society. Congestion control algorithms (CCAs)\nare critical for the stabi lity of the Internet: ensuring that users\nare able to fairly and efficien tly share the network. Over the past 30\nyears\, researchers and Internet content providers have proposed and\ndeployed dozens of new CCAs designed to keep up with the growing\ndemands of faster networks\, diverse applicat ions\, and mobile users.\nWithout tools to understand this growing heterog eneity in CCAs\ndeployed in the Internet\, the fairness of the Internet is at stake.\n\nTowards understanding this growing heterogeneity\, we develo p\nCCAnalyzer\, a tool to determine what CCA a particular web service\ndep loys\, outperforming previous classifiers in accuracy and\nefficiency. Wit h CCAnalyzer\, we show that new CCAs\, both known and\nunknown\, have wide spread deployment in the Internet today\, including a\nrecently proposed C CA by Google: BBRv1. Next\, we develop the first\nmodel of BBRv1\, and pro ve BBRv1 can be very unfair to legacy\nloss-based CCAs\, an alarming findi ng given the prolific deployment of\nBBRv1.\n\nConsequently\, we argue the need for a better methodology for\ndetermining if a new CCA is safe to de ploy in the Internet today. We\ndescribe how the typical methodology testi ng for equal-rate fairness\n(every user gets the same bandwidth) is both a n unachievable goal and\nultimately\, not the right threshold for determin ing if a new CCA is\nsafe to deploy alongside others. Instead of equal-rat e fairness\, we\npropose a new metric we call\, harm\, and argue for a har m-based\nthreshold. Lastly we present RayGen\, a novel framework for evalu ating\ninteractions between heterogeneous CCAs. RayGen uses a genetic\nalg orithm to efficiently explore the large state space of possible\nworkloads and network settings when two CCAs compete. With a small\nbudget of exper iments\, RayGen finds more harmful scenarios than a\nparameter sweep and r andom search.\n\nThesis Committee: \n\nJustine Sherry (Co-Chair)\n\nSrini vasan Seshan (Co-Chair)\n\nTheophilus A. Benson\n\nJim Kurose (University of Massachusetts Amherst)\n\n \n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605ae44 DTSTART;TZID=America/New_York:20240719T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240719T160000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-jenny-lin LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Thesis Oral Defense - Jenny Lin CLASS:PUBLIC DESCRIPTION:Speaker: JENNY LIN\, Ph.D. Candidate\, Computer Science Departm ent\,\nCarnegie Mellon University\n\nTalk Title: Formalizing Object Equiva lence in Machine Knitting\n\nCorrectness is a desirable property for any p rogram\, whether that\nprogram computes an equation\, controls a machine\, or interprets data.\nDefining what it means for a program to be correct c an be surprisingly\nnuanced\, however\, especially when that program is us ed to create a\nphysical object. We can reframe this problem by treating c orrectness\nas a question of equivalence. Given some target object\, is th e result\nof a fabrication process equivalent to the target object? Howeve r\,\nthis now requires that we answer the still complicated question of\nw hat it means for two objects to be equivalent. In order to do so\, we\nnot only need a precise definition of object meaning\, but also a\nstrong und erstanding of how we create and interact with the objects\naround us. \n\ nIn this thesis I tackle this problem of meaning and equivalence for\nmach ine knitting programs. Knitting is the act of taking a few strands\nof yar n and deforming them into interlocking loops forming a stable\nstructure. While knitting machines are capable of quickly fabricating\na vast array o f structures with controllable material properties\, the\ncomplexity of bo th the machine control process and the resulting\nphysical object makes tr anslating between the two incredibly\ndifficult. This gap prevents existin g programing and design tools from\naccessing the full breadth of its fabr ication possibilities. \n\nTo address this\, I formally characterize the complete space of machine\nknitting programming. I begin by introducing fe nced tangles\, a novel\nmathematical object designed to match intuition ab out knit object\nmeaning\, to define semantics for Knitout\, which is a lo w-level\nlanguage for controlling v-bed knitting machines. The underlying\ nprogram meaning is then used to reason about the correctness of a set\nof practical program transformations. This semantic function is used\nas gui dance for developing Instruction Graphs\, which are an\nintermediate repre sentation of knit objects. Unlike existing knit\nobject representations\, Instruction Graphs can capture the full range\nof machine knittable object s and can be verified as machine knittable\nusing three easy to check grap h embedding properties. Finally\, I\ndiscuss how fabrication constraints m ay enable an algebraic approach\nto computing machine knitting program equ ivalence.   \n\nThesis Committee:\n\nJames McCann (Chair)\n\nJan Hoffma nn\n\nScott Hudson\n\nAdriana Schulz (University of Washington)\n\nIn Pers on and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605b39b DTSTART;TZID=America/New_York:20240718T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240718T160000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-shiva-kaul LOCATION:Mauldin Auditorium\, Newell-Simon 1305 SUMMARY:Thesis Oral Defense - Shiva Kaul CLASS:PUBLIC DESCRIPTION:Speaker: SHIVA KAUL\, Ph.D. Candidate\, Computer Science Depart ment\,\nCarnegie Mellon University\n\nTalk Title: Classical Improvements t o Modern Machine Learning\n\nThe following two dilemmas of modern foundati on models concern\nstatistical accuracy and computational efficiency\, res pectively:\n\nCan language models be trusted to rigorously answer importan t\nscientific questions? (Specifically\, causal questions from\nevidence-b ased medicine which are currently answered through\nmeta-analysis)Can Tran sformers and RNNs be replaced by faster\nstate-space models (which are lin ear across time / sequence length)\nwithout sacrificing expressive power?\ n\nI present solutions to both. For (1)\, I adapt conformal prediction to\ nmeta-analysis\, which may be thought of as a regression from treatment\na nd population features (e.g. \"800mg of amiodarone for atrial\nfibrillatio n patients\") to treatment effect (e.g. \"60% chance of\nreversion to norm al heart rhythm\"). By using conformal prediction to\nsafely incorporate u ntrusted data (i.e. observational studies and\nother background informatio n)\, this complex regression problem can be\nsatisfactorily addressed even with a small number of randomized\ncontrolled trials. The main technical challenges are computationally\nsimplifying full conformal prediction (whi ch is necessary due to the\nsmall number of trials) and handling noisy obs ervations (due to the\nlimited number of participants in each trial). \n\ nFor (2)\, I present a general scheme by which nonlinearity across time\nc an be replaced by nonlinearity along depth. This involves stacking\nlinear systems with interposed local corrections. This scheme is fast\,\nconstru ctive\, involves no additional parameters\, provably converges\neven in th e worst case\, and empirically exhibits fast convergence. It\ncan be used to practically develop fast sequence models and to\ntheoretically understa nd the power of depth. \n\nBoth of these solutions exemplify a broader th esis of developing\nsyntheses between classical machine learning technique s (such as\nmeta-analytic averaging or linear dynamical systems) and moder n\napproaches (such as deep nonlinear regression or Transformers). The\nhi gh-level goal is to combine the safety and tractability of classical\nappr oaches with the accuracy of modern ones through a close (and\nsometimes su rprising) examination of their technical relationship. \n\nThesis Committ ee: \n\nGeoffrey Gordon (Chair)\n\nZachary Lipton\n\nAditi Raghunathan\n\ nRyan Tibshirani (University of California\, Berkeley)\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605b8e4 DTSTART;TZID=America/New_York:20240715T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240715T170000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-haithem-turki LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Thesis Oral Defense - Haithem Turki CLASS:PUBLIC DESCRIPTION:Speaker: HAITHEM TURKI\, Ph.D. Candidate\, Computer Science Dep artment\,\nCarnegie Mellon University\n\nTalk Title: Towards City-Scale Ne ural Rendering\n\nAdvances in neural rendering techniques have led to sign ificant\nprogress towards photo-realistic novel view synthesis. When combi ned\nwith increases in data processing and compute capability\, this\nprom ises to unlock numerous VR applications\, including virtual\ntelepresence\ , search and rescue\, and autonomous driving. Large-scale\nvirtual reality \, long the domain of science fiction\, feels markedly\nmore tangible. \n \nThis thesis explores the frontier of large-scale neural rendering by\nbu ilding upon Neural Radiance Fields (NeRFs)\, a family of methods\nattracti ng attention due to their state-of-the-art rendering quality\nand conceptu al simplicity. Since its inception\, at least 3\,000 papers\nhave been pro posed in less than three years by research groups across\nthe world across numerous use cases. However\, many shortcomings\nremain. The first is sca le itself. Only a handful of existing methods\ncapture scenes larger than a room. Those that do only handle static\nreconstruction\, which limits th eir applicability. Another is speed\, as\nrendering falls below interactiv e thresholds. Current acceleration\nmethods remain too slow or degrade qua lity at high resolution. Quality\nis a third issue\, as NeRF assumes ideal viewpoint conditions that are\nunrealistic in practice and degrades when they are violated. \n\nWe first explore scaling within the context of sta tic reconstruction.\nWe design a sparse network structure that specializes parameters to\ndifferent regions of the scene that can be trained in para llel\,\nallowing us to scale linearly as we increase model capacity (vs\nq uadratically in the original NeRF)\, and reconstruct urban-scale\nenvironm ents orders of magnitude larger than prior work. We then\naddress dynamic reconstruction of entire cities\, and build the largest\ndynamic NeRF repr esentation to date. To accelerate rendering\, we\nimprove sampling efficie ncy through a hybrid surface-volume\nrepresentation that encourages the mo del to represent as much of the\nworld as possible through surfaces (which require few samples per ray)\nwhile maintaining the freedom to render tra nsparency and finer details\n(which pure surface representations struggle to capture). We finally\npropose a fast anti-aliasing method that greatly improves rendering\nquality when training with data collected from freefor m camera\ntrajectories. Importantly\, our method incurs a minimal performa nce\noverhead and is compatible with the scale and speed improvements\npre viously mentioned.\n\nThesis Committee:\n\nDeva Ramanan (Chair)\n\nShubham Tulsiani\n\nJessica K. Hodgins\n\nMartial Hebert\n\nJonathan T. Barron (G oogle DeepMind)\n\nIn Person and Zoom Participation.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605be53 DTSTART;TZID=America/New_York:20240701T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240701T130000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-peter-manohar LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Thesis Oral Defense - Peter Manohar CLASS:PUBLIC DESCRIPTION:Speaker: PETER MANOHAR\, Ph.D. Candidate\, Computer Science Dep artment\,\nCarnegie Mellon University\n\nTalk Title: New Spectral Techniqu es in Algorithms\, Combinatorics\, and\nCoding Theory: The Kikuchi Matrix Method\n\nIn this thesis\, we present a new method to solve algorithmic an d\ncombinatorial problems by (1) reducing them to bounding the maximum\,\n over x in {-1\,1}n\, of homogeneous degree-q multilinear polynomials\,\nan d then (2) bounding the maximum value attained by these polynomials\nby an alyzing the spectral properties of appropriately chosen induced\nsubgraphs of Cayley graphs on the hypercube (and related variants)\ncalled \"Kikuch i matrices\". We will present the following applications\nof this method.\ n\nDesigning algorithms for refuting/solving semirandom and smoothed\ninst ances of constraint satisfaction problems\;Proving Feige's\nconjectured hy pergraph Moore bound on the extremal girth vs. density\ntrade-off for hype rgraphs\;Proving a cubic lower bound for 3-query\nlocally decodable codes and an exponential lower bound for 3-query\nlocally correctable codes.\n\n Thesis Committee: \n\nVenkatesan Guruswami (Co-Chair\, Carnegie Mellon Un iversity /\nUniversity of California\, Berkeley)\n\nPravesh K. Kothari (Co -Chair\, Carnegie Mellon University / Princeton\nUniversity)\n\nRyan O’D onnell\n\nUriel Feige (Weizmann Institute)\n\nIn Person and Zoom Participa tion.  See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605c27d DTSTART;TZID=America/New_York:20240628T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240628T160000 URL:https://csd.cmu.edu/calendar/thesis-oral-defense-david-kahn LOCATION:Mauldin Auditorium\, Newell-Simon 1305 SUMMARY:Thesis Oral Defense - David Kahn CLASS:PUBLIC DESCRIPTION:Speaker: DAVID KAHN\, Ph.D. Candidate\, Computer Science Depart ment\,\nCarnegie Mellon University\n\nTalk Title: Leveraging Linearity to Improve Automatic Amortized\nResource Analysis\n\nAfter correctness\, the most important properties of programs concern\ntheir resource requirements \, like how much time they take to run or\nhow much memory they need. It i s therefore desirable to automate the\nderivation of a program’s costs. One successful approach to such\nautomatic derivation is the type system k nown as Automatic Amortized\nResource Analysis (AARA). AARA finds polynomi al bounds on resource\nusage by using its types to apply the physicist’s method of\namortized cost analysis. Type inference in AARA can be reduced to\nlinear programming\, thereby automating resource analysis. This balan ce\nof expressive bounds and efficient analysis has brought AARA success.\ n\nUnfortunately\, deriving a program’s resource usage can be difficult\ n— in fact it is generally not computable. Thus\, despite AARA’s\nsucc ess\, it is not surprising that there are many natural program\npatterns t hat it cannot analyze well. Sometimes AARA finds loose\nresource bounds\, other times it finds bounds slowly\, and sometimes it\ncannot find any bou nds at all. \n\nThis thesis addresses such shortcomings by developing a v ariety of\nupgrades to the AARA type system that allow the efficient deriv ation\nof tight resource bounds for more programs. The key theme underlyin g\nthese upgrades is the leveraging of linear reasoning principles. These\ nideas integrate well with AARA because AARA exists in the intersection\no f various forms of linearity: the linear flavor its type system\, the\nlin ear relations of its cost bound templates\, and the linear\nphysicality be hind the physicist’s method of amortized cost\nanalysis.\n\nThis work fi rst upgrades the type system with remainder contexts to\nbetter reason abo ut reusable resources like memory. Then the class of\nAARA’s bounding fu nctions is enlarged to include\, e.g.\, exponential\nbounds. This class of functions is further enlarged to be\nmultivariate\, allowing dependence o n products of data structure sizes.\nNext\, this work provides a more effi cient\, matrix-based approach to\ninferring the cost-free AARA types neede d for\, e.g.\, non-tail\nrecursion. Finally the physicist’s method of am ortized cost analysis\nis refined into the quantum physicist’s method\, which provides an\nautomatable framework for reasoning about resource real location\, while\nalso allowing resource bounds to depend on data structur e height. \n\nThesis Committee:\n\nJan Hoffmann (Chair)\n\nFrank Pfenning \n\nStephanie Balzer\n\nThomas Reps (University of Wisconsin)\n\nIn Person and Zoom Participation. See announcement.\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605c7cc DTSTART;TZID=America/New_York:20240613T160000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240613T180000 URL:https://csd.cmu.edu/calendar/thesis-oral-DERY-2024-06-13 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Thesis Oral Defense - Lucio Mwinmaarong Dery CLASS:PUBLIC DESCRIPTION:Speaker: LUCIO MWINMAARONG DERY\, Ph.D. Candidate\, Computer Sc ience\nDepartment\, Carnegie Mellon University\n\nTalk Title: On Resource Efficient Transfer Learning via End Task Aware\nTraining\n\nIn Transfer le arning\, performance on a desired end task (or tasks) is\nimproved by expl oiting \"knowledge\" from other tasks. The technique has\nbecome a critica l workhorse driving many of the advances in machine\nlearning. The current formula is relatively simple -- train a large\nmodel on large amounts of data from the transfer task(s)\; then apply\nthe learned model either zero -shot or adapted to the desired\ndownstream task(s). \n\nThis thesis reco gnizes that these powerful models are not developed\nin-vacuo but rather r equire non-trivial resources to train and deploy.\nAs such\, there are a w ide range of salient problems and communities of\nresearchers that the sta tus-quo leaves behind. In the first part of\nthis thesis\, we will focus o n the training time problem of\ndata-efficient transfer learning. We will begin by making a case for\nexploiting advanced knowledge of the desired d ownstream task(s) —\nwhich is commonly the case in many ML settings — to inform different\ndimensions of transfer learning. We dub this end task aware transfer\nlearning. Next\, we will present a set of novel end task aware\noptimization algorithms that bias the learning trajectory towards\n data-efficient solutions with strong generalization on the end task.\nWe w ill close this part by providing an automated approach to\nconstructing an d searching over task-relevant transfer objectives when\nonly end task dat a is available and in limited amounts. \n\nWe will proceed to develop alg orithms for compute and memory efficient\ntransfer learning. Our goal will be to deliver a small and efficient\nyet performant task specific model f or deployment seeded from a large\,\ngeneralist model that has already bee n pre-trained on a transfer task\n(or set of tasks). Focusing on structure d pruning for making models\nsmaller\, we will investigate pruning under t wo resource constrained\nsettings:\n\nlimited task data\, where we will ex ploit extra transfer tasks to learn\npruning structures that\, at the same task performance\, lead to more\ncompute and memory efficient modelssetti ngs of limited memory\, where\nmany of the classical pruning techniques br eak down because they\nrequire gradient-based optimization which can have prohibitive memory\noverhead.\n\nThesis Committee: \n\nGraham Neubig (Co- Chair)\n\nAmeet Talwalkar (Co-Chair)\n\nZico Kolter\n\nLuke Zettlemoyer (U niversity of Washington / Meta)\n\nMarc'Aurelio Ranzato  (Google DeepMind )\n\nIn Person and Zoom Participation. See announcement.\n\nMeeting ID:  797 670 0891\n\nPasscode:  ldm-thesis\n DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605cd14 DTSTART;TZID=America/New_York:20240605T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240605T120000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 SUMMARY:Thesis Oral Defense - Dravyansh Sharma CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605ceee DTSTART;TZID=America/New_York:20240530T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240530T170000 LOCATION:Reddy Conference Room\, Gates HIllman 4405 and Zoom SUMMARY:Thesis Oral Defense - Praneeth Kacham CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d083 DTSTART;TZID=America/New_York:20240506T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240506T170000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d220 DTSTART;TZID=America/New_York:20240503T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240503T120000 LOCATION:McWilliams Classroom\, Gates Hillman 4303 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d3b5 DTSTART;TZID=America/New_York:20240502T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240502T170000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d516 DTSTART;TZID=America/New_York:20240501T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240501T160000 LOCATION:Gordon Bell Conference Room\, Gates Hillman 5117 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d6aa DTSTART;TZID=America/New_York:20240501T133000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240501T153000 LOCATION:McWilliams Classroom\, Gates HIllman 4303 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d81e DTSTART;TZID=America/New_York:20240430T133000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240430T153000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 and ZOom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605d9f4 DTSTART;TZID=America/New_York:20240426T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240426T170000 LOCATION:Newell-Simon Hall 3002 SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605db89 DTSTART;TZID=America/New_York:20240424T160000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240424T180000 LOCATION:Gates Hillman 8102 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605dcfd DTSTART;TZID=America/New_York:20240422T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240422T120000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605de82 DTSTART;TZID=America/New_York:20240416T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240416T140000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605dfff DTSTART;TZID=America/New_York:20240415T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240415T140000 LOCATION:Reddy Conference Room\, Gates Hillman 4405 SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605e17e DTSTART;TZID=America/New_York:20240411T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240411T170000 LOCATION:ASA Conference Room\, Gates Hillman 6115 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605e2f1 DTSTART;TZID=America/New_York:20240405T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240405T113000 LOCATION:Traffic21 Classroom\, Gates Hillman 6501 and Zoom SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT BEGIN:VEVENT UID:6a5b67605e478 DTSTART;TZID=America/New_York:20240403T160000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/New_York:20240403T180000 LOCATION:Gates and HIllman Centers SUMMARY:Computer Science Thesis Oral CLASS:PUBLIC DTSTAMP:20260718T114536Z END:VEVENT END:VCALENDAR