Alexander Knop
S.E. Warschawski Assistant Professor
Research interests:
Proof complexity, structural complexity, algorithms, cryptography.

Papers, talks and posters

Conference Articles

Talks

  • Alexander Knop (in collaboration with Dmitry Itsykson).
    Hard Satisfiable Formulas for Splittings by Linear Combinations
    Theory and Practice of Satisfiability Solving, Oaxaca, Mexico, 2018
  • Alexander Knop.
    Branching Program Complexity of Canonical Search Problems and Proof Complexity of Formulas
    Proof Complexity Workshop, FLOC, Oxford, UK, 2018
  • Alexander Knop (in collaboration with Dmitry Itsykson and Dmitry Sokolov).
    Complexity of distributions and average-case hardness
    ISAAC 2016, Sydney, Australia, 2016
  • Alexander Knop (in collaboration with Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov).
    On the Limits of Gate Elimination,
    MFCS 2016, Krakow, Poland, 2016
  • Alexander Knop (in collaboration with Dmitry Itsykson and Dmitry Sokolov).
    Heuristic time hierarchies via hierarchies for sampling distributions,
    ISAAC 2015, Nagoya, Japan, 2015
  • Alexander Knop (in collaboration with Dmitry Itsykson and Dmitry Sokolov).
    Complexity of distributions and average-case hardness,
    ELC Mini Workshop, Tokyo, Japan, 03.12.2015
  • Alexander Knop.
    Circuit Lower Bounds for Average-Case MA,
    CSR 2015, Irkutsk, Russia, 2015.
  • Alexander Knop.
    Circuit Lower Bounds for Heuristic MA,
    Eighth International Conference on Computability, Complexity and Randomness (CCR 2013), Moscow, Russia, 2013.
  • Alexander Knop.
    Diophantine Hierarchy,
    Franco-Russian workshop on Algorithms, complexity and applications, Moscow, Russia, 2013.
  • Alexander Knop,
    Diophantine Hierarchy,
    Discrete Mathematics seminar, Saint Petersburg, 2011

    • Journal Articles

    Preprints

  • Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
    Reordering Rule Makes OBDD Proof Systems Stronger
    Electronic Colloquium on Computational Complexity (ECCC), volume 41, 2018
  • Sam Buss, Alexander Knop
    Strategies for Stable Merge Sorting
    CoRR, volume abs/1801.04641, 2018
  • Alexander Knop
    IPS-like Proof Systems Based on Binary Decision Diagrams
    Electronic Colloquium on Computational Complexity (ECCC), volume 179, 2017
  • Kamil Khadiev, Aliya Khadiev, Alexander Knop
    Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
    Electronic Colloquium on Computational Complexity (ECCC), volume 176, 2017
  • Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov
    On the Limits of Gate Elimination
    Electronic Colloquium on Computational Complexity (ECCC), volume 119, 2016
  • Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
    Complexity of Distributions and Average-case Hardness
    Electronic Colloquium on Computational Complexity (ECCC), volume 174, 2015
  • Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
    Heuristic time Hierarchies via Hierarchies for Sampling Distributions
    Electronic Colloquium on Computational Complexity (ECCC), volume 178, 2014
  • Alexander Knop
    Circuit Lower Bounds for Heuristic MA
    Electronic Colloquium on Computational Complexity (ECCC), volume 37, 2013