We consider the problem of computing market equilibria and show three results. (i) For exchange economies satisfying weak gross substitutability we analyze a simple discrete version of tâtonnement, and prove that it converges to an approximate equilibrium in polynomial time. This is the first polynomial-time approximation scheme based on a simple tâtonnement process. It was only recently shown, using vastly more sophisticated techniques, that an approximate equilibrium for this class of economies is computable in polynomial time. (ii) For Fisher’s model, we extend the frontier of tractability by developing a polynomial-time algorithm that applies well beyond the homothetic case and the gross substitutes case. (iii) For production economies, we obtain the first polynomial-time algorithms for computing an approximate equilibrium when the consumers ’ side of the economy satisfies weak gross substitutability and the producers’ side is restricted to positive production.

Abstract We report our experience in implementing UbiCrawler, a scalable distributed Web crawler, using the Java programming language. The main features of UbiCrawler are platform independence, linear scalability, graceful degradation in the presence of faults, a very effective assignment function (based on consistent hashing) for partitioning the domain to crawl, and more in general the complete decentralization of every task. The necessity of handling very large sets of data has highlighted some limitations of the Java APIs, which prompted the authors to partially reimplement them. Copyright © 2004 John Wiley & Sons, Ltd.

We show that for several natural classes of “structured” matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime p is as hard as computing its exact value. Results of this kind are well known for arbitrary matrices. However the techniques used do not seem to apply to “structured” matrices. Our approach is based on recent advances in the hidden number problem introduced by Boneh and Venkatesan in 1996 combined with some bounds of exponential sums motivated by the Waring problem in finite fields.

In this paper, we prove that bent functions can be precisely characterized in terms of a special class of strongly regular graphs, thus providing a positive answer to a question raised in the paper by A. Bernasconi and B. Codenotti (1999).

Several problems in digital logic can be conveniently approached in the spectral domain. In this paper we show that the Walsh spectrum of Boolean functions can be analyzed by looking at algebraic properties of a class of Cayley graphs associated with Boolean functions. We use this idea to investigate the Walsh spectrum of certain special functions.

In this paper we introduce a technique for developing efficient iterated local search procedures and we apply it to solve very large instances of the Euclidean Traveling Salesman Problem (TSP). This technique, which we call perturbation, uses global information on TSP instances to speed-up the computation and to improve the quality of the tours found by heuristic methods. The main idea is to escape from local optima by introducing perturbations in the problem instance rather than in the solution. The performance of our algorithms has been tested and compared with known methods. To this end, we have executed a number of experiments both on available benchmarks, for which the optimal tour length is known, and on randomly generated instances, for which the comparison is done with the Held-Karp lower bound. The experimental results, performed on up to 100,000 cities, show that our algorithms outperform the known methods for iterating local search for very large instances.

This paper provides the first systematic investigation of checking approximate numerical computations over subsets of the reals. In most cases, approximate checking is more challenging than exact checking. Problem conditioning, i.e., the measure of sensitivity of the output to slight changes in the input, and the presence of approximation parameters foil the direct transformation of many exact checkers to the approximate setting. Furthermore, approximate checking over the reals is complicated by the lack of nice finite field properties such as the existence of a samplable distribution which is invariant under addition or multiplication by a scalar. We overcome the above problems by using such techniques as testing and checking over similar but distinct distributions, using functions' random and downward self-reducibility properties, and taking advantage of the small variance of the sum of independent identically distributed random variables. We provide approximate checkers for a variety of computations, including matrix multiplication, linear system solution, matrix inversion, and computation of the determinant. We also present an approximate version of Beigel's trick and extend the approximate linear self tester/corrector of [8] and the trigonometric self-Tester/corrector of [5] to more general computations.

The authors discuss the development and implementation of an object-oriented experimental environment for global routing heuristics in VLSI layout design. This experimental environment has been implemented in both common lisp (with object-oriented extensions) and Smalltalk, providing a user-friendly graphical interface for problem input, output, interaction and modification of the heuristics. Several heuristics have been implemented, some of which use only local information, while others use global information concerning the instance of the problem. All heuristics seem to have good average case performance, and from the results it is concluded that, also on average, multi-turn routings do not provide a significant improvement over one-turn routings.>

A technique for reconfiguring a two-dimensional VLSI array with faulty cells is presented. A network flow model of the problem is used to provide an algorithm for connecting the functional cells of the array so that they simulate a fault-free array of smaller size. The interconnection wires are routed inside horizontal and vertical channels according to the Manhattan model. Experimental results indicate that the algorithm has good performance in practice.>