Article
Computer Science, Theory & Methods
Gordon Hoi, Frank Stephan
Summary: This paper introduces the Exact Satisfiability problem and its generalised form GiXSAT, proposing faster exact polynomial space algorithms for solving them at different time complexities. The improvements in solving G2XSAT, G3XSAT, and G4XSAT are significant, offering more efficient solutions under different time and space constraints.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Mathematics
Balazs Barany, Antti Kaenmaki
Summary: We present self-similar sets on a line that are not exponentially separated and do not generate any exact overlaps, showing that the exponential separation introduced by Hochman is insufficient to fully describe the theory.
ADVANCES IN MATHEMATICS
(2021)
Article
Mathematics, Applied
Enqiang Zhu, Pu Wu, Zehui Shao
Summary: This paper focuses on the design of exact algorithms for counting 3-colorings of a graph. The approach utilizes branch and reduce paradigm, as well as measure and conquer method. By designing two sets of measures and leveraging dynamic programming, an improved algorithm with a time complexity of O(1.588n) is obtained for the #3-COLORING problem.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Physics, Fluids & Plasmas
Patrice Koehl, Henri Orland
Summary: The study proposes an alternative method for solving the assignment problem using techniques adapted from statistical physics, demonstrating efficient performance in large-scale problems. Furthermore, a rapidly convergent method for handling degenerate assignment problems was discovered.
Article
Computer Science, Artificial Intelligence
K. Subramani, Piotr Wojciechowski
Summary: This paper discusses algorithms for finding read-once resolution refutations of unsatisfiable 2CNF formulas within the resolution refutation system. The study designs non-trivial, parameterized, and exact exponential algorithms for this problem and explores the computational complexity of finding a shortest read-once resolution refutation of a 2CNF formula.
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
(2022)
Article
Astronomy & Astrophysics
Robert J. Scherrer
Summary: We derive exact general solutions and corresponding first integrals for the evolution of a scalar field in a universe dominated by a background fluid. We find that different types of potentials lead to different evolution modes.
Article
Mathematics
Awad Abdelrahman, Mogtaba Mohammed, Osman O. O. Yousif, Murtada K. Elbashir
Summary: Nonlinear conjugate gradient methods are crucial for solving unconstrained optimization problems, but classical methods usually yield poor numerical results in practice. In this paper, the method of Fletcher and Reeves is enhanced in terms of numerical performance through a convexity modification on its coefficient, ensuring sufficient descent condition and global convergence.
JOURNAL OF MATHEMATICS
(2022)
Article
Physics, Multidisciplinary
Jordan C. Moodie, M. W. Long
Summary: An exact representation of the Baker-Campbell-Hausdorff formula as a power series in just one of the two variables is constructed, with closed form coefficients found in terms of hyperbolic functions. It is argued that truncating this exact series can provide a good approximation to the full expansion when the perturbative variable is small, improving upon existing formulae. Emphasis is given to the situation where one of the matrices is diagonal, leading to a particularly easy to use formula.
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
(2021)
Article
Astronomy & Astrophysics
Muhammad Asaduzzaman, Goksu Can Toga, Simon Catterall, Yannick Meurice, Ryo Sakai
Summary: We discuss the use of quantum simulation to study interacting relativistic fermions in (1 + 1) dimensions. The case of two flavors is particularly interesting and can be mapped to the Hubbard model. We derive the appropriate qubit Hamiltonians and compare classical simulation and quantum simulation results on different platforms.
Article
Mathematics, Applied
Nadiia Derevianko, Gerlind Plonka
Summary: This paper presents a new recovery procedure for extended exponential sums, utilizing classical Fourier coefficients to reconstruct the parameters and employing a stable iterative rational approximation algorithm. When a sufficiently large set of Fourier coefficients is available, the method can automatically detect the number of terms, multiplicities, and parameters of the exponential sums.
ANALYSIS AND APPLICATIONS
(2022)
Article
Mathematics, Applied
Ting Li, Bin Wang
Summary: In this letter, explicit exponential algorithms for two-dimensional charged-particle dynamics with non-homogeneous electromagnetic fields are proposed and studied. The reformulation of the considered system allows for the derivation of three practical algorithms for charged-particle dynamics. The convergence of these algorithms is established and proved, and numerical tests demonstrate their excellent behavior and support the convergence result.
APPLIED MATHEMATICS LETTERS
(2023)
Article
Computer Science, Interdisciplinary Applications
Saliha Ferda Dogan, Ozlem Karsu, Firdevs Ulus
Summary: The study introduces an exact algorithm for solving biobjective integer programming problems and compares different strategies through experiments. Results show that some strategies are quicker at finding the whole set of nondominated solutions, while others are more representative when run under time constraint.
COMPUTERS & OPERATIONS RESEARCH
(2021)
Article
Computer Science, Hardware & Architecture
Ke Chen, Chenyu Xu, Haroon Waris, Weiqiang Liu, Paolo Montuschi, Fabrizio Lombardi
Summary: This paper designs an accurate squarer based on a Radix-8 Booth-folding square algorithm, and proposes several approximate squarers to reduce power and delay. The approximate squarers are implemented in a square-law detector for communication applications and applied to the k-means clustering algorithm for machine learning. The proposed designs achieve high performance in classification.
IEEE TRANSACTIONS ON COMPUTERS
(2023)
Article
Mechanics
Liu Ziyin, Botao Li, Xiangming Meng
Summary: This work derives the analytical expression for the global minima of a deep linear network with weight decay and stochastic neurons, revealing that the origin plays a special role in the highly nonlinear landscape of deep neural networks. The interaction between weight decay and model architecture leads to the creation of bad minima at zero in networks with multiple hidden layers, which is qualitatively different from networks with only one hidden layer. The practical implication is that common deep learning initialization methods are generally inadequate for optimizing neural networks.
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
(2023)
Article
Quantum Science & Technology
Elias F. Combarro, Sofia Vallecorsa, Alberto Di Meglio, Alejandro Pinera, Ignacio Fernandez Rua
Summary: The study generalizes quantum algorithms to solve promise problems stated over Boolean functions. These problems form a partially ordered set, with the Deutsch-Jozsa and Bernstein-Vazirani problems serving as extreme cases within it. The classical query complexities for problems in the poset can range between 1 and 2(n-1) + 1.
QUANTUM INFORMATION PROCESSING
(2021)
Article
Computer Science, Theory & Methods
Fedor Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
ACM TRANSACTIONS ON ALGORITHMS
(2020)
Editorial Material
Computer Science, Theory & Methods
Fedor V. Fomin, Vladimir V. Podolskii
THEORY OF COMPUTING SYSTEMS
(2020)
Article
Computer Science, Software Engineering
Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Stromme, Dimitrios M. Thilikos
Article
Computer Science, Artificial Intelligence
Fedor Fomin, Petr A. Golovach, Fahad Panolan
DATA MINING AND KNOWLEDGE DISCOVERY
(2020)
Article
Computer Science, Software Engineering
Fedor Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, Roohani Sharma
Summary: This study explores the parameterized complexity of minimum t-spanner problems on directed graphs, introducing the concepts of multiplicative and additive t-spanners. It provides insights into the polynomial kernel and solution methods for Directed Multiplicative Spanner, as well as the solution for the weighted variant on directed acyclic graphs, and highlights the difficulty of Directed Additive Spanner when parameterized by k on directed acyclic graphs.
Article
Computer Science, Software Engineering
Fedor Fomin, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Summary: This passage discusses the complexity of the classic Integer Programming Feasibility (IPF) problem and related algorithms, particularly focusing on the study of branch-width of the constraint matrix. By proving lower and upper bounds, optimal results for the (IPF) problem with specific branch-width are obtained.
MATHEMATICAL PROGRAMMING
(2023)
Article
Computer Science, Theory & Methods
Fedor Fomin, Vijayaragunathan Ramamoorthi
Summary: The study focuses on the Expected Coverage Problem from the perspective of parameterized complexity, showing that it is WM-hard for the parameter pathwidth. A complementary algorithm is proposed to solve the problem efficiently within time constraints based on treewidth and maximum vertex degree parameters.
THEORY OF COMPUTING SYSTEMS
(2022)
Article
Economics
Fedor V. Fomin, Pierre Fraigniaud, Petr A. Golovach
Summary: This paper explores the behavior of present-biased agents and extends the framework for studying time-inconsistent planning. The analysis of optimization tasks reveals the differences in the behavior of these agents under different problem constraints. The paper also investigates various combinations of minimization/maximization and underestimation/overestimation.
MATHEMATICAL SOCIAL SCIENCES
(2022)
Article
Computer Science, Theory & Methods
Fedor Fomin, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Summary: In this paper, we prove a theorem that states that given a planar graph G and an integer k, it is possible to randomly sample a subset A of vertices of G in polynomial time. The induced subgraph of G by A has a treewidth of O(k log k), and for any connected subgraph H of G with at most k vertices, the probability that A covers the whole vertex set of H is at least (2^O(k log^2 k) * n^O(1)) - 1, where n is the number of vertices of G. Together with dynamic programming techniques, this result provides a versatile approach for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, typically with running time bound of 2^O(k log^2 k) * n^O(1). This technique can be applied to various problems, such as local search and subgraph isomorphism, among others. Furthermore, our results hold on any class of graphs that exclude a fixed apex graph as a minor, including graphs embeddable in any fixed surface.
SIAM JOURNAL ON COMPUTING
(2022)
Article
Computer Science, Hardware & Architecture
Fedor Fomin, Danil Sagunov, Kirill Simonov
Summary: The study focuses on efficient algorithms for the EDGE k-CORE optimization problem, particularly in constructing k-cores from sparse graphs with structural properties. The results show that the problem can be solved in polynomial time when the input graph is a forest. Additionally, by parameterizing the problem with the minimum size of a vertex cover or the treewidth of the graph plus k, it can be solved in fixed-parameter tractable (FPT) time.
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
(2023)
Proceedings Paper
Computer Science, Theory & Methods
Fedor Fomin, Tuukka Korhonen
Summary: Branchwidth is a key measure for decomposing graphs and connectivity functions into a tree-like structure. Researchers have developed a general framework for designing fixed-parameter tractable 2-approximation algorithms for branchwidth, which has been applied to rank decomposition and cliquewidth optimization.
PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22)
(2022)
Proceedings Paper
Computer Science, Theory & Methods
Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20)
(2020)
Article
Mathematics, Applied
Fedor Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2020)
Proceedings Paper
Computer Science, Theory & Methods
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)
(2020)
Article
Mathematics, Applied
Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2020)
