Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Edward Hirsch:

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?

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 >>>

TR16-119 | 1st August 2016
Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

On the Limits of Gate Elimination

Revisions: 1

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 >>>

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: 1

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 >>>

TR14-050 | 21st March 2014
Edward Hirsch, Dmitry Sokolov

On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

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 >>>

TR11-091 | 20th May 2011
Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

Optimal heuristic algorithms for the image of an injective function

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 >>>

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

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 >>>

TR07-117 | 8th November 2007
Edward Hirsch, Dmitry Itsykson

An infinitely-often one-way function based on an average-case assumption

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 >>>

TR06-046 | 1st April 2006
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

A Complete Public-Key Cryptosystem

Comments: 1

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 >>>

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

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 >>>

TR05-076 | 2nd July 2005
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

Time hierarchies for cryptographic function inversion with advice

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 >>>

TR05-006 | 28th December 2004
Edward Hirsch, Sergey I. Nikolenko

Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Comments: 1

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 >>>

TR04-041 | 18th May 2004
Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

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 >>>

TR03-072 | 15th September 2003
Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

Algorithms for SAT based on search in Hamming balls

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 >>>

TR03-012 | 21st January 2003
Edward Hirsch, Arist Kojevnikov

Several notes on the power of Gomory-Chvatal cuts

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 >>>

TR01-103 | 14th December 2001
Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

Complexity of semi-algebraic proofs

Revisions: 3

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 >>>

TR01-012 | 4th January 2001
Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

Algorithms for SAT and Upper Bounds on Their Complexity

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 >>>

TR01-011 | 21st January 2001
Dima Grigoriev, Edward Hirsch

Algebraic proof systems over formulas

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 >>>

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

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 >>>

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

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 >>>

TR99-036 | 6th September 1999
Edward Hirsch

A New Algorithm for MAX-2-SAT

Revisions: 2

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 >>>

ISSN 1433-8092 | Imprint