David Harvey, Markus Hittmeir · Research in Number Theory · 2022
Abstract Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers p such that $$p^r \mathrel {|}N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>p</mml:mi> <mml:mi>r</mml:mi> </mml:msup> <mml:mo>|</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> in time $$O(N^{1/4r+\epsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> <mml:mi>r</mml:mi> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for any $$\epsilon > 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> . For example, the algorithm can be used to test squarefreeness of N in time $$O(N^{1/8+\epsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>8</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> ; previously, the best rigorous bound for this problem was $$O(N^{1/6+\epsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>6</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , achieved via the Pollard–Strassen method.
Cited by 5Open access
Jingyang Zhao, Mingyu Xiao · Theoretical Computer Science · 2024
Cited by 3
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai · 2019
We present a deterministic dynamic algorithm for maintaining a (1+ε)f-approximate minimum cost set cover with O(f log(Cn)/ε^2) amortized update time, when the input set system is undergoing element insertions and deletions. Here, n denotes the number of elements, each element appears in at most f sets, and the cost of each set lies in the range [1/C, 1]. Our result, together with that of Gupta~et~al.~[STOC'17], implies that there is a deterministic algorithm for this problem with O(f log(Cn)) amortized update time and O(min(log n, f)) -approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only O(log (Cn)) away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was O(f^2), which was due to Bhattacharya~et~al.~[ICALP`15]. In contrast, the only result that guaranteed O(f) -approximation was obtained very recently by Abboud~et~al.~[STOC`19], who designed a dynamic algorithm with (1+ε)f-approximation ratio and O(f^2 log n/ε) amortized update time. Besides the extra O(f) factor in the update time compared to our and Gupta~et~al.'s results, the Abboud~et~al.~algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. This approach was pursued previously by Bhattacharya~et~al.~and Gupta~et~al., but not in the recent paper by Abboud~et~al. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed.
Cited by 19
Yoshinori Ohno, Kenji Nagata, Tatsu Kuwatani et al. · Journal of the Physical Society of Japan · 2012
We propose a deterministic algorithm for image restoration using a nonlinear Markov random field (MRF) model. Recent advances in measurement techniques allow us to obtain a large quantity of imaging data in various natural science fields. These data are often exposed to observation noise. For the removal of noise from imaging data, we use an MRF model, in which the Bayesian inference framework enables us to estimate hyperparameters through free-energy minimization. When a nonlinear function represents an observation process, a Markov chain Monte Carlo (MCMC) method is often used for image restoration. An MCMC method retains nonlinearity, but it is a probabilistic algorithm, which increases computational cost. The proposed deterministic algorithm linearizes the observation process to achieve more efficient hyperparameter estimation and image restoration. We also applied the proposed algorithm to artificial images to show its efficiency.
Cited by 6
Dariusz R. Kowalski, Dominik Pająk · arXiv (Cornell University) · 2022
When facing a very large stream of data, it is often desirable to extract most important statistics online in a short time and using small memory. For example, one may want to quickly find the most influential users generating posts online or check if the stream contains many identical elements. In this paper, we study streams containing insertions and deletions of elements from a possibly large set $N$ of size $|N| = n$, that are being processed by online deterministic algorithms. At any point in the stream the algorithm may be queried to output elements of certain frequency in the already processed stream. More precisely, the most frequent elements in the stream so far. The output is considered correct if the returned elements it contains all elements with frequency greater than a given parameter $φ$ and no element with frequency smaller than $φ-ε$. We present an efficient online deterministic algorithm for solving this problem using $O(\min(n, \frac{polylog(n)}ε))$ memory and $O(polylog(n))$ time per processing and outputting an element. It is the first such algorithm as the previous algorithms were either randomized, or processed elements in substantially larger time $Ω(\min(n, \frac{\log n}ε))$, or handled only insertions and required two passes over the stream (i.e., were not truly online). Our solution is almost-optimally scalable (with only a polylogarithmic overhead) and does not require randomness or scanning twice through the stream. We complement the algorithm analysis with a lower bound $Ω(\min(n, \frac{1}ε))$ on required memory.
Cited by 0Open access
Lee, Changryeol · Zenodo (CERN European Organization for Nuclear Research) · 2026
The P versus NP problem asks whether every problem in NP, whose membership can be verified in polynomial time given a suitable certificate, can be decided by a deterministic Turing machine in polynomial time. In this paper, we present a proof that P = NP by constructing a deterministic polynomial-time algorithm for NP problems based on a graph-based computation framework.We introduce a structured computation model in which the transitions of a deterministic Turing machine are incrementally realized in the corresponding computation graph via edge extensions. Each extension step enforces a local feasibility condition that preserves consistency with valid NP verification paths across all possible certificates, ensuring that the maintained computation graph remains feasible at every stage. The total number of extension steps is polynomially bounded in the input size, and each step can be verified in polynomial time.As a result, the entire graph construction process runs in deterministic polynomial time and decides NP problems without enumerating certificates. This provides a direct and constructive resolution of the P versus NP question. Our result has significant implications for cryptography, combinatorial optimization, and artificial intelligence, where NP-complete problems play a central role.
Cited by 0Open access
Bala Kalyanasundaram, Kirk Pruhs · Lecture notes in computer science · 1996
Cited by 18
2008
Software-based active replication is expensive in terms of performance overhead. Multithreading can help improve performance; however, thread scheduling is a source of nondeterminism in replica behavior. This paper presents a Preemptive Deterministic Scheduling (PDS) algorithm for ensuring deterministic replica behavior while preserving concurrency. Threads are synchronized only on updates to the shared state. A replica execution is broken into a sequence of rounds, and in a round each thread can acquire up to two mutexes. When a new round fires, all threads ’ mutex requests are known; thus, it is possible to form a deterministic scheduling of mutex acquisitions in the round. No inter-replica communication is required. The algorithm is formally specified, and the proposed formalism is used to prove its correctness. Failure behavior and performance of a PDS algorithm’s implementation are evaluated in a triplicated system and compared with two existing solutions: nonpreemptive deterministic schedulers and the Loose Synchronization Algorithm (LSA) proposed by the authors in an earlier paper. The results show that PDS outperforms nonpreemptive deterministic schedulers. Compared with LSA, PDS has lower throughput; however, it provides additional benefits in terms of system dependability and, hence, can be considered as a trade-off between performance and dependability. These characteristics are investigated with fault injection. 1
Cited by 0
Edward A. Hirsch · 1998
How can we find any satisfying assignment for a Boolean formula that has many satisfying assignments ? There exists an obvious randomized algorithm for solving this problem: one can just pick an assignment at random and check the truth value of the formula for this assignment, this is iterated until a satisfying assignment occurs. Does there exist a polynomial-time deterministic algorithm that solves the same problem? This paper presents such an algorithm and shows that its worst-case running time is linear when input formulas are in k-CNF and a fraction of satisfying assignments (among all possible assignments) is greater than a constant. This algorithm is almost the same as the algorithm proposed by Monien and Speckenmeyer (and independently by Dantsin) in the early 1980s for less than 2 steps 3-SAT decision. Another
Cited by 0
Chao Yu Chiu · CERN Document Server (European Organization for Nuclear Research) · 2001
An algorithm was developed for beam envelope matching with fixed geometry, taking into account the full order behavior of the quadrupoles and their compounded effects.In the present approach an algorithm was employed to systematically reduce the overall dimensionality of the problem.This resulted in two algebraic systems that are independent but can be solved in tandem.At the numerical level these 2 reduced systems are input to an equation solver in Mathematica 4.0 based on Grbner-basis techniques, capable of providing global solutions to such algebraic systems.This has resulted in a robust and effective algorithm for on-line optical beam envelope matching.The global nature of the algorithm also may point to possible deficiencies in the optical system configuration.An on-line high precision transfer matrix measurement program was developed in conjunction to provide input to this algorithm.Preliminary on-line testing on the CEBAF accelerator has positively demonstrated the effectiveness of this method.
Cited by 0Open access
Anthony Don, Nicolas Hanusse · HAL (Le Centre pour la Communication Scientifique Directe) · 2006
International audience
Cited by 0
Lin Chen, Yijin Zhang, Kehao Wang et al. · IEEE Transactions on Wireless Communications · 2022
We formulate and investigate the problem of distributed channel rendezvous in collision-prone wireless networks. Existing researches on this topic are mainly devoted to designing channel hopping sequences, each pair of which can overlap on a common channel within bounded delay. However, this overlap-based canonical rendezvous design does not take into account channel collision, which may render existing rendezvous algorithms fail to achieve bounded delay in collision-prone environment. Motivated by this observation, we formulate and investigate the collision-aware channel rendezvous problem in a generic scenario, where a collision occurs if more than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$C$ </tex-math></inline-formula> packets overlap in time on a same channel. Our generic formulation allows to model both the baseline single packet reception model with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$C=1$ </tex-math></inline-formula> and the more sophisticated multiple packet reception model with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$C > 1$ </tex-math></inline-formula> . We further abstract the collision-aware rendezvous problem as the problem of constructing a robust rendezvous system. We establish the theoretical limit of the problem, guided by which we design a collision-resilient distributed rendezvous algorithm with truly bounded rendezvous delay. We then demonstrate the performance of our rendezvous algorithm both analytically and numerically.
Cited by 4
Songhwai Oh · 2011
The data association problem appears in many applications and is considered as the most challenging problem in intelligent systems. In this paper, we consider the Bayesian formulation of data association problems and present a deterministic polynomial-time approximation algorithm with guaranteed error bounds using correlation decay from statistical physics. We then show that the proposed algorithm naturally partitions a complex problem into a set of local problems and develop a distributed version of the algorithm. The performance of the proposed algorithm is evaluated in simulation.
Cited by 2
Hongwei Jiao, Yongqiang Chen · Applied Mathematics and Computation · 2008
Cited by 8
Albertus Fuad, Edwin Zondervan, Meik B. Franke · Computer-aided chemical engineering/Computer aided chemical engineering · 2024
Cited by 0
Lee, Changryeol · Zenodo (CERN European Organization for Nuclear Research) · 2026
The P versus NP problem asks whether every language verifiable in polynomial time can also be decided in deterministic polynomial time. In this paper, we present a constructive proof that P = NP via a deterministic polynomial-time algorithm based on a graph-based computation framework.We introduce a model where edges correspond to deterministic Turing machine transitions. Because these execution steps formpaths sharing the initial edge, the total number of edges is polynomially bounded due to overlapping edges across the entire certificate space. By shifting the verification focus from searching over exponential certificates to incremental edge extensions through verification of their validity, we reduce the complexity of the verification process to polynomial size.A key feature of our approach is that each extension step enforces global consistency via a local in-feasibility trimmingtool. This mechanism systematically preserves consistent NP paths to the edge under verification, ensuring the graph remains globally feasible at every stage without explicit enumeration of certificates. Both extension and trimming steps are strictly bounded by a polynomial in the input size. Consequently, our construction decides NP problems in deterministic polynomial time, providing a direct resolution to the P versus NP question.
Cited by 0Open access
Guanfeng Liang, Nitin H. Vaidya · 2010
In this report, building on the deterministic multi-valued one-to-many Byzantine agreement (broadcast) algorithm in our recent technical report [2], we introduce a deterministic multi-valued all-to-all Byzantine agreement algorithm (consensus), with linear complexity per bit agreed upon. The discussion in this note is not self-contained, and relies heavily on the material in [2] - please refer to [2] for the necessary background.
Cited by 0
Omar Nagib, M. Saffman, K. Mølmer · Physical review. A/Physical review, A · 2025
Cited by 2
Efthymios Costa, Ioanna Papatsouma, Angelos Markos · arXiv (Cornell University) · 2026
Cluster analysis relates to the task of assigning objects into groups which ideally present some desirable characteristics. When a cluster structure is confined to a subset of the feature space, traditional clustering techniques face unprecedented challenges. We present an information theoretic framework that overcomes the problems associated with sparse data, allowing for joint feature weighting and clustering. Our proposal constitutes a competitive alternative to existing clustering algorithms for sparse data, as demonstrated through simulations on synthetic data. The effectiveness of our method is established by an application on a real-world genomics data set.
Cited by 0Open access
Bernard Chazelle · 2002
A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m /spl alpha/ log /spl alpha/), where /spl alpha/=/spl alpha/(m,n) is a functional inverse of Ackermann's function and n (resp. m) is the number of vertices (resp. edges). This improves on the previous, ten-year old bound of (roughly) O(m log log* m).
Cited by 32