We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e. the problem of assigning values to the variables in a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to the fundamental problems in computational complexity ... more >>>

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>>

In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we can find in ... more >>>

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem. more >>>

In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements ... more >>>

We consider minimum equivalent digraph (directed network) problem (also known as the strong transitive reduction), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest. more >>>

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>>

We give a new method for analysing the mixing time of a Markov chain using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ... more >>>

We consider the problem of traversing skew (unbalanced) Merkle trees and design an algorithm for traversing a skew Merkle tree in time O(log n/log t) and space O(log n (t/log t)), for any choice of parameter t\geq 2. This algorithm can be of special interest in situations when the exact ... more >>>

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times. more >>>

We prove upper and lower bounds for computing Merkle tree traversals, and display optimal trade-offs between time and space complexity of that problem. more >>>

We prove that the problems of minimum bisection on k-uniform hypergraphs are almost exactly as hard to approximate, up to the factor k/3, as the problem of minimum bisection on graphs. On a positive side, our argument gives also the first approximation algorithms for the problem of minimum bisection on ... more >>>

We prove approximation hardness of short symmetric instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3. We display also an explicit approximation lower bound for that problem. The bound two on the number of occurrences of literals in symmetric MAX-3SAT is ... more >>>

We study approximation hardness and satisfiability of bounded occurrence uniform instances of SAT. Among other things, we prove the inapproximability for SAT instances in which every clause has exactly 3 literals and each variable occurs exactly 4 times, and display an explicit approximation lower bound for this problem. We also ... more >>>

We improve a number of approximation lower bounds for bounded occurrence optimization problems like MAX-2SAT, E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching. more >>>

We prove that MAX-3SAT can be approximated in polynomial time within a factor 9/8 on random instances. more >>>

We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some intriguing and still open questions about the approximability status of that problem. Some connections to other optimization problems are also indicated. more >>>

We prove that the subdense instances of MAX-CUT of average degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary maximum constraint satisfaction problems (MAX-CSP) of the same average density have PTASs. Our results display for the first ... more >>>

We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across that partition. The method of solution depends on a new metric placement partitioning method which could be ... more >>>

This paper presents new results on parallel constructions of the length-limited prefix-free codes with the minimum redundancy. We describe an algorithm for the construction of length-limited codes that works in $O(L)$ time with $n$ processors for $L$ the maximal codeword length. We also describe an algorithm for a construction of ... more >>>

We give polynomial time approximation schemes for the problem of partitioning an input set of n points into a fixed number k of clusters so as to minimize the sum over all clusters of the total pairwise distances in a cluster. Our algorithms work for arbitrary metric spaces as well ... more >>>

In this paper we present some new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our ... more >>>

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error \epsilon n^r.We prove a new general paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, ... more >>>

We give improved trade-off results on approximating general minimum cost scheduling problems. more >>>

This paper studies the existence of efficient (small size) amplifiers for proving explicit inaproximability results for bounded degree and bounded occurrence combinatorial optimization problems, and gives an explicit construction for such amplifiers. We use this construction also later to improve the currently best known approximation lower bounds for bounded occurrence ... more >>>

Analysis of genomes evolving by inversions leads to a general combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. This combinatorial problem has a long history, and a number of other motivations. It was studied in a great detail ... more >>>

We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages of proving approximation hardness ... more >>>

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT-formulas, and linear equations ... more >>>

We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 is the bounded occurrence (degree) ... more >>>

We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. For the case of the ... more >>>

We give a polynomial time approximation scheme (PTAS) for dense instances of the NEAREST CODEWORD problem. more >>>

The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics ... more >>>

The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first polynomial time approximation ... more >>>

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree $k$-regular graphs for $3\le k\le 8,$ ... more >>>

We design a $0.795$ approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of $0.834$. more >>>

We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently known for the Max Cut problem on general graphs~\cite{GW95}. We consider a semidefinite relaxation of the Max Cut problem, round it using the random ... more >>>

We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant, improving the previous competitive ratios of 8 and $2e\approx ... more >>>

We show that deciding square-freeness of a sparse univariate polynomial over the integer and over the algebraic closure of a finite field is NP-hard. We also discuss some related open problems about sparse polynomials. more >>>

We survey some of the recent results on the complexity of recognizing n-dimensional linear arrangements and convex polyhedra by randomized algebraic decision trees. We give also a number of concrete applications of these results. In particular, we derive first nontrivial, in fact quadratic, randomized lower bounds on the problems like ... more >>>

We prove that the error-free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for the Las Vegas read-once branching programs. more >>>

Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in bounded degree graphs, like MIS, Node Cover and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by ... more >>>

We give the first polynomial time approximability characterization of dense weighted instances of MAX-CUT, and some other dense weighted NP-hard problems in terms of their empirical weight distributions. This gives also the first almost sharp characterization of inapproximability of unweighted 0,1 MAX-BISECTION instances in terms of their density parameter. more >>>

We survey some upper and lower bounds established recently on the sizes of randomized branching programs computing explicit boolean functions. In particular, we display boolean functions on which randomized read-once ordered branching programs are exponentially more powerful than deterministic or nondeterministic read-$k$-times branching programs for any $k=o(n/\!\log n)$. We investigate ... more >>>

We prove a number of improved inaproximability results, including the best up to date explicit approximation thresholds for MIS problem of bounded degree, bounded occurrences MAX-2SAT, and bounded degree Node Cover. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit ... more >>>

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is the problem of finding a tour of minimum length in a complete weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy $0more >>>

The bandwidth problem is the problem of enumerating the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications. There was not much known about approximation hardness of this problem ... more >>>

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new lower bound on Yao's randomized one-way communication complexity of certain boolean functions. It generalizes to some other common models of randomized branching ... more >>>

We introduce a model of a {\em randomized branching program} in a natural way similar to the definition of a randomized circuit. We exhibit an explicit boolean function $f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that: 1) $f_{n}$ can be computed by a polynomial size randomized ordered read-once branching program with a ... more >>>

The bandwidth problem is the problem of enumerating the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications and is known to be $NP$-hard, Papadimitriou 1976. There is not ... more >>>

We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard optimization problems. We indicate further some inherent limits for existence of such schemes for some other dense instances of the optimization problems. more >>>

The bandwidth problem is the problem of numbering the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and is known to be NP-complete Papadimitriou [Pa76]. Only few special cases of this problem are ... more >>>

We study dense instances of several covering problems. An instance of the set cover problem with $m$ sets is dense if there is $\epsilon>0$ such that any element belongs to at least $\epsilon m$ sets. We show that the dense set cover problem can be approximated with the performance ratio ... more >>>

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the general model of \emph{randomized computation trees} solving the \emph{Knapsack Problem}, and more generally \emph{Restricted Integer Programming}. This is the \emph{first nontrivial} lower bound proven for this model of computation. The method of the proof depends crucially on the new technique for ... more >>>

We extend the lower bounds on the depth of algebraic decision trees to the case of {\em randomized} algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, ... more >>>

We prove an exponential lower bound on the size of any fixed-degree algebraic decision tree for solving MAX, the problem of finding the maximum of $n$ real numbers. This complements the $n-1$ lower bound of Rabin \cite{R72} on the depth of algebraic decision trees for this problem. The proof in ... more >>>

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension of analog neural networks with the sigmoidal activation function $\sigma(y)=1/1+e^{-y}$ is bounded by a quadratic polynomial $O((lm)^2)$ in ... more >>>

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function $f_{n}$ for which we prove that: 1) $f_{n}$ can be computed by polynomial size randomized read-once ordered branching program with a small one-sided error; ... more >>>

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve ... more >>>

We consider strings which are succinctly described. The description is in terms of straight-line programs in which the constants are symbols and the only operation is the concatenation. Such descriptions correspond to the systems of recurrences or to context-free grammars generating single words. The descriptive size of a string is ... more >>>

In contrast to deterministic or nondeterministic computation, it is a fundamental open problem in randomized computation how to separate different randomized time classes (at this point we do not even know how to separate linear randomized time from ${\mathcal O}(n^{\log n})$ randomized time) or how to compare them relative to ... more >>>

The Steiner tree problem requires to find a shortest tree connection a given set of terminal points in a metric space. We suggest a better and fast heuristic for the Steiner problem in graphs and in rectilinear plane. This heuristic finds a Steiner tree at most 1.757 and 1.267 times ... more >>>

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, the VC Dimension of analog neural networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$ to be bounded by a quadratic polynomial in the ... more >>>