Graph invariants | Circuit complexity

Tardos function

In graph theory and circuit complexity, the Tardos function is a graph invariant introduced by Éva Tardos in 1988 that has the following properties: * Like the Lovász number of the complement of a graph, the Tardos function is sandwiched between the clique number and the chromatic number of the graph. These two numbers are both NP-hard to compute. * The Tardos function is monotone, in the sense that adding edges to a graph can only cause its Tardos function to increase or stay the same, but never decrease. * The Tardos function can be computed in polynomial time. * Any monotone circuit for computing the Tardos function requires exponential size. To define her function, Tardos uses a polynomial-time approximation scheme for the Lovász number, based on the ellipsoid method and provided by . Approximating the Lovász number of the complement and then rounding the approximation to an integer would not necessarily produce a monotone function, however. To make the result monotone, Tardos approximates the Lovász number of the complement to within an additive error of , adds to the approximation, and then rounds the result to the nearest integer. Here denotes the number of edges in the given graph, and denotes the number of vertices. Tardos used her function to prove an exponential separation between the capabilities of monotone Boolean logic circuits and arbitrary circuits.A result of Alexander Razborov, previously used to show that the clique number required exponentially large monotone circuits, also shows that the Tardos function requires exponentially large monotone circuits despite being computable by a non-monotone circuit of polynomial size.Later, the same function was used to provide a counterexample to a purported proof of P ≠ NP by Norbert Blum. (Wikipedia).

Video thumbnail

A5 More on tables

In this video I show you how to use the tables function in Desmos.

From playlist Biomathematics

Video thumbnail

A3 More graphs and their functions

We expand to transcendental functions such a trigonometric functions. Ply around with the Desmos calculator software and learn more about the how variables that can appear in trigonometric functions affect the graphs of those functions.

From playlist Biomathematics

Video thumbnail

What is a Function? Calculus for Beginners: Dr Chris Tisdell Live Stream

What is a function and how are they useful? This video will answer these questions from an elementary mathematics point of view. Functions are a bit like a machine that follows a processing rule. You input something (like a number), the machine processes the number according to the rule,

From playlist Calculus for Beginners

Video thumbnail

Trigonometry 2 The Trigonometric Functions

Meet the 6 main trigonometric functions of right triangles and some of their identities.

From playlist Trigonometry

Video thumbnail

Describing Functions (Discrete Math)

This video covered the various ways to describe functions in a discrete math class.

From playlist Functions (Discrete Math)

Video thumbnail

Quadratic Function

The Video going to guide how to make quadratic function with graph. lets see the video to make it, it's easy.

From playlist CALCULUS

Video thumbnail

Progress on algorithmic versions of the Lovasz Local Lemma - Aravind Srinivasan

Aravind Srinivasan University of Maryland, College Park April 7, 2014 There has been substantial progress on algorithmic versions and generalizations of the Lovasz Local Lemma recently, with some of the main ideas getting simplified as well. I will survey some of the main ideas of Moser &

From playlist Mathematics

Video thumbnail

Working with Functions (1 of 2: Notation & Terminology)

More resources available at www.misterwootube.com

From playlist Working with Functions

Video thumbnail

Stanley-Wilf limits are typically exponential - Jacob Fox

Jacob Fox Massachusetts Institute of Technology October 7, 2013 For a permutation p, let Sn(p) be the number of permutations on n letters avoiding p. Stanley and Wilf conjectured that, for each permutation p, Sn(p)1/n tends to a finite limit L(p). Marcus and Tardos proved the Stanley-Wilf

From playlist Mathematics

Video thumbnail

Abel in Paris - Éva Tardos (Cornell University): "Quality of equilibria and effect of learning...

Abel in Paris - Éva Tardos (Cornell University): "Quality of equilibria and effect of learning in games" Éva Tardos est professeure en informatique à l’université de Cornell (Ithaca, New York). Sa recherche porte sur des algorithmes appliqués aux jeux en réseaux et aux ventes aux

From playlist Abel in PARIS - IHP - 2015

Video thumbnail

Aravind Srinivasan: Approximating integer programming problems by partial resampling

Partial resampling is a variant of the Moser-Tardos algorithm for the Lovasz Local Lemma; it was developed by Harris and the speaker (FOCS 2013). We present two families of applications of this framework for approximating column-sparse integer programs, parametrized by the maximum L1 norm

From playlist HIM Lectures: Trimester Program "Combinatorial Optimization"

Video thumbnail

Alberto Del Pia: Proximity in concave integer quadratic programming

A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n∆ on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, n is the number of variables and ∆ denotes the maximum of the absolute va

From playlist Workshop: Tropical geometry and the geometry of linear programming

Video thumbnail

Represent a Discrete Function Using Ordered Pairs, a Table, and Function Notation

This video explains how to represent a discrete function given as points as ordered pairs, a table, and using function notation. http://mathispower4u.com

From playlist Introduction to Functions: Function Basics

Video thumbnail

Constantinos Daskalakis' Nevanlinna Prize Laudatio — Éva Tardos — ICM2018

The work of Constantinos Daskalakis Éva Tardos ICM 2018 - International Congress of Mathematicians © www.icm2018.org     Os direitos sobre todo o material deste canal pertencem ao Instituto de Matemática Pura e Aplicada, sendo vedada a utilização total ou parcial do conteúdo sem autorizaç

From playlist Special / Prizes Lectures

Video thumbnail

Trigonometry - Vocabulary of trigonometric functions

In this video will cover some of the basic vocabulary that you'll hear when working with trigonometric functions. Specifically we'll cover what is trigonometry, angles, and defining the trigonometric functions as ratios of sides. You'll hear these terms again as we dig deeper into the st

From playlist Trigonometry

Video thumbnail

Extremal theory of ordered graphs – Gábor Tardos – ICM2018

Combinatorics Invited Lecture 13.3 Extremal theory of ordered graphs Gábor Tardos Abstract: We call simple graphs with a linear order on the vertices ‘ordered graphs’. Turán-type extremal graph theory naturally extends to ordered graphs. This is a survey on the ongoing research in the ex

From playlist Combinatorics

Video thumbnail

Topics in Combinatorics lecture 7.4 --- The Marcus-Tardos theorem

We say that a permutation pi of {1,2,...,k} is contained in a permutation sigma of {1,2,...,n} if we can find k elements of {1,2,...,n} that are reordered by sigma in the way that pi reorders {1,2,...,k}. For instance, the permutation 2413 (meaning that 1 goes to 2, 2 goes to 4, 3 goes to

From playlist Topics in Combinatorics (Cambridge Part III course)

Video thumbnail

Short interview with László Lovász

0:11 Reaction to winning the Abel Prize? 1:08 Impact of the emergence of computers on your career? 3:56 Randomness in combinatorics and computer science. Why is the probabilistic method so powerful? Interview with László Lovász from the Abel Prize announcement 2021 by Alex Bellos. Thu

From playlist László Lovász

Video thumbnail

Adventures in Monotone Complexity - Mika Göös

Short talks by postdoctoral members Topic: Adventures in Monotone Complexity Speaker: Mika Göös Affiliation: Member, School of Mathematics Date: September 26, 2018 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

What is a Function?

What is a function? How do you use the vertical line test? Learn more about functions and determine if mappings, sets of ordered pairs, tables, or graphs are functions in this short algebra video. Need more math help? Check out our algebra and geometry lessons at katesmathlessons.com

From playlist Algebra 1

Related pages

Graph theory | Circuit complexity | Chromatic number | Polynomial-time approximation scheme | Ellipsoid method | Lovász number | Clique number | Complement graph | Counterexample