More Like this

1. Maximizing Submodular Functions under Submodular Constraints

   Padmanabhan, Madhavan R; Zhu, Yanhui; Basu, Samik; Pavan A. (July 2023, Uncertainty in Artificial Intelligence, {UAI} 2023)

   Evans, Robin; Shpitser, Ilya (Ed.)

   We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: \SCSKC and \DiffC. Given two submodular functions $$f$$ and $$g$$ where $$f$$ is monotone, the objective of \SCSKC problem is to find a set $$S$$ of size at most $$k$$ that maximizes $f(S)$ under the constraint that $$g(S)\leq \theta$$, for a given value of $$\theta$$. The problem of \DiffC focuses on finding a set $$S$$ of size at most $$k$$ such that $h(S) = f(S)-g(S)$$ is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve data-dependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of \SCSKC, we prove that the greedy algorithm produces a solution whose value is at least $$(1-1/e)f(\OPT) - A$, where $$A$$ is the data-dependent additive error. For the \DiffC problem, we design an algorithm that uses the \SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least $$(1-1/e)h(\OPT)-B$, where $$B$$ is also a data-dependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced. 

   more » « less
2. On the Rational Degree of Boolean Functions and Applications

   Iyer, Vishnu; Jain, Siddhartha; Kovacs-Deak, Matt; Kumar, Vinayak M; Schaeffer, Luke; Wang, Daochen; Whitmeyer, Michael (October 2023, arXivorg)

   On the Rational Degree of Boolean Functions and Applications Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least sqrt(deg(f)). We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2−O(sqrt(n)). In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. 

   more » « less
3. Waring’s Problem for Rational Functions in One Variable

   https://doi.org/10.1093/qmathj/haz052  

   Im, Bo-Hae; Larsen, Michael (February 2020, The quarterly journal of mathematics)

   Let f∈ℚ(x) be a non-constant rational function. We consider ‘Waring’s problem for f(x), i.e., whether every element of ℚ can be written as a bounded sum of elements of {f(a)∣a∈ℚ}. For rational functions of degree 2, we give necessary and sufficient conditions. For higher degrees, we prove that every polynomial of odd degree and every odd Laurent polynomial satisfies Waring’s problem. We also consider the 'easier Waring’s problem': whether every element of ℚ can be represented as a bounded sum of elements of {±f(a)∣a∈ℚ}. ⁠. 

   more » « less
4. Twisted Mahler Discrete Residues

   https://doi.org/10.1093/imrn/rnae238  

   Arreche, Carlos_E; Zhang, Yi (October 2024, International Mathematics Research Notices)

   Abstract Recently we constructed Mahler discrete residues for rational functions and showed they comprise a complete obstruction to the Mahler summability problem of deciding whether a given rational function $f(x)$ is of the form $$g(x^{p})-g(x)$$ for some rational function $g(x)$ and an integer $p> 1$. Here we develop a notion of $$\lambda $$-twisted Mahler discrete residues for $$\lambda \in \mathbb{Z}$$, and show that they similarly comprise a complete obstruction to the twisted Mahler summability problem of deciding whether a given rational function $f(x)$ is of the form $$p^{\lambda } g(x^{p})-g(x)$$ for some rational function $g(x)$ and an integer $p>1$. We provide some initial applications of twisted Mahler discrete residues to differential creative telescoping problems for Mahler functions and to the differential Galois theory of linear Mahler equations. 

   more » « less
5. Computing discrete residues of rational functions

   https://doi.org/10.1145/3666000.3669676  

   Arreche, Carlos E; Sitaula, Hari (July 2024, ACM)

   In 2012 Chen and Singer introduced the notion of discrete residues for rational functions as a complete obstruction to rational summability. More explicitly, for a given rational function f(x), there exists a rational function g(x) such that f(x) = g(x+1) - g(x) if and only if every discrete residue of f(x) is zero. Discrete residues have many important further applications beyond summability: to creative telescoping problems, thence to the determination of (differential-)algebraic relations among hypergeometric sequences, and subsequently to the computation of (differential) Galois groups of difference equations. However, the discrete residues of a rational function are defined in terms of its complete partial fraction decomposition, which makes their direct computation impractical due to the high complexity of completely factoring arbitrary denominator polynomials into linear factors. We develop a factorization-free algorithm to compute discrete residues of rational functions, relying only on gcd computations and linear algebra. 

   more » « less