Lecture

Pairwise Independence: Hashing and Load Balancing

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many ...

Description

This lecture covers the concept of pairwise independence in hashing, focusing on the goal of achieving no collisions in a hash family. The instructor explains the importance of using random linear functions to achieve this goal and discusses the process of load balancing when hashing elements uniformly into slots.

Instructors (3)

Mikhail Kapralov

Teaching & PhD PhD Students Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth Past EPFL PhD Students Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail Past EPFL PhD Students as codirector Paritosh Garg Courses Algorithms II CS-450 The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing alg

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Official source

Related concepts (32)

Collision

In physics, a collision is any event in which two or more bodies exert forces on each other in a relatively short time. Although the most common use of the word collision refers to incidents in which two or more objects collide with great force, the scientific use of the term implies nothing about the magnitude of the force. In physics, collisions can be classified by the change in the total kinetic energy of the system before and after the collision: If most or all of the total kinetic energy is lost (dissipated as heat, sound, etc.

Inelastic collision

An inelastic collision, in contrast to an elastic collision, is a collision in which kinetic energy is not conserved due to the action of internal friction. In collisions of macroscopic bodies, some kinetic energy is turned into vibrational energy of the atoms, causing a heating effect, and the bodies are deformed. The molecules of a gas or liquid rarely experience perfectly elastic collisions because kinetic energy is exchanged between the molecules' translational motion and their internal degrees of freedom with each collision.

Elastic collision

In physics, an elastic collision is an encounter (collision) between two bodies in which the total kinetic energy of the two bodies remains the same. In an ideal, perfectly elastic collision, there is no net conversion of kinetic energy into other forms such as heat, noise, or potential energy. During the collision of small objects, kinetic energy is first converted to potential energy associated with a repulsive or attractive force between the particles (when the particles move against this force, i.e.

Head-on collision

A head-on collision is a traffic collision where the front ends of two vehicles such as cars, trains, ships or planes hit each other when travelling in opposite directions, as opposed to a side collision or rear-end collision. With railways, a head-on collision occurs most often on a single line railway. This usually means that at least one of the trains has passed a signal at danger, or that a signalman has made a major error. Head-on collisions may also occur at junctions, for similar reasons.

Traffic collision

A traffic collision, also called a motor vehicle collision (car crash in case cars are involved in the collision), occurs when a vehicle collides with another vehicle, pedestrian, animal, road debris, or other moving or stationary obstruction, such as a tree, pole or building. Traffic collisions often result in injury, disability, death, and property damage as well as financial costs to both society and the individuals involved.

Related lectures (64)

Plasma Physics: Collisions and Resistivity

Covers Coulomb collisions and resistivity in plasma, highlighting their random walk nature.

Probabilistic Analysis: Hiring & Birthday Paradox

Explores probabilistic analysis in algorithms, covering the hiring problem and the birthday paradox, along with hash tables and functions.

Plasma Collisions: Coulomb Force

Analyzes Coulomb collisions between charged particles and the conservation of energy, momentum, and angular momentum.

Hash Tables Analysis

Covers the analysis of hash tables, including search operations and expected collisions.

Chemical Equilibria and Reactivity