Transformers are slow and memory-hungry on long sequences, since the time memory complexity of self-attention quadratic in sequence length. Approximate attention methods have attempted to address this problem by trading off model quality reduce compute complexity, but often do not achieve wall-clock speedup. We argue that a missing principle is making algorithms IO-aware -- accounting for reads writes between levels GPU memory. propose FlashAttention, an exact algorithm uses tiling number...

column Share on Skew strikes back: new developments in the theory of join algorithms Authors: Hung Q Ngo University at Buffalo, SUNY SUNYView Profile , Christopher Ré Stanford UniversityView Atri Rudra Authors Info & Claims ACM SIGMOD RecordVolume 42Issue 4December 2013 pp 5–16https://doi.org/10.1145/2590989.2590991Online:28 February 2014Publication History 115citation817DownloadsMetricsTotal Citations115Total Downloads817Last 12 Months130Last 6 weeks16 Get Citation AlertsNew Alert...

We present error-correcting codes that achieve the information-theoretically best possible trade-off between rate and error-correction radius.Specifically, for every 0 < R 1 ε > 0, we an explicit construction of can be list decoded in polynomial time up to a fraction (1-R-ε) worst-case errors.At least theoretically, this meets one central challenges algorithmic coding theory.Our are simple describe: they folded Reed-Solomon codes, which fact exactly (RS) but viewed as code over larger...

Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural queries over many relations describe a novel algorithm to process these optimally terms worst-case data complexity. Our result builds on recent work by Atserias, Grohe, Marx, who gave bounds size full conjunctive query sizes individual body query. These bounds, however, are not constructive: they rely Shearer's entropy inequality which...

We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical models logic. This is our main conceptual contribution. then present a simple algorithm called "InsideOut" to solve this general problem. InsideOut variation of traditional dynamic programming approach for based on variable elimination. Our adds couple twists basic elimination order deal with...

Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural queries over many relations describe a new algorithm to process these optimally terms worst-case data complexity. Our result builds on recent work by Atserias, Grohe, Marx, who gave bounds size query sizes individual body query. These bounds, however, are not constructive: they rely Shearer’s entropy inequality, which information-theoretic....

A central problem in learning from sequential data is representing cumulative history an incremental fashion as more processed. We introduce a general framework (HiPPO) for the online compression of continuous signals and discrete time series by projection onto polynomial bases. Given measure that specifies importance each step past, HiPPO produces optimal solution to natural function approximation problem. As special cases, our yields short derivation recent Legendre Memory Unit (LMU) first...

Recurrent neural networks (RNNs), temporal convolutions, and differential equations (NDEs) are popular families of deep learning models for time-series data, each with unique strengths tradeoffs in modeling power computational efficiency. We introduce a simple sequence model inspired by control systems that generalizes these approaches while addressing their shortcomings. The Linear State-Space Layer (LSSL) maps $u \mapsto y$ simply simulating linear continuous-time state-space...

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order vertices by their indegrees. show that this has an approximation guarantee of 5 if weights satisfy probability constraints (for any pair u and v, wuv + wvu = 1). Special cases such include unweighted rank aggregation. Finally, constant e > 0, we exhibit infinite family (unweighted) which above (irrespective how ties are broken) ratio - e.

We consider the following "efficiently decodable" non-adaptive group testing problem. There is an unknown string x ∊ {0, 1}n with at most d ones in it. are allowed to test any subset S ⊆ [n] of indices. The answer tells whether xi = 0 for all i or not. objective design as few tests possible (say, t tests) such that can be identified fast poly(t)-time). Efficiently decodable has applications many areas, including data stream algorithms and forensics.A strategy represented by a × n matrix,...

State space models (SSMs) have demonstrated state-of-the-art sequence modeling performance in some modalities, but underperform attention language modeling. Moreover, despite scaling nearly linearly length instead of quadratically, SSMs are still slower than Transformers due to poor hardware utilization. In this paper, we make progress on understanding the expressivity gap between and modeling, reducing barrier attention. First, use synthetic tasks understand We find that existing struggle...

We consider the following efficiently decodable non-adaptive group testing problem. There is an unknown string x ∈ {0, 1}n with at most d ones in it. are allowed to test any subset S ⊆ [n] of indices. The answer tells whether xi = 0 for all i or not. objective design as few tests possible (say, t tests) such that can be identified fast poly(t)-time). Efficiently has applications many areas, including data stream algorithms and forensics.A strategy represented by a n matrix, which stacking...

Energy consumption has emerged as a first class computing resource for both server systems and personal devices. The growing importance of energy led to rethink in hardware design, hypervisors, operating compilers. Algorithm design is still relatively untouched by the algorithmic complexity models do not capture consumed an algorithm. In this paper, we propose new model account used Based on abstract memory (which was inspired popular DDR3 similar parallel disk I/O Vitter Shriver), present...

Join optimization has been dominated by Selinger-style, pairwise optimizers for decades. But, Selinger-style algorithms are asymptotically suboptimal applications in graphic analytics. This sub-optimality is one of the reasons that many have advocated supplementing relational engines with specialized graph processing engines. Recently, new join discovered achieve optimal worst-case run times any or even so-called beyond (or instance optimal) time guarantees classes joins. These match improve...

Teaching applied ethics in computer science has shifted from a perspective of teaching about professional codes conduct and an emphasis on risk management towards broader understanding the impacts computing humanity environment principles practices responsible computing. One primary shifts approach to comes research social sciences humanities. This position is grounded idea that all artifacts, projects, tools, products are situated within set ideas, attitudes, goals, cultural norms. means...

For every 0 < R 1 and ε > 0, we present an explicit construction of error-correcting codes rate that can be list decoded in polynomial time up to a fraction (1-R-ε) errors. These achieve the "capacity" for decoding from adversarial errors, i.e., optimal trade-off between error-correction radius. At least theoretically, this meets one central challenges coding theory.Prior work, achieving capacity were not known any R. In fact, our are first beat radius 1-√R, was achieved Reed-Solomon (RS)...

The primary goal of compressed sensing and (non-adaptive) combinatorial group testing is to recover a sparse vector x from an underdetermined set linear equations Φx = y. Both problems entail solving y given Φ but they use different models arithmetic, randomness for F, guarantees upon the solution class signals which drawn. In [1], Lipton introduced model error correction where channel computationally bounded, subject standard cryptographic assumptions, produces that must be found then...

We show that any q-ary code with sufficiently good distance can be randomly punctured to obtain, high probability, a is list decodable up radius 1 --- 1/q ε near-optimal rate and sizes.