The complexity of the travelling repairman problem
The difference and truth-table hierarchies for NP
The discrete logarithm problem over prime fields: the safe prime case. The Smart attack, non-canonical lifts and logarithmic derivatives
We connect the discrete logarithm problem over prime fields in the safe prime case to the logarithmic derivative.
The limiting common distribution of two leaf heights in a random binary tree
The observational predicate calculus and complexity of computations (Preliminary communication)
The Orthogonal Convex Skull Problem.
The partial inverse minimum cut problem with L1-norm is strongly NP-hard
The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L1-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional bound...
The problems of complexity of almost context-free languages [Abstract of thesis]
The reduction of binary trees by means of an input-restricted deque
The role of rudimentary relations in complexity theory
The size of triangulations supporting a given link.
The Structure and complexity of interactive zero-knowledge proofs
The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based...
The Union of Balls and Its Dual Shape.
The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.
The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces.
Theorem proving through depth-first test
Threshold circuits for iterated matrix product and powering
Threshold Circuits for Iterated Matrix Product and Powering
The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension matrices with integer or rational entries is studied. We call these two problems and , respectively, for short. We prove that: (i) For , does not belong to , unless .newline (ii) For stochastic matrices : belongs to while, for , does not belong to , unless . (iii) For any k, belongs to .
Tiling Polygons with Parallelograms.