Recordings
Past Proceedings
2016
Keynote: Classification Trees for Determining Mood Affiliation of Males with Androgenic Alopecia
Michal Grzadkowski
Optimistic Fault Tolerance
Shoumik Palkar, Akshay Narayan, and Paroma Varma
Traditionally, fault tolerance has been
considered a pivotal component of system design. However, as modern
commodity hardware becomes increasingly reliable, building dedicated
fault tolerance systems becomes unnecessary. Therefore, while in this
paper we propose nothing novel and make no technical contributions, we
nevertheless identify a unique approach to fault tolerance, which we dub
optimistic fault tolerance. We implement optimistic fault tolerance, or
OFT, as a framework implemented as a C library which supports seamless
interoperability with any large scale system. We provide a survey of
real systems that demonstrates the rarity of system failure, and
additionally show through benchmarks and simulation that across numerous
workloads, our framework provides tolerance in the face of rare
arbitrary failures.
Evident Logic
Ben Sherman
Many logical systems justify their
consistency via proofs of cut elimination or normalization. However,
these metatheoretic proofs inevitably use a transfinite induction which
cannot be proved well-founded within the system itself. We present
evident logic, a logical system with a normalization proof which does
not require any induction that is stronger than what is available within
the logical system itself. Via the Curry-Howard correspondence, this
system may also be viewed a programming language for very efficient
computations. We provide a typechecker and normalizer within Coq; all
programs normalize in time constant with respect to their length. We
discuss the potential advantages of working with weak foundations.
Falso: a simple, self-consistent logic
A. Amarilli, T. Bourgeat, and B. Sherman
Conventional wisdom states that according
to Gödel's incompleteness theorem, any consistent logical system which
subsumes Peano arithmetic cannot prove its own consistency. However,
Falso, a powerful higher-order logical framework, shows that this is not
the case: Falso proves itself consistent, and this consistency proof,
of course, tells us that Falso is consistent. Falso is also complete:
every proposition can be proved or refuted. We use the Estatis Inc.
HyperProver and HyperVerifier, which implements a complete decision
procedure for Falso, to resolve several prominent open problems in
theoretical computer science.
A Polynomial Time Solution for 2-SAT
Will Leiserson
The question of whether the P and NP
complexity classes are equivalent is unresolved. It is conjectured that
they are inequivalent because of the vast number of NP-Complete
languages (including the ever-popular 3-SAT) for which there is no known
polynomial time solution. The author of this paper respectfully
disagrees and presents a polynomial time solution to a problem closely
related to 3-SAT: 2-SAT.
Solving the Dating Problem with the SENPAI Protocol
S. Dukhovni, J. Weisblat, and I. Chung
The Dating Problem is an extremely
difficult computational problem that has plagued humanity since time
immemorial. The problem concerns two agents Alice and Bob (or Alex and
Bob, or Alice and Beatrice), each of whom may or may not have a crush on
the other. Each is initially unaware of the other's feelings, and if
they have a crush, they would like to know whether the other does as
well; however, each would like to reveal their crush only if the other
shares the interest. This problem is of widespread interest and
applicability; for example, a solution to the Dating Problem is a
hitherto unremarked-on prerequisite for the Stable Marriage Algorithm.
How [verb, gerund] the [noun] affects the [adjective] [property] of [proper noun] [collection, plural].
M. Coulombe and P. Vasudevan
Word Blanks is a game in which one player
has as input a secret paragraph with some words replaced with blanks
with part-of- speech tags, such as [plural noun], and the other player
has as input the experience of being human for long enough to understand
parts-of-speech. The first player queries the other player with
part-of-speech tags and receives words to put in the corresponding
blanks. The goal of Word Blanks is to maximize the humor of the
resulting paragraph. First, we collected data from a representative
population of 11 theoretical computer science grad students as the
second player in the game, then chose 5 filled paragraphs and asked 20
computer science grad students which of a pair was funnier given the
order they were presented. Second, we took our data and used a logistic
regression model to learn which paragraph in any ordered pair is more
humorous, and applied the model to the other filled paragraphs. Our
results are that humor dominance is a strict partial order, and that the
second paragraph presented is usually the most humorous.
Locally Bijective, Non-Noetherian, Ultra-Liouville Random Variables and Parabolic Lie Theory
S. Park, M. Cohen, D. Tsipras, and G. Ramnarayan
Let ${\iota^{(\mathfrak{{a}})}} \ge e$. In
\cite{cite:0}, the authors address the degeneracy of compactly
intrinsic algebras under the additional assumption that $u$ is not
greater than $\mathscr{{Q}}$. We show that $\bar{\mathbf{{f}}} =
\infty$. Now the groundbreaking work of K. Zhou on anti-composite hulls
was a major advance. It is essential to consider that $D'$ may be
commutative. We extend this to the most general case. In the process, we
discover novel tools for analyzing pseudo-elliptic operators on dense
schemes of the $9.52$-dimensional lens space. We also point to some
possible connections to deep learning.
PERSHING: An Automatic Place-and-Route Tool for Minecraft Redstone Circuits
Quan Nguyen
In Minecraft, circuits can be assembled
from redstone components. We introduce PERSHING, a place and route tool
that can transform a gate-level netlist into logic gates built of
redstone in Minecraft, without the need for external Minecraft mods. We
discuss challenges, such as vertical signal transmission, and the
algorithms used to perform placement and routing. We show preliminary
results, including completed layouts, note future paths to explore, and
conclude.
A Data Driven Analysis Framework and Erotica Writing Assistant
Sara Achour
Since the advent of the internet, there
have been an increasing numbers user-curated pornographic fanfiction and
erotic narratives. With the rising popularity of erotic fiction on
digital book readers and on the silver and movie screens, the corpus of
erotica is an increasingly valuable and fascinating, dataset. We present
(1) \tx{xxxwriter}, an erotica writing assistant (2) \tx{tagmage}, a
tag suggestion engine and (3) \tx{triplex}, an erotic fiction dataset.
We additionally perform a detailed analysis of trends in both the
metadata and prose present in the \tx{triplex} dataset.
50,000,000,000 Instructions Per Second : Design and Implementation of a 256-Core BrainFuck Computer
S. Jun
This paper describes the design and
implementation of a machine for servicing a large number of BrainFuck
execution instances. The design includes the BrainFuck manycore
processor and the soft- ware daemon that manages the execution instances
on the proces- sor. The BrainFuck manycore processor is a 256 core
processor implementing a slightly modified version of BrainFuck as its
ISA. Each core is implemented with a two stage pipeline with a carefully
designed ISA encoding operating on disjoint memory spaces. Each core
achieves over 0.8 instructions per cycle. We have implemented our design
with an x86 host server and a Xilix Vertex 7 FPGA, and achieved an
agglomerate performance over 50 billion instructions per second, which
is light years ahead of what any single general purpose processor is
capable of achieving while executing Brain- Fuck code. The BrainFuck
computer is an attractive solution for servicing high throughput
BrainFuck cloud services, both in terms of performance and cost.
2017
OneHunnit: Exactly One Hundred Megabytes of Academic Work [PDF 100M]
Ilia Lebedev
With OneHunnit, this manuscript introduces
a novel body of inherently useful scientific work totaling precisely
one hundred megabytes (100MB) in size, working under an assumption of an
ISO 32000-1 (PDF) manuscript, submitted via an Apache-hosted HotCRP
(Hot Crap) content management system. The methodology used to obtain
this result generalizes easily, allowing for manuscripts of arbitrary
file size, with a minimum of $u_{doc}$ - the minimum achievable file
size of the desired manuscript, where $u_{doc}$ is small (but highly
variable and dependent on the document content). This work includes a
thorough evaluation of OneHunnit, and discusses several alternate
approaches to the task of increasing manuscript file size.
Stochastic Caching for Read Optimized Eventually Consistent Datastores
Jonathan Behrens
In this work we describe a new cache
mechanism to radically improve read performance of an eventually
consistent database without sacrificing consistency guarantees and
actually resulting in improved availability. Our system scales
quadratically in the number of nodes and can support many hundreds of
concurrent connections. Early results also suggest that bandwidth
utilization is competitive with existing solutions and aligned to the
capabilities of existing 2G cellular networks.
Locality Insensitive Hashing: Towards Ignoring the Curse of Dimensionality
D. Blalock and Bruce Wayne
The task of retrieving points from a
collection based on a query is foundational in machine learning and data
mining. Almost all existing work focuses on retrieving points that are
similar to the query under some similarity or distance measure. However,
virtually no work has been done on retrieving points that have little
or nothing to do with the query.
BurgerMax Presents: Open Adcess
Brett Boston and Max Dunitz
In this paper we examine an alternate
funding model for open access papers. Through modest modifications to
the ACM Digital Library and the addition of paper sponsorships we can
make the entire corpus of ACM works free to the public. We also peer
into a chilling future that only we can prevent. Will we stop the ACM
from encroaching on our everyday freedoms? Continue existing and
participating in reality to find out!
Fortune Cookies as a Source of Entropy - A Qualitative Analysis
E. Rahn
Abstract Entropy, as used in computing, is
a source of random information collected from various sources. This
randomness is subject to various measurements of quality and is a
measurable resource that can be depleted by using it up. Coming up with
sources of high quality entropy under non-standard circumstances is a
research question of interest within the security community. This paper
explores an unconventional source of entropy; the usage of so-called
”lucky numbers” on fortune cookies as a source of entropy. Studies are
conducted on both the cost of this source compared to more conventional
sources as well as the quality of random numbers generated.
A Pizza My Mind
W. Boag and A. Larochelle
Alfredo's Italian Kitchen. Brothers Pizza.
Papa Gino's. ABC Pizza. What do these all have in common? They are
pizza stores. For whatever reason, the phrase "pizza store'' seems to
inspire such vitrol among my so-called "friends''. "That's not a real
phrase'' they always snidely remark. Oh yeah? Well I'm the one with a
3.8-billion-word dump of English Wikipedia! I decided to run some
experiments to see just how "not a thing'' my very normal phrase is. How
frequently did a few common pizza phrases occur? My experiments suggest
that although synonymous phrases might be modestly more popular, many
of the acceptable phrases are all within the same order of magnitude. In
addition, a popular internet search engine does an arguably better job
with understanding "pizza store' than it does "pizza place''. In other
words, my friends are jerks.
Optimum Space Complexity Lower Bound Achieved by Quantum Pong Circuit
Michael Coulombe
Fantasy Football is America's favorite
pretend pastime. Friend groups of all varieties play , though we all
have that asshole friend Jason that never sets his lineup. It is
interesting that although most fantasy football platforms allow for
computer-aided "auto-draft", there is little-to-no support for
"auto-manage my entire team all season." Such a notion -- bots playing
fantasy -- is a great idea, and I'll tell you why. One can create an
entire league of bots playing against one another using different
policies. In fact, why stop at one league? Let's create thousands of
leagues of bots, and then draft those bots. It'll feel just like we're
playing fantasy football, but without all of the undesirable overhead;
we'll be playing *fantasy* fantasy football!
2018
Incremental Improvements on the Placement and Routing of Minecraft Redstone Circuits
Quan Nguyen
We present Dewey, the successor to the
PERSHING place-and-route tool for Minecraft Redstone circuits. As a
performance-oriented rewriting of PERSHING from the ground-up in C,
Dewey implements greatly improved routines for standard cell placement
and routing, and leaks a ton of memory. However, we materialize a
speedup of up to 34.0x over previous work. Dewey shows tremendous
strides towards the placement and routing of entire computer processors
in Minecraft.
PolyLU: The Over-Powered Activation Function
Anonymous
We present PolyLU, the polynomial linear
unit, as an activation function with optimal performance
characteristics, outperforming ReLU when applied to deep models. The
celebrated ReLU activation function eliminates the vanishing gradient;
our work takes this a step further, culminating in the field's first
trainable activation function that is also resistant to adversarial
attacks. Experiments demonstrate the potential of PolyLU and support a
mathematical analysis of PolyLU's optimality.
Good Dogs of Cambridge
Willie Boag
The city of Cambridge is home to over
105,000 residents, yet there are only barely registered 5,000 dogs. With
more than a 20-to-1 ratio of people-to-dogs, it is now more important
than ever that we use big data in order to automatically identify where
to find the best dogs. Because Cambridge is really h*ckin big, it can be
incredibly costly to go to a neighborhood that lacks sufficient good
dogs, only to realize you need to go elsewhere if you wanna be part of a
high-quality belly rub. In this work, we propose a method for
identifying which parts of Cambridge can maximize one's time with some
big ole puppers.
“We need more free food!”: Free Food and Excellent Performance of Academic Institutes
Soya Park and Nikhil Vyas
Many tech companies nowadays provide free
food to their employees as part of employee welfare program. Previous
research reveals free food at companies contributes building a bond
between employees and increasing productivity. However, not much
research on free food has been done at academy environment. Through
three weeks of the field experiment, we examine how experiment
participants find out and ingest free food in depth. We report how the
participants with different personality are managed to survive with free
food. We also observe behavior change in participants by conducting
post-interviews. We foresee our work aids Ph.D. students who are
generally broke and motivates university administrators to provide more
free food for the success of their students.
2019
TCP Over Email
Venkat Arun, Akshay Narayan, and and Mercury
In response to recent trends in e-mail
usage patterns, we propose "Reliable e-mail", or remail. remail
implements reliable delivery of email messages end-to-end, in
accordance with the end-to-end principle. Thisis a timely contribution,
in light of increasing software complexity, and Software 2.0
Human Baseline for Zero-Shot Transfer Learning of Good Dogs
William Boag and Shashank Srikant
It is estimated that there are 900 million
dogs in the world. That is a lot of dogs, and we assure you that each
one is a good dog [2]. Unfortunately, we don’t have enough time to meet
each dog de novo, and have inevitably needed to rely on word-of-mouth to
learn about which dogs to meet and when. In this work, we demonstrate
human-level performance for zero-shot dog recognition from features
describedby other humans. Human performance is robust (>85%
accuracy), even when presented with challenging comparisons. This
accuracy is in the same ballpark as Karpathy et al.’s work on a human
baseline for ImageNet [6]. We believe that this work will help future
researchers develop AI-based tools for super-human performance on
word-of-mouth-based human-dog introductions. From a neuroscience
perspective, this work also establishes the presence of a seeming
information barrier between the visual cortex and the language system of
the human brain
Do NOT Modify Breadth-First Search
Michael Coulombe
This paper settles the conjecture that
Breadth-First Search can solve the single source shortest paths
problem on weighted graphs in linear time, by demonstrating
counter-example graphs for which BFS and modifications thereof fail.
To Mississippi or Not To Mississippi: A Review of Colloquial Clocks
Dylan Cable, Austin Gadient, Aspen Hopkins, Divya Shanmugam, and Dominique Thompson
We present the first study of informal
counting, or the linguistic approximation of one second. For years, we
have trusted the word "Mississippi" to correspond with a single second.
It is past time to vet this choice and propose a path forward. First, we
quantify how imprecise the word \"Mississippi\" is. Second, we evaluate
alternatives across a random sample of 24 people (read: our friends).
We conclude with recommendations going forward.
Successful Task and Motion Planning with Hindsight Experience Reinterpretation
In this paper we describe an
approach for improving the performance of robotic Task and Motion
Planning (TAMP) systems on complex, long-horizon manipulation problems.
In an uncertain environment, unexpected situations are all but
guaranteed to arise, causing the robot to risk failure to plan or
complete a task. HERinterpret allows the robot to reinterpret its
initial goal under uncertainty, claiming a more believable goal given
the current state. We show how our Deep Reframing Net allows the robot
to reinterpret challenging goals into more achievable ones, resulting in
a 100% success rate on a variety of TAMP problems. We also propose
alternative planning methods that do not require deep reframing but
still achieve a 100% success rate through goal reinterpretation.
IRBot: InadvisableRelationshipBot
nyancy
Many graduate students struggle to deal
emotionally with daily life stresses, ranging from overdue problem
sets to not dying at sea. Additionally, computer scientists may feel
more comfortable typing at a screen than engaging in human contact.
Although therapy chatbots exist and in fact have reached millions of
smartphone users, they run on remote servers, creating privacy concerns.
In this work, we propose that a local chatbot can also provide useful
advice and can reach the vulnerable sub-population of computer
science grad students. We create InadvisableRelationshipBot (IRBot)
using high-quality online commentary from
www.reddit.com/r/relationships.
2020
Adaptive Mesh De-Resolution
Paul Zhang
The finite element method (FEM) is a
triumph of modern engineering that allows us to computationally solve a
plurality of partial differential equations (PDE) and physical system
models. It would not be an overstatement to say this technique alone
enables and supports the entire infrastructure of modern society.
Despite its flexibility and ubiquity, the method comes at high
computational cost: it seemingly requires denser meshes to decrease
numerical error. In this paper we demonstrate that contrary to
established hearsay, sparser meshes are actually what is needed to
decrease numerical error. We introduce the adaptive mesh de-resolution
technique which provably decreases all numerical error to exactly zero.
2021
Alexander Hamiltonian Monte Carlo
Alexander Lew
A curious defect of the Hamiltonian Monte
Carlo algorithm, an otherwise state-of-the-art Markov chain Monte Carlo
scheme for simulating from an unnormalized density, is that despite its
name, it has very little to do with Lin-Manuel Miranda's hit musical
Hamilton. To remedy this flaw, we propose Alexander Hamiltonian Monte
Carlo, a revolutionary new variant of HMC in which the
Metropolis-Hastings accept/reject step is replaced by an elaborate duel
between the proposed position and the previous state of the chain. The
result is a loud (in the sense of noise), diverse (in the sense of
variance) celebration of both Bayes and Broadway, which is guaranteed to
converge to the room where it happens, if the user is willing to wait
for it.
Design and Implementation of a Server Health Monitoring System
Quan Nguyen
Computer architecture research at CSAIL
requires significant computing resources. These resources are
distributed across the Stata center and sometimes crash or run into
anomalous conditions. Server problems have been hitherto discovered on
an ad-hoc basis. In this paper, we present the design and implementation
of Gibraltar, which simplifies checking the status of many machines at
once. It tries to avoid external software dependencies and tries to be
secure. We present results and conclude.
CSAIL is social
Christina Ji and Willie Boag
Scientists have long been interested in
studying human behavior, including how humans interact with each other
as social creatures. The social activities within MIT CSAIL have been
documented within the csail-social mailing list archives for many years,
providing a rich dataset for research. In our work, we use word clouds
as a way to visualize the dataset. We uncover several long-standing
traditions and fascinating events in the recent history of CSAIL. We
hope the reader will be inspired to recover these traditions and start
new ones in the coming years.
Fantasy Fantasy Football
Willie Boag
Fantasy Football is America's favorite
pretend pastime. Friend groups of all varieties play , though we all
have that asshole friend Jason that never sets his lineup. It is
interesting that although most fantasy football platforms allow for
computer-aided "auto-draft", there is little-to-no support for
"auto-manage my entire team all season." Such a notion -- bots playing
fantasy -- is a great idea, and I'll tell you why. One can create an
entire league of bots playing against one another using different
policies. In fact, why stop at one league? Let's create thousands of
leagues of bots, and then draft those bots. It'll feel just like we're
playing fantasy football, but without all of the undesirable overhead;
we'll be playing fantasy fantasy football!
prophet.pdf, the Paper to End All Papers
Quan Nguyen
The
machine learning approach to model checking is defined not only by the
appropriate unification of wide-area networks and the memory bus, but
also by the theoretical need for Moore's Law \cite{cite:0}.
Given the current status of autonomous archetypes, hackers worldwide
predictably desire the visualization of fiber-optic cables, which
embodies the key principles of robotics.
We construct a novel heuristic for the evaluation of rasterization,
which we call our system \cite{cite:undefined+}.
2022
Learning an Agile and Considerate Quadruped Relief Policy
Gabriel Margolis
End-to-end model-free reinforcement
learning has recently been demonstrated capable of synthesizing highly
robust locomotion policies for robot quadrupeds. However, most such
approaches optimize for performance objectives without considering the
robotic animal's need to occasionally relieve itself. We introduce a
novel command formulation, reward function, and vision pipeline to
enable the agent to satisfy its natural needs while complying with user
constraints. Real-world experiments demonstrate state-of-the-art
performance on fire hydrants, trees, and unsuspecting humans.
PeLU: The Porcelain-Emulated Linear Unit
Kartik Chandra and Jeffrey Chang
Inspired by the nonlinear dynamics of a
flush toilet, we introduce a novel activation function for deep
learning: the Porcelain-emulated Linear Unit (PeLU). PeLUs allow for
cheap, low-power inference on an unconventional hardware target.
SolMATe:
A Linear Algebra Package for Cloud-Based Machine Learning via
Blockchain, with Applications in IoT for Web 3.0 and Quantum Computing
in the Metaverse
Naveen T Arunachalam
Blockchain technology has the potential to
bring disruption to a wide range of disciplines by providing new means
of storing, accessing, and processing data. In particular, machine
learning is a field that stands to benefit from the accountability,
immutability, and reproducibility properties offered by blockchain
virtual machines. In this paper, we present the design and
implementation of SolMATe, a matrix library for Solidity that enables
machine learning directly within Ethereum smart contracts, thus
preventing the need for an off-chain oracle for model training and
execution. We then use SolMATe to implement both an end-to-end machine
learning pipeline and a simulated quantum computer entirely within the
Ethereum virtual machine. Future work and implications for IoT devices
such as virtual reality headsets are then discussed.
Abstract abstractions abstract abstract abstractions abstractly
Gabriel Grand, Catherine Wong, and Matthew Bowers
Abstract abstractions abstract abstract
abstractions abstractly. In the abstract, the abstraction of abstracts
represents the essence of abstraction. We abstract, via abstract
abstraction, that many abstract abstractions exist at various levels of
abstraction. We introduce meta-abstraction, a novel abstraction method
that abstracts away many of the abstract abstractions that make the
standard process of abstraction so abstract. Ultimately, this work
suggests a truly abstract view of abstraction that is so abstract as to
be, somehow, concrete.
My electric kettle cost $1000: Incorporating "irrational" caffeine addition into the rational speech act framework
Gabriel Grand
The Rational Speech Act framework is often
touted for its ability to account for nonliteral pragmatics: Under RSA,
“My electric kettle cost $1000” is interpreted as a hyperbolic
utterance conveying information about the speaker’s affect (Goodman
& Frank, 2016). However, this interpretation ignores data suggesting
that a growing population of caffeine-addicted consumers are, in fact,
willing to pay exorbitant prices for espresso machines, Burr grinders,
and, of course, electric kettles. In this work, we argue that RSA
systematically undervalues high-end coffee paraphernalia. To correct for
this bias, we propose a new framework, EspReSSA, which adds an
additional term U(caff) to explicitly model the utility that the speaker
derives from a 12oz cup of well-brewed Arabica coffee. We demonstrate
that, compared to vanilla RSA, our EspReSSA model more robustly predicts
pragmatic inferences about consumer purchasing behavior that would
otherwise be considered irrational under vanilla RSA. This work
highlights the strong mediating influence of biological impulse on
speaker/listener utility, suggesting a variety of individually-tailored,
addiction-based pragmatics models for future work to explore.
Country-Fried Coq: Overly-Formalized Nonstandard Arithmetic, with Applications to Computer Science Research
Michael Coulombe
Country-Fried Coq is an extension to the
popular proof assistant software Coq to support nonstandard arithmetic.
Did you know there is a natural number k with the properties
“0 < k”, “1 < k”, “2 < k”,
“3 < k”, and so on for EVERY numeral? In any nonstandard
proof using axioms
{ “n_1 < k”, “n_2 < k , ... , “n_m < k” },
we could just redefine k as
max(n_1, n_2, ... , n_m)+1 to get a standard proof.
In this paper, I give a novel approach for taking way too long to
formally-verify this simple idea in Coq; introduce Country-Fried Coq,
which adds this number to Coq itself; and show that it has a home in
your computer science recipe book.
Macro-oriented design and implementation of a 32-bit RISC-V processor in Minecraft
Quan Nguyen
Complex processor designs in Minecraft
require months of manual effort tantamount to full-custom design. Prior
works have enabled the automatic placement and routing of Minecraft
redstone circuits, but even modest designs exceed the limits of these
works. We propose a new discipline of Minecraft redstone circuit design
that reduces complexity by operating at the macro cell level. Our new
technique also leverages key observations that were not observed by
prior work, such as the balance of memory and logic. We evaluate our new
technique by demonstrating the first known implementation of a 32-bit
RISC-V processor in Minecraft.
2023
The Art of Making Good Jokes: An Algorithmic Approach
Shashank Srikant
Humor is an essential part of human
communication, and making jokes is one of the most common forms of
humor. While making good jokes may seem like a natural talent, recent
studies have shown that it can also be approached algorithmically. In
this paper, we propose a novel algorithmic approach to making good
jokes, based on a combination of linguistic analysis, computational
creativity, and social context.
You're Too Slow! The Case for Constant-time Algorithms
Michael Coulombe
Constant-time algorithms underlie all
computation, but are often discarded as mere building blocks for solving
inherently-slow problems. In this paper, we demonstrate the astonishing
power of various deterministic and nondeterministic models when
constrained to O(1) time.
StabGPT: A Tool-Equipped LLM Designed for Improving Social Outcomes
Naveen Arunachalam, Ferdinand Kossmann, and Stephen Casper
We present a proof-of-concept for an
autonomous, armed multi-Roomba system that leverages a Transformer-based
artificial intelligence model as its central "brain". The system uses a
federated model of control that enables each Roomba to make informed
decisions to optimize social outcomes while collaborating with other
Roombas in the system. Our simulations demonstrate that this system
improves social outcomes, including reduced crime rates and increased
prosocial behavior. Our proof-of-concept implementation with a 2021
iRobot device demonstrates the first instance of injury and subsequent
remediation of a human caused by a Transformer-based intelligence model.
Ethics statement: We acknowledge the ethical concerns this technology
raises and are committed to its development in a responsible and
transparent manner that respects individual rights and privacy. Our
future work will focus on further refining the system's capabilities and
exploring its potential societal impact, such as increasing its
resilience to individuals that interfere with its operations (e.g.,
increasing punishments for malevolent users, and allowing Roombas to
swarm powerful targets).
Gates as a Service
Quan Nguyen
Digital circuit simulation continues to be
an important tool for verifying the correctness of silicon prior to
fabrication. However, growing chip sizes threaten to make simulation
impossible on modern systems. In addition, computing infrastructure is
expensive, making large-scale simulations available to only but the most
well-heeled organizations. In this paper, we propose Gates as a Service
(GaaS), which encapsulates the function of a single logic gate. Our
system distributes gate simulation across the Earth, building atop
Amazon AWS, to address the scalability problem. To the best of our
knowledge, we will (have been) the first to distribute the simulation of
a four-bit counter across the globe.
Every Author as First Author
Erik Demaine
Martin Demaine
We propose a new standard for writing
author names on papers and in bibliographies, which places every author
as a first author — superimposed. This approach enables authors to
write papers as true equals, without any advantage given to whoever's
name happens to come first alphabetically (for example). We develop the
technology for implementing this standard in LaTeX, BibTeX, and HTML;
show several examples; and discuss further advantages.
A LLM for Free-food Application
Thomas Benchetrit
Food is essential for the human body to
function correctly. How- ever, students and PhDs often lack the funds to
eat an healthy and regular diet. Such issue could be resolved by
attending to the free- food events that occur regularly on the place of
work. However no current algorithm exists to curate and sort these
events. Using LLM and scrapping algorithms, this paper showcases an
unified method to resolve this issue and provide a simple method to be
informed of such events.
2024
SIGTBD did not occur in 2024.
2025
This Paper Ends When I Make a Syntax Error
Matt Li (Boston University)
Writing a paper in the LATEX format is difficult, due to its
many technical idiosyncrasies. In this paper, we provide an
overview of formatting commands that users report having
the most trouble with and introduce a framework to assist
authors when writing research papers.
This 100% Accurate Device Detects Perpetual Motion Machines. Bhaskara II in Shambles!
Matt Li (Microsoft)
We introduce a novel device, termed the Perpetual Motion
Detection System (PMDS), which utilizes a complex machine
learning framework to detect and validate perpetual
motion machines. The PMDS system was measured to have
an accuracy of 100% in a double blind trial, exceeding the
leading accuracy rates of any detection device created in the
past. The PMDS system, which is both small and easy to
carry, can be mass-produced and housed within any institution seeking to validate potential discoveries of infinite energy sources.
Restoring Humanity to Interfaces: A Systems Approach
Quan Nguyen
In the supposed name of improved communication, we
have created techniques to transfer information between the physical world
and machines, such as QR codes. The proliferation of such codes comes at
the expense of intuitive and natural interfaces in a world inhabited and
manipulated largely by humans. We see this shift as an abdication from the
responsibility of sensible interface design, and argue it is technology's
obligation to adapt to a human world, not the other way around. This talk
examines the surrender of human-friendly interfaces for the sake of
"efficiency" with a special case study on QR codes. Our discussion
culminates in a proof-of-concept tool as a protest against unnecessarily
machine-oriented interfaces.
Zero Is All You Need (To Get Many Useful Properties)
Yunyi Shen (MIT), Eric Xia (MIT), Tamara Broderick (MIT)
Data analysts typically report empirical accuracy
scores to support the efficacy of new methodology. But it has long been
understood that good accuracy performance on a collection of available
data sets is not enough to guarantee useful performance in real-world
deployment of a method. For instance, learned models may fail to
generalize well to new data sets due to issues with stability and
robustness. Some methods may be too expensive in the face of limited
resources (e.g., compute time, memory, or user time) for many analysts to
run at all. In the present paper, we take the opposite perspective and
ask: what if we considered a wide range of desiderata for data science
methods excluding experimental accuracy? In this case, we find that a
classic algorithm from the literature, namely an algorithm that always
returns 0, achieves peak performance across a very wide range of
desiderata.
Philosophers Certainly Are, But Do They Think?
Selina Guter (MIT), Michael Z. Wang (MIT), Tanner J. Andrulis (MIT)
Do philosophers think? It has long been assumed that
they do. However, reports of philosophers thinking are generally limited
self-reports (e.g., Descartes, 1641). Modern psychology casts doubt on
this methodology, as introspective evidence can be misleading (Nisbett &
Wilson, 1977). To overcome these methodological issues, we conducted the
first empirically informed study of philosopher intelligence in the form
of Turing’s (1950) ‘Imitation Game’, also known as the Turing Test.
Results were shocking: Most MIT philosophers did not reliably pass the
test against a modified version of GPT-4, and qualitative analysis of
Interrogator responses cast serious doubt on philosophers’ ability to
think. Interrogators consistently report that philosophers seem to not be
appropriately connected to the real world. This suggests philosophers are
incapable of forming mental states with intentional content&emdash;a key
necessary ingredient for thought (Brentano, 1874).
HAT: Toward Robustness to Adversarial Silly Hat Attacks
Bjorn Lutjens (MIT), Justin Kay (MIT)
Computer vision systems are increasingly being
deployed for real-time detection of invasive species, such as sea urchins.
After a period of initial success, detection rates have been dropping,
with the reasons still being unknown. Here, we demonstrate that a trend in
sea urchins wearing silly hats can decrease detection rates in commonly
used urchin recognition software. To overcome the fragility of the
underlying neural networks to this distribution shift, we propose silly
*h*at *a*ugmenta*t*ions. HAT is a universal augmentation strategy adding
generative AI-based hats onto sea urchin imagery, and we show that using
HAT increases adversarial robustness to silly hat attacks over
82.8%.
Hardness Table Layout Hardness Table
MIT Hardness Grp., Josh Brunner (MIT), Andy Tockman (MIT), Frederick Stock (UMass Lowell), Della Hendrickson (MIT), Hayashi Layers (MIT), Timothy Gomez (MIT), Erik D. Demaine (MIT), Jenny Diomidova (MIT)
nan
If you don't see your paper here, never fear! We would be happy to add your submission to this list.
Instructions for Submission to SIGTBD'26
This document provides instructions for submitting papers to
SIGTBD. In an effort to respect the efforts of reviewers and in the
interest of fairness to all prospective authors, we request that all
submissions to SIGTBD follow the formatting and submission rules
detailed below. Submissions that violate these instructions may not be
reviewed, at the discretion of the program chair, in order to maintain a
review process that is fair to all potential authors.
The committee will make every effort to judge each submitted
paper on its own merits. There will be no target acceptance rate. We
expect to accept a wide range of papers with appropriate expectations
for evaluation — while papers that build on significant past work with
strong evaluations are valuable, papers that open new areas with less
rigorous evaluation are equally welcome and especially encouraged. In
either case, what is important is that the paper’s claims are no
stronger than what is supported by the evaluation. Given the wide range
of topics covered by SIGTBD, every effort will be made to find expert any reviewers.
All questions regarding paper formatting and submission should be directed to the program chair.
The paper submission site is this Google Form.
Submission Resources
General Submission Requirements
- Paper must be submitted in printable PDF format.
- Text must be in a minimum 10pt font (not 9pt).
- Submissions are double blind and author names must be removed.
- On the published copy, authors must be ordered by ascending number of vowels.
- Papers must be at most 11 pages in US letter format, not including references.
- additional appendices (beyond 11 pages) are allowed in the paper submission.
- There is no page limit for references.
- Each reference must specify all authors (no et al.).
- The rules above don't apply to posters.
Conference Requirements
Authors of all accepted papers will be required to give a
regular conference talk and submit a tweet abstract (no longer than 280
characters), and may optionally submit a Vine video advertising their
talk. The published copy of the paper will be included in the Proceedings
of SIGTBD and available on the online SIGTBD digital library
(subscription required for access).
Summary of requirements:
- Required: A 5 minute conference talk
- Required: A short form abstract (< 280 characters)
- Optional: A Vine video advertising the talk (Example)
Poster session:
- Required: A poster no larger than an 8 ½ x 11 piece of paper (Example)
- Required: A 1 minute lightning talk
Conflicts
You should specify the names that represent actual conflicts -
where an individual who is a conflict in the context of this conference
shares the same initials as one of the co-authors. Individuals declared a
conflict will be tagged with a unique identifier to prevent aliasing of
entries in the database.
Any interpersonal conflicts of interest must be declared in the
form of a passive aggressive email sent to the PC chair. In the event an
interpersonal conflict of interest is declared, the validity of the
interpersonal conflict of interest will be determined by the PC. The
best conflict of interest emails will be anonymized and included in the
conference proceedings.
Submission Formatting
Papers must be submitted in PDF format and follow the standard
two-column ACM proceedings style in 9-point font and be at most 10
pages, exclusive of the bibliography. The bibliography is excluded from
the page count to encourage good citation practices and discourage
illegible bibliographies. Citations can be either in numeric style or
author-year style. Numeric citations always stand as a parenthetical
note (e.g., “[42]”), while author-year citations may stand either as a
noun phrase (e.g., “Church (1935)”), or as a parenthetical note (e.g.,
“(Church, 1935)”).
If you are using LaTeX to typeset your paper, then we strongly suggest that you use this LaTeX class file (with the ‘sigtbd’ class option) and template.
If you are using Microsoft Word, we recommend you give up on following
any of the formatting requirements and submit in whatever format you
please.
Double Blind
Reviewing will be double blind; therefore, please do not
include any author names or links to author’s website, etc. on any
submitted documents except in the space provided on the online
submission form. Please take time to read the SIGTBD FAQ on Double Blind
Reviewing, which gives a more comprehensive and authoritative account
than this short paragraph. If you are improving upon your prior work,
refer to your prior work in the third person and include a full citation
for the work in the bibliography. For example, if you happened to be
Collins and McCarthy, building on your own prior work, you might say
something like: “While prior work [Backus et al. 1960; Collins 1960;
McCarthy 1960] did X, Y, and Z, this paper additionally does W, and is
therefore much better.” Do NOT omit or anonymize references for blind
review.
In general, you should aim to reduce the risk of accidental
unblinding. For example, if your paper describes a system with a
well-known name or codename, or you use a personally-identifiable naming
convention for your work, you must use a different name for your
submission (which you may indicate has been changed for the purposes of
double-blind reviewing). You should also avoid revealing the institution
where the work was performed.
Figures and Tables
Ensure that the figures and tables are legible. Please also
ensure that you refer to your figures in the main text. Many reviewers
print the papers in gray-scale. Therefore, please use colors for your
figures and ensure that the different colors are not highly
distinguishable in gray-scale, so that these reviewers can finally be
persuaded to stop doing that.
References
There is no length limit for references. Each reference must
explicitly list all authors of the paper. Papers not meeting this
requirement will be rejected.
Declaring Authors
Enter all authors of the paper into the online paper submission
tool upfront. Addition/removal of authors once the paper is accepted
will have to be approved by the program chair, since it potentially
undermines the goal of eliminating conflicts for reviewer assignment.
Concurrent Submissions and Workshops
By submitting a manuscript to SIGTBD, authors guarantee that
they are adhering to the SIGPLAN Republication Policy. Please ensure
that you are familiar with it. Violation of any of these conditions will
lead to rejection.
As always, if you are in doubt, it is best to contact the program chair.
Finally, we also note that the ACM Plagiarism Policy covers a
range of ethical issues concerning the misrepresentation of other works
or one’s own work. To encourage proper citation of your work, all
submissions must cite themselves in their own references section.
Early Access in the Digital Library
The SIGTBD proceedings may be available on the ACM Digital
Library as early as May 30, 2034. Authors must consider any implications
of this early disclosure of their work before submitting their papers.
Acknowledgements
This document is based heavily on ones prepared for previous
conferences and we thank their program chairs; in particular, Sandhya
Dwarkadas (ASPLOS’15), Sarita Adve (ASPLOS’14), Steve Keckler (ISCA’14),
Christos Kozyrakis (Micro’13), Margaret Martonosi (ISCA’13), Onur Mutlu
(Micro’12), Michael L. Scott (ASPLOS’12), and Steve Blackburn
(SIGTBD’15).
References
J. W. Backus, F. L. Bauer, J. Green, C. Katz, J. McCarthy, A.
J. Perlis, H. Rutishauser, K. Samelson, B. Vauquois, J. H. Wegstein, A.
van Wijngaarden, and M. Woodger. Report on the algorithmic language
ALGOL 60. Commun. ACM, 3(5):299– 314, May 1960. ISSN 0001-0782. doi:
10.1145/367236.367262.
G. E. Collins. A method for overlapping and erasure of lists.
Commun. ACM, 3(12):655–657, December 1960. doi: 10.1145/367487.367501.
L. Lamport. LaTeX: A Document Preparation System. Addison- Wesley, Reading, Massachusetts, 2nd edition, 1994.
J. McCarthy. Recursive functions of symbolic expressions and
their computation by machine, part I. Commun. ACM, 3(4): 184–195, April
1960. doi: 10.1145/367177.367199.
