I am looking for partners in the research area.

I am looking for partners interested in the Horizon Europe Call.

I am looking for partners for the Horizon Europe research area.

I am looking for laboratory facilities in the research/application area.

Algorithm Theory

Research keywords: · algorithms · complexity theory · preference-based pairings · fair assignment · parametric complexity theory · safety measure · Nash equilibrium · matroid · greedoid · quantum algorithms · QUBO
Horizon Europe keywords: · Artificial Intelligence and Robotics · Increased cybersecurity · Next generation computing and data technologies · Next Generation Internet

Faculty of Electrical Engineering and Informatics Department of Computer Science and Information Theory

Introduction of the Research Group

The work of this research group contributes to Combinatorial algorithms, Classical and quantum algorithms, complexity theory and parametric complexity approaches. Within this, e.g. social choices, fair assignments, stable and popular pairings, examining the reliability of networks using combinatorial and game theory methods. Investigation of different quantum approaches (algorithm, QUBO, quantum wandering). Logical and declarative programming.
Achievements Publications Awards Journals Projects Conferences

Achievements

- We have achieved several results in the field of fair assignment: among others, we have proved that the search for an envy-free allocation for 3 agents is an NP-complete task (thus answering a question open for 5 years), while the search for proportional allocation can be solved with a polynomial-time algorithm
- We also went around the latter question in the case of a general number of agents, mapping its parametric complexity and approximability .
- We examined the multi-parameter complexity of the stable pairing problem in the case where we can prescribe the coverage of certain agents: for each combination of five examined parameters, the complexity of the problem was determined.
- We have even dealt with the problem of popular pine forests, and in addition to providing efficient exact and approximation algorithms, we have also demonstrated a number of difficulty results.
- We have demonstrated a new result by which the previously known matroid theory methods for measuring the reliability of networks with game theory tools have been extended to a broader class of greedoids than matroids .
- Among quantum algorithms, we investigated the limits of the application of the Fourier transform to certain algebraic problems.
- We have dealt with a kind of use of quantum algorithms in machine learning, showing that a method proposed by others does not offer many advantages over classical methods, also, how to embed classic problems in the D-Wave (former) quantum computer, using the QUBO (quantum unconstrained binary optimization).

Publications

N/A

Awards

2017,OTKA (TMIT-tel)

Journals

ACTA CYBERNETICA
LINEAR ALGEBRA AND ITS APPLICATIONS
SIAM JOURNAL ON COMPUTING
ALGORITHMICA
MATHEMATICAL PROGRAMMING

Projects

N/A

Conferences

Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications;
Integer programming and combinatorial optimization: International Conference, IPCO;
Algorithmic game theory: International Symposium, SAGT;
International Conference on Algorithmic Decision Theory, ADT;