János Komlós

SODA Conference 1996 Conference Paper

Matching Nuts and Bolts in O(n log n) Time (Extended Abstract)

• János Komlós
• Yuan Ma
• Endre Szemerédi

FOCS Conference 1992 Conference Paper

Halvers and Expanders

• Miklós Ajtai
• János Komlós
• Endre Szemerédi

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches. >

FOCS Conference 1988 Conference Paper

Effect of Connectivity in Associative Memory Models (Preliminary Version)

• János Komlós
• Ramamohan Paturi

The authors investigate how good connectivity properties translate into good error-correcting behavior in sparse networks of threshold elements. They determine how the eigenvalues of the interconnection graph (which in turn reflect connectivity properties) relate to the quantities, number of items stored, amount of error-correction, radius of attraction, and rate of convergence in an associative memory model consisting of a sparse network of threshold elements or neurons. >

STOC Conference 1987 Conference Paper

Deterministic Simulation in LOGSPACE

• Miklós Ajtai
• János Komlós
• Endre Szemerédi

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n ) 2 / log log n passes the test with probability at least 1/ n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size. The sequence that we construct does not really depend on the test, in the sense that a polynomial family of sequences is constructed so that at least one of them passes any test. This family is the same even if the test is allowed to use an oracle of polynomial size, and it can be constructed in LOGSPACE (without using an oracle).

STOC Conference 1986 Conference Paper

Deterministic Selection in O(log log N) Parallel Time

• Miklós Ajtai
• János Komlós
• William L. Steiger
• Endre Szemerédi

STOC Conference 1986 Conference Paper

Two lower bounds for branching programs

• Miklós Ajtai
• László Babai
• Péter Hajnal
• János Komlós
• Pavel Pudlák
• Vojtech Rödl
• Endre Szemerédi
• György Turán

FOCS Conference 1984 Conference Paper

Linear Verification for Spanning Trees

• János Komlós

Given a rooted tree with values associated with the n vertices and a set A of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only 5n + n log [(|A|+n)/n] comparisons. This leads to a spanning tree verification algorithm using O(n+e) comparisons in a graph with n vertices and e edges. No implementation is offered.

STOC Conference 1983 Conference Paper

An O(n log n) Sorting Network

• Miklós Ajtai
• János Komlós
• Endre Szemerédi

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n). A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. Unfortunately, while one can halve a set using only 0(n) comparisons, this cannot be done in less than log n (parallel) time, and it is known that a halving network needs (½)n log n comparisons. It is possible, however, to construct a network of 0(n) comparisons which halves in constant time with high accuracy. This procedure (ε-halving) and a derived procedure (ε-nearsort) are described below, and our sorting network will be centered around these elementary steps.

FOCS Conference 1983 Conference Paper

Hash Functions for Priority Queues

• Miklós Ajtai
• Michael L. Fredman
• János Komlós

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

FOCS Conference 1982 Conference Paper

Storing a Sparse Table with O(1) Worst Case Access Time

• Michael L. Fredman
• János Komlós
• Endre Szemerédi

We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.