All reports by Author Edward Hirsch:

__
TR24-072
| 11th April 2024
__

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch#### Tropical proof systems

Revisions: 1

__
TR23-016
| 22nd February 2023
__

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals#### Proving Unsatisfiability with Hitting Formulas

__
TR22-176
| 1st December 2022
__

Yaroslav Alekseev, Edward Hirsch#### The power of the Binary Value Principle

__
TR19-142
| 23rd October 2019
__

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret#### Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

Revisions: 1

__
TR16-119
| 1st August 2016
__

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov#### On the Limits of Gate Elimination

Revisions: 1

__
TR15-166
| 17th October 2015
__

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov#### A better-than-$3n$ lower bound for the circuit complexity of an explicit function

Revisions: 2

__
TR14-050
| 21st March 2014
__

Edward Hirsch, Dmitry Sokolov#### On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

__
TR11-091
| 20th May 2011
__

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal#### Optimal heuristic algorithms for the image of an injective function

__
TR10-193
| 5th December 2010
__

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal#### On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

__
TR07-117
| 8th November 2007
__

Edward Hirsch, Dmitry Itsykson#### An infinitely-often one-way function based on an average-case assumption

__
TR06-046
| 1st April 2006
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### A Complete Public-Key Cryptosystem

Comments: 1

__
TR05-102
| 13th September 2005
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

__
TR05-076
| 2nd July 2005
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### Time hierarchies for cryptographic function inversion with advice

__
TR05-006
| 28th December 2004
__

Edward Hirsch, Sergey I. Nikolenko#### Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Comments: 1

__
TR04-041
| 18th May 2004
__

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson#### Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

__
TR03-072
| 15th September 2003
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Algorithms for SAT based on search in Hamming balls

__
TR03-012
| 21st January 2003
__

Edward Hirsch, Arist Kojevnikov#### Several notes on the power of Gomory-Chvatal cuts

__
TR01-103
| 14th December 2001
__

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik#### Complexity of semi-algebraic proofs

Revisions: 3

__
TR01-012
| 4th January 2001
__

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov#### Algorithms for SAT and Upper Bounds on Their Complexity

__
TR01-011
| 21st January 2001
__

Dima Grigoriev, Edward Hirsch#### Algebraic proof systems over formulas

__
TR00-037
| 26th May 2000
__

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith#### New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

__
TR00-019
| 20th March 2000
__

Edward Hirsch#### Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search

__
TR99-036
| 6th September 1999
__

Edward Hirsch#### A New Algorithm for MAX-2-SAT

Revisions: 2

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>

Yaroslav Alekseev, Edward Hirsch

The (extended) Binary Value Principle (eBVP, the equation $\sum x_i 2^{i-1} = -k$ for $k > 0$

and in the presence of $x_i^2=x_i$) has received a lot of attention recently, several lower

bounds have been proved for it [Alekseev et al 20, Alekseev 21, Part and Tzameret 21].

Also ...
more >>>

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

We introduce the `binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>>

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate ... more >>>

Edward Hirsch, Dmitry Sokolov

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>

Edward Hirsch, Dmitry Itsykson

We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We prove a time hierarchy theorem for inverting functions

computable in polynomial time with one bit of advice.

In particular, we prove that if there is a strongly

one-way function, then for any k and for any polynomial p,

there is a function f computable in linear time

with one ...
more >>>

Edward Hirsch, Sergey I. Nikolenko

Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We present a simple randomized algorithm for SAT and prove an upper

bound on its running time. Given a Boolean formula F in conjunctive

normal form, the algorithm finds a satisfying assignment for F

(if any) by repeating the following: Choose an assignment A at

random and ...
more >>>

Edward Hirsch, Arist Kojevnikov

We prove that the Cutting Plane proof system based on

Gomory-Chvatal cuts polynomially simulates the

lift-and-project system with integer coefficients

written in unary. The restriction on coefficients can be

omitted when using Krajicek's cut-free Gentzen-style extension

of both systems. We also prove that Tseitin tautologies

have short proofs in ...
more >>>

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

It is a known approach to translate propositional formulas into

systems of polynomial inequalities and to consider proof systems

for the latter ones. The well-studied proof systems of this kind

are the Cutting Planes proof system (CP) utilizing linear

inequalities and the Lovasz-Schrijver calculi (LS) utilizing

quadratic ...
more >>>

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

We survey recent algorithms for the propositional

satisfiability problem, in particular algorithms

that have the best current worst-case upper bounds

on their complexity. We also discuss some related

issues: the derandomization of the algorithm of

Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani

Lemma, and random walk ...
more >>>

Dima Grigoriev, Edward Hirsch

We introduce two algebraic propositional proof systems F-NS

and F-PC. The main difference of our systems from (customary)

Nullstellensatz and Polynomial Calculus is that the polynomials

are represented as arbitrary formulas (rather than sums of

monomials). Short proofs of Tseitin's tautologies in the

constant-depth version of F-NS provide ...
more >>>

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

The maximum 2-satisfiability problem (MAX-2-SAT) is:

given a Boolean formula in $2$-CNF, find a truth

assignment that satisfies the maximum possible number

of its clauses. MAX-2-SAT is MAXSNP-complete.

Recently, this problem received much attention in the

contexts of approximation (polynomial-time) algorithms

...
more >>>

Edward Hirsch

During the past three years there was an explosion of algorithms

solving MAX-SAT and MAX-2-SAT in worst-case time of the order

c^K, where c<2 is a constant, and K is the number of clauses

in the input formula. Such bounds w.r.t. the number of variables

instead of the number of ...
more >>>

Edward Hirsch

Recently there was a significant progress in

proving (exponential-time) worst-case upper bounds for the

propositional satisfiability problem (SAT).

MAX-SAT is an important generalization of SAT.

Several upper bounds were obtained for MAX-SAT and

its NP-complete subproblems.

In particular, Niedermeier and Rossmanith recently

...
more >>>