Péter Hajnal

I&C Journal 2022 Journal Article

Nearest neighbor representations of Boolean functions

• Péter Hajnal
• Zhihao Liu
• György Turán

A nearest neighbor representation of a Boolean function is a set of positive and negative prototypes in R n such that the function has value 1 on an input iff the closest prototype is positive. For k-nearest neighbor representation the majority classification of the k closest prototypes is considered. The nearest neighbor complexity of a Boolean function is the minimal number of prototypes needed to represent the function. We give several bounds for this measure. Separations are given between the cases when prototypes can be real or are required to be Boolean. The complexity of parity is determined exactly. An exponential lower bound is given for mod 2 inner product, and a linear lower bound is given for its k-nearest neighbor complexity. The results are proven using connections to other models such as polynomial threshold functions over { 1, 2 }. We also discuss some of the many open problems arising.

FOCS Conference 1988 Conference Paper

Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs

• Elias Dahlhaus
• Péter Hajnal
• Marek Karpinski

G. A. Dirac's classical theorem (1952) asserts that if every vertex of a graph G on n vertices has degree at least n/2, the G has a Hamiltonian cycle. A fast parallel algorithm on a concurrent-read-exclusive-write parallel random-access machine (CREW PRAM) is given to find a Hamiltonian cycle in such graphs. The algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. It works in O(log/sup 4/n) parallel time and uses linear number of processors on a CREW PRAM. It is also proved that a perfect matching in dense graphs can be found in NC/sup 2/. The cost of improved time is a quadratic number of processors. It is also proved that finding an NC algorithm for perfect matching in slightly less dense graphs is as hard as the same problem for all graphs, and the problem of finding a Hamiltonian cycle becomes NP-complete. >

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