More Like this

1. Towards Testing Monotonicity of Distributions Over General Posets

   Alaikbarpour, A.; Gouleakis, T.; Peebles, J.; Rubinfeld, R.; Yodpinyanee, A (January 2019, Proceedings of the Thirty-Second Conference on Learning Theory (COLT 2019))

   In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is monotone if, for any pair of domain elements x and y such that x ⪯ y, p(x) ≤ p(y). To understand the sample complexity of this problem, we introduce a new property called bigness over a finite domain, where the distribution is T-big if the minimum probability for any domain element is at least T. We establish a lower bound of Ω(n/ log n) for testing bigness of distributions on domains of size n. We then build on these lower bounds to give Ω(n/ log n) lower bounds for testing monotonicity over a matching poset of size n and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem. The previous lower bound for testing Monotonicity of 

   more » « less
2. Effective Density for Inhomogeneous Quadratic Forms I: Generic Forms and Fixed Shifts

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

   Ghosh, Anish; Kelmer, Dubi; Yu, Shucheng (August 2020, International Mathematics Research Notices)

   Abstract We establish effective versions of Oppenheim’s conjecture for generic inhomogeneous quadratic forms. We prove such results for fixed shift vectors and generic quadratic forms. When the shift is rational we prove a counting result, which implies the optimal density for values of generic inhomogeneous forms. We also obtain a similar density result for fixed irrational shifts satisfying an explicit Diophantine condition. The main technical tool is a formula for the 2nd moment of Siegel transforms on certain congruence quotients of $$SL_n(\mathbb{R}),$$ which we believe to be of independent interest. In a sequel, we use different techniques to treat the companion problem concerning generic shifts and fixed quadratic forms. 

   more » « less
3. Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint

   Ene, Alina; Nguyen, Huy L. (July 2019, International Colloquium on Automata, Languages, and Programming)

   We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a $$1 - 1/e - \epsilon$$ approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, $$1 - 1/e - \epsilon$$ approximation, using a nearly-linear number of function evaluations and arithmetic operations. 

   more » « less
4. Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint

   https://doi.org/10.4230/LIPIcs.ICALP.2019.54  

   Ene, Alina; Nguyen, Huy L. (January 2019, Leibniz international proceedings in informatics)

   We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1 - 1/e - epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, 1 - 1/e - epsilon approximation, using a nearly-linear number of function evaluations and arithmetic operations. 

   more » « less
5. Towards Testing Monotonicity of Distributions Over General Posets

   Alaikbarpour, Maryam; Gouleakis, Themis; Peebles, John; Rubinfeld, Ronitt; Yodpinyanee, Anak (January 2019, Proceedings of the Thirty-Second Conference on Learning Theory, PMLR)

   In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is {\em monotone} if, for any pair of domain elements x and y such that x⪯y, p(x)≤p(y). To understand the sample complexity of this problem, we introduce a new property called \emph{bigness} over a finite domain, where the distribution is T-big if the minimum probability for any domain element is at least T. We establish a lower bound of Ω(n/logn) for testing bigness of distributions on domains of size n. We then build on these lower bounds to give Ω(n/logn) lower bounds for testing monotonicity over a matching poset of size n and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem. 

   more » « less