Careers360 Logo
ask-icon
share
    Compare

    Quick Facts

    Medium Of InstructionsMode Of LearningMode Of Delivery
    EnglishSelf StudyVideo and Text Based

    Courses and Certificate Fees

    Certificate AvailabilityCertificate Providing Authority
    yesIIT Kanpur

    The Syllabus

    • Introduction I
    • Introduction II
    • Lower bound for circuits
    • Lower bound for formulas
    • Khrapchenko's theorem

    • Proof of Khrapchenko's Theorem
    • Applications of Khrapchenko's Theorem
    • Nechiporuk's Theorem
    • Applications of Nechiporuk's Theorem
    •  Subbotovskaya's Theorem I

    • Subbotovskaya's Theorem II
    • Applications of Subbotovskaya's Theorem
    • Upper and Lower Bounds on the Andreev Function
    • Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) I
    • Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) II

    • Circuits for Addition Ripple Adder and Carry Lookahead Adder
    • Circuits for Addition Parallel Prefix Sum Method
    • Circuits for Iterated Addition and Multiplication
    • Bounded Depth Circuit Classes
    • Basic Circuit for Division using NewtonRaphson Method

    • Division in NC1 (Beame, Cook, Hoover Theorem) I
    • Division in NC1 (Beame, Cook, Hoover Theorem) II
    • Division in NC1 (Beame, Cook, Hoover Theorem) III
    • Division in NC1 (Beame, Cook, Hoover Theorem) IV
    • Division in NC1 (Beame, Cook, Hoover Theorem) V

    • Division in NC1 (Beame, Cook, Hoover Theorem) VI
    • Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes I
    • Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes II
    • Reducing Circuit Depth
    • P is in P/poly

    • Discussion on Circuit Lower Bounds for Bounded Depth Circuit Classes
    • Monotone Circuit Lower Bound for Clique (Razborov's Theorem) I
    • Monotone Circuit Lower Bound for Clique (Razborov's Theorem) II
    • Monotone Circuit Lower Bound for Clique (Razborov's Theorem) III
    • Monotone Circuit Lower Bound for Clique (Razborov's Theorem) IV

    • Monotone Circuit Lower Bound for Clique (Razborov's Theorem) V
    • Monotone Circuit Lower Bound for Clique (Razborov's Theorem) VI
    • Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) I
    • Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) II
    • Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) III

    • Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) I
    • Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) II
    • Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) III
    • Proof of Hastad's Switching Lemma I
    • Proof of Hastad's Switching Lemma II

    • Communication Complexity of a Function
    • Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) I
    • Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) II
    • Bounded Width Branching Programs = NC1 (Barrington's Theorem) I
    • Bounded Width Branching Programs = NC1 (Barrington's Theorem) II

    • Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) I
    • Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) II
    • Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) I
    • Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) II
    •  ValiantVazirani Theorem I

    • ValiantVazirani Theorem II
    • Natural Proof Barrier (RazborovRudich Theorem) I
    • Natural Proof Barrier (RazborovRudich Theorem) II
    • Pseudorandom Function Generator by Goldreich, Goldwasser and Micali I
    • Pseudorandom Function Generator by Goldreich, Goldwasser and Micali II

    Instructors

    Articles

    Student Community: Where Questions Find Answers

    Ask and get expert answers on exams, counselling, admissions, careers, and study options.