**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Stein Algorithm: Polynomial Identity Testing

Description

This lecture covers the Stein algorithm for polynomial identity testing, focusing on the minimization of a cut problem. The instructor explains the process step by step, emphasizing the importance of finding the correct solution efficiently. The lecture also delves into the concept of determining the determinant of a matrix in relation to polynomials, showcasing practical examples and applications.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

Instructors (3)

Related concepts (176)

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 reper

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

A contract is an agreement that specifies certain legally enforceable rights and obligations pertaining to two or more mutually agreeing parties. A contract typically involves the transfer of goods, services, money, or a promise to transfer any of those at a future date. In the event of a breach of contract, the injured party may seek judicial remedies such as damages or rescission. A binding agreement between actors in international law is known as a treaty.

In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1. Polynomials appear in many areas of mathematics and science.

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

A quasi-contract (or implied-in-law contract or constructive contract) is a fictional contract recognised by a court. The notion of a quasi-contract can be traced to Roman law and is still a concept used in some modern legal systems. Quasi contract laws have been deduced from the Latin statement "Nemo debet locupletari ex aliena jactura", which proclaims that no man should grow rich out of another person's loss. It was one of the central doctrines of Roman law.

Related lectures (741)

Graphical Models: Representing Probabilistic DistributionsPHYS-512: Statistical physics of computation

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Polynomial Identity TestingCS-450: Algorithms II

Covers polynomial identity testing using oracles and random point evaluation, with applications in graph theory and algorithmic aspects.

Polynomials: Operations and PropertiesMATH-111(e): Linear Algebra

Explores polynomial operations, properties, and subspaces in vector spaces.

Linear Algebra: Abstract ConceptsMATH-111(e): Linear Algebra

Introduces abstract concepts in linear algebra, focusing on operations with vectors and matrices.

Linear Transformations: Matrices and Kernels

Covers linear transformations, matrices, kernels, and properties of invertible matrices.