11 citations · 45 across the 40 of their papers we have counts for
49 papers
Separations with Immunity Relative to a Random Oracle in Computational Complexity
Gabriel Istrate
Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering \emph{strong s…
On the Cauchy-Hamel Continuity of Real Functions
Gabriel Istrate
We compare several "pathological" notions of continuity that make every additive function continuous. Our goal is to determine which of these notions is best behaved and deserves t…
Hypersphere-Based Restricting Conditions for Colorings of the Euclidean Space
Gabriel Istrate, Catalin Zara
We study colorings of the Euclidean space constrained by \emph{hypersphere forcing conditions}: if an admissible hypersphere, , centered at a point and of radius co…
On multiagent online problems with predictions
Gabriel Istrate, Cosmin Bonchis, Victor Bogdan
We study the power of (competitive) algorithms with predictions in a multiagent setting. We introduce a two predictor framework, that assumes that agents use one predictor for thei…
Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
Gabriel Istrate
Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-s…
A Language-Theoretic Approach to the Heapability of Signed Permutations
Gabriel Istrate
We investigate a signed version of the Hammersley process, a discrete process on words related to a property of integer sequences called heapability (Byers et al., ANALCO 2011). Th…