How to sample from N and from Sigma*, and why

           Stavros Konstantinidis

Consider a hard NFA problem like universality, or equivalence. We want a PTIME randomized test to give us information about the hard problem via sampling words from Sigma*. Similarly, for a given hard Diophantine equation, we want to sample integers from N and test whether the equation has any solution. Typically, sampling relies on the uniform probability distribution, but there is no uniform distribution on N, or on Sigma*. What is a good distribution D? How to sample from D in PTIME? Such questions are investigated in the framework of PRAX algorithms (Polynomial Randomized ApproXimation algorithms). Which hard problems have a good PRAX algorithm? 

Presented on November 4, 2026, at EAADS, Kosice, Slovakia

This exposition is based on recent and ongoing research with Pantelis Andreou, Mitja Mastnak, Nelma Moreira,  Argyrios Papageorgiou, Rogerio Reis, Juraj Sebej, and Taylor Smith.