Picture this. It’s a warm summer evening. After a long day, your roommate and you settle down on the couch to indulge
your respective Internet-fueled pastimes. You’ve pulled up undeniably adorable cat videos on YouTube, and your roommate
is catching up on the latest episode of he…
In this blog post, I will explain a series of 3 papers, where the third one gives the first construction of explicit constant-degree lossless vertex expanders.
[HMMP24] Explicit two-sided unique-neighbor expanders. With Theo McKenzie, Sidhanth Mohanty, Pedro Paredes.
STOC, 2024…
Paper assignment is crucial in conference peer review as we need to ensure that papers receive high-quality reviews and reviewers are assigned papers that they are willing and able to review. Moreover, it is essential that a paper-matching process mitigates potential malicious b…
Data structures contain two important aspects that computer scientists seek to verify: behavior and cost.
The behavior of data structures has long been studied using abstraction functions, which translate concrete data structure representations into a semantic representation.
On …
Since the development of the first database management systems (DBMSs) over five decades ago, DBMSs
have become the foundation of modern data-intensive applications. However, deploying and
maintaining a DBMS for these applications is more challenging now than ever. Such applicat…
The field of formal verification is all about using mathematically rigorous techniques and tools to prove properties about systems. The applications of formal verification vary widely. There are computer-checked correctness proofs for critical pieces of software such as compilers…
How do we allocate items among individuals with different preferences in a way that is both fair and efficient?
Striking this balance is a fundamental challenge in economics and game theory, with implications ranging from inheritance division and divorce settlements to resourc…
The content of this blog post is derived from the research paper Computing Game Symmetries and Equilibria That Respect Them, published at AAAI-25, and authored by Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, and Vincent Conitzer.
TL;DR: We discuss the impl…
Modern AI excels at pattern recognition but suffers when faced with logical reasoning tasks. What happens when we ask a neural network to solve a Sudoku puzzle from an image, verify a mathematical proof, or diagnose a medical condition based on a set of symptoms and rules? These…
Key takeaway: When learning over discrete prompts used in modern vision-language models, classical PAC-Bayes bounds turn out to be remarkably tight — significantly tighter than prior PAC-Bayes results on deep networks.
If you have ever tinkered with a large vision-language model …
