Follow the ideas that keep turning up in Hacker News discussions.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
David Manheim, Scott Garrabrant
There are several distinct failure modes for overoptimization of systems on the basis of metrics.
Donald E. Knuth
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.
Kenji Kawaguchi, Leslie Pack Kaelbling, Yoshua Bengio
This paper provides theoretical insights into why and how deep learning can generalize well, despite its large capacity, complexity, possible algorithmic instability, nonrobustness, and sharp minima, responding to an open question in the literature.
Ziwei Xu, Sanjay Jain, Mohan Kankanhalli
Hallucination has been widely recognized to be a significant drawback for large language models (LLMs).
Heidi Howard, Richard Mortier
Distributed consensus is a fundamental primitive for constructing fault-tolerant, strongly-consistent distributed systems.
Scott Aaronson
Can NP-complete problems be solved efficiently in the physical universe?
Stefan Edelkamp, Armin Weiß
Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort -- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an essential way from branch mispredictions.
Ewin Tang
We give a classical analogue to Kerenidis and Prakash's quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning.
Heidi Howard, Dahlia Malkhi, Alexander Spiegelman
Distributed consensus is integral to modern distributed systems.
Zhen Qin, Rolf Jagerman, Kai Hui +9
Ranking documents using Large Language Models (LLMs) by directly feeding the query and candidate documents into the prompt is an interesting and practical problem.
Robert P. Colwell, Edward F. Gehringer, E. Douglas Jensen
The Intel 432 is noteworthy as an architecture incorporating a large amount of functionality that most other systems perform by software.
OpenAI, Josh Achiam, Steven Adler +278
We report the development of GPT-4, a large-scale, multimodal model which can accept image and text inputs and produce text outputs.
Hattie Zhou, Azade Nova, Hugo Larochelle +3
Large language models (LLMs) have shown increasing in-context learning capabilities through scaling up model and data size.
Philip Maymin
I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time.
Rajeev Acharya, Laleh Aghababaie-Beni, Igor Aleiner +246
Quantum error correction provides a path to reach practical quantum computing by combining multiple physical qubits into a logical qubit, where the logical error rate is suppressed exponentially as more qubits are added.
Joel Lehman, Jeff Clune, Dusan Misevic +50
Biological evolution provides a creative fount of complex and subtle adaptations, often surprising the scientists who discover them.
John Kirchenbauer, Jonas Geiping, Yuxin Wen +3
Potential harms of large language models can be mitigated by watermarking model output, i.e., embedding signals into generated text that are invisible to humans but algorithmically detectable from a short span of tokens.
Mary Phuong, Marcus Hutter
This document aims to be a self-contained, mathematically precise overview of transformer architectures and algorithms (*not* results).
Paul-Virak Khuong, Pat Morin
We attempt to determine the best order and search algorithm to store $n$ comparable data items in an array, $A$, of length $n$ so that we can, for any query value, $x$, quickly find the smallest value in $A$ that is greater than or equal to $x$.
Raph Levien
Computation of bounding boxes is a fundamental problem in high performance rendering, as it is an input to visibility culling and binning operations.
Chengzheng Sun, David Sun, Agustina +1
OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become a core technique used in today's working co-editors and adopted in major industrial products.
Mihaly Barasz, Paul Christiano, Benja Fallenstein +3
We consider the one-shot Prisoner's Dilemma between algorithms with read-access to one anothers' source codes, and we use the modal logic of provability to build agents that can achieve mutual cooperation in a manner that is robust, in that cooperation does not require exact equality of the agents' source code, and unexploitable, meaning
Naftali Tishby, Noga Zaslavsky
Deep Neural Networks (DNNs) are analyzed via the theoretical framework of the information bottleneck (IB) principle.
David M. Blei, Alp Kucukelbir, Jon D. McAuliffe
One of the core problems of modern statistics is to approximate difficult-to-compute probability densities.
Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan +1
We introduce OpSets, an executable framework for specifying and reasoning about the semantics of replicated datatypes that provide eventual consistency in a distributed system, and for mechanically verifying algorithms that implement these datatypes.
Robert E. Tarjan, Caleb C. Levy, Stephen Timmel
We introduce the zip tree, a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package.
Bobby Powers, David Tench, Emery D. Berger +1
Programs written in C/C++ can suffer from serious memory fragmentation, leading to low utilization of memory, degraded performance, and application failure due to memory exhaustion.
Rafael Rafailov, Archit Sharma, Eric Mitchell +3
While large-scale unsupervised language models (LMs) learn broad world knowledge and some reasoning skills, achieving precise control of their behavior is difficult due to the completely unsupervised nature of their training.