ﻻ يوجد ملخص باللغة العربية
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $mathsf{BPTIME}$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows. 1. We build on techniques developed to prove hierarchy theorems for probabilistic time with advice (Fortnow and Santhanam, FOCS 2004) to construct the first unconditional pseudorandom generator of polynomial stretch computable in pseudodeterministic polynomial time (with one bit of advice) that is secure infinitely often against polynomial-time computations. As an application of this construction, we obtain new results about the complexity of generating and representing prime numbers. 2. Oliveira and Santhanam (STOC 2017) established unconditionally that there is a pseudodeterministic algorithm for the Circuit Acceptance Probability Problem ($mathsf{CAPP}$) that runs in sub-exponential time and is correct with high probability over any samplable distribution on circuits on infinitely many input lengths. We show that improving this running time or obtaining a result that holds for every large input length would imply new time hierarchy theorems for probabilistic time. In addition, we prove that a worst-case polynomial-time pseudodeterministic algorithm for $mathsf{CAPP}$ would imply that $mathsf{BPP}$ has complete problems. 3. We establish an equivalence between pseudodeterministic construction of strings of large $mathsf{rKt}$ complexity (Oliveira, ICALP 2019) and the existence of strong hierarchy theorems for probabilistic time. More generally, these results suggest new approaches for designing pseudodeterministic algorithms for search problems and for unveiling the structure of probabilistic time.
Boolean functions can be represented in many ways including logical forms, truth tables, and polynomials. Additionally, Boolean functions have different canonical representations such as minimal disjunctive normal forms. Other canonical representatio
We propose models for lobbying in a probabilistic environment, in which an actor (called The Lobby) seeks to influence voters preferences of voting for or against multiple issues when the voters preferences are represented in terms of probabilities.
Let $mathcal{C}$ and $mathcal{D}$ be hereditary graph classes. Consider the following problem: given a graph $Ginmathcal{D}$, find a largest, in terms of the number of vertices, induced subgraph of $G$ that belongs to $mathcal{C}$. We prove that it c
In the design of probabilistic timed systems, bounded requirements concerning behaviour that occurs within a given time, energy, or more generally cost budget are of central importance. Traditionally, such requirements have been model-checked via a r
We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $epsilon$ in (0,1/3), the $epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ su