Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>

2-Opt is probably the most basic and widely used local search
heuristic for the TSP. This heuristic achieves amazingly good
results on "real world" Euclidean instances both with respect to
running time and approximation ratio. There are numerous
experimental studies on the performance of 2-Opt. However, the
theoretical knowledge about ... more >>>