Dmitry Itsykson

Available identifiers

zbMath Open itsykson.dmitry-mWikidataQ102360382 ScholiaQ102360382MaRDI QIDQ413275

List of research outcomes

Publication	Date of Publication	Type
Proof complexity of natural formulas via communication arguments	2023-07-12	Paper
Lower Bounds on OBDD Proofs with Several Orders	2022-12-08	Paper
Bounded-depth Frege complexity of Tseitin formulas for all graphs	2022-10-14	Paper
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs	2022-07-21	Paper
Computational and Proof Complexity of Partial String Avoidability	2022-03-14	Paper
Correction to: ``Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs	2022-01-03	Paper
Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs	2021-09-10	Paper
On tseitin formulas, read-once branching programs and treewidth	2021-08-03	Paper
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES	2021-01-29	Paper
https://portal.mardi4nfdi.de/entity/Q5121904	2020-09-22	Paper
Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.	2020-05-26	Paper
Resolution over linear equations modulo two	2019-11-06	Paper
On Tseitin formulas, read-once branching programs and treewidth	2019-10-22	Paper
Complexity of Distributions and Average-Case Hardness	2018-04-19	Paper
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables	2018-04-19	Paper
https://portal.mardi4nfdi.de/entity/Q4608614	2018-03-21	Paper
Hard satisfiable formulas for splittings by linear combinations	2017-11-15	Paper
Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms	2017-11-07	Paper
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles	2017-07-28	Paper
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions	2016-01-11	Paper
Resolution Complexity of Perfect Matching Principles for Sparse Graphs	2015-10-20	Paper
On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs	2014-12-22	Paper
Lower Bounds for Splittings by Linear Combinations	2014-10-14	Paper
Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP	2013-06-14	Paper
Optimal heuristic algorithms for the image of an injective function	2013-04-09	Paper
The complexity of inverting explicit Goldreich's function by DPLL algorithms	2013-04-09	Paper
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography	2012-12-07	Paper
On an optimal randomized acceptor for graph nonisomorphism	2012-05-04	Paper
https://portal.mardi4nfdi.de/entity/Q3113771	2012-01-23	Paper
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic	2011-12-16	Paper
Structural complexity of AvgBPP	2011-09-12	Paper
The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms	2011-06-17	Paper
An infinitely-often one-way function based on an average-case assumption	2010-09-01	Paper
Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms	2010-06-22	Paper
Structural Complexity of AvgBPP	2009-08-18	Paper
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies	2009-03-12	Paper
An Infinitely-Often One-Way Function Based on an Average-Case Assumption	2008-07-10	Paper
https://portal.mardi4nfdi.de/entity/Q3444802	2007-06-04	Paper
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas	2007-01-24	Paper
Automata, Languages and Programming	2005-08-24	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Dmitry Itsykson