University of Waterloo

Tue 10 Sep 2019, 4:00pm
Discrete Math Seminar
ESB 4127

SAT Solving with Computer Algebra: A Powerful Combinatorial Search Method

ESB 4127
Tue 10 Sep 2019, 4:00pm5:00pm
Abstract
Solvers for the Boolean satisfiability problem have been increasingly used to solve hard problems from many fields and now routinely solve problems with millions of variables. Combinatorial problems are a natural target, as SAT solvers contain excellent combinatorial search algorithms. Despite this, SAT solvers can fail on small problems, for example when properties of the problem cannot be concisely expressed in Boolean logic. We describe a new combinatorial search method that allows properties to be specified using a computer algebra system (CAS), thereby combining the expressiveness of a CAS with the search power of SAT solvers.
In this talk we describe how our SAT+CAS system MathCheck has verified, partially verified, or found new counterexamples to conjectures from design theory, graph theory, and number theory. In particular, we have classified Williamson matrices up to order 70, quaternary Golay sequence pairs up to length 28, best matrices up to order 7, verified the Ruskey–Savage and Norine conjectures up to larger bounds than had previously been verified, found the smallest counterexample of the Williamson conjecture, and found three new counterexamples to a conjecture on good matrices. Currently we are using the system to verify the nonexistence of projective planes of order 10.
hide

University of Washington

Tue 17 Sep 2019, 4:00pm
Discrete Math Seminar
ESB 4127

Resolving Stanley’s conjecture on kfold acyclic complexes

ESB 4127
Tue 17 Sep 2019, 4:00pm5:00pm
Abstract
In 1993, Stanley showed that if a simplicial complex is acyclic over some field, then its face poset can be decomposed into disjoint rank 1 boolean intervals whose minimal faces together form a subcomplex. Stanley further conjectured that complexes with a higher notion of acyclicity could be decomposed in a similar way using boolean intervals of higher rank. We provide an explicit counterexample to this conjecture. We also prove a special case of the conjecture, and show that a weaker decomposition into boolean trees always exists. This is joint work with Joseph Doolittle.
hide

UBC

Tue 24 Sep 2019, 4:00pm
Discrete Math Seminar
ESB 4127

TBA

ESB 4127
Tue 24 Sep 2019, 4:00pm5:00pm
Abstract
hide

U. Waterloo

Tue 1 Oct 2019, 4:00pm
Discrete Math Seminar
ESB 4127

TBA

ESB 4127
Tue 1 Oct 2019, 4:00pm5:00pm
Abstract
hide

Sauder, UBC

Tue 15 Oct 2019, 4:00pm
Discrete Math Seminar
ESB 4127

The discrete moment problem with nonconvex shape constraints

ESB 4127
Tue 15 Oct 2019, 4:00pm5:00pm
Abstract
The discrete moment problem is a foundational problem in distributionfree robust optimization, where the goal is to find a worstcase distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional “shape constraints” that guarantee the worstcase distribution is either logconcave (LC), has an increasing failure rate (IFR), or an increasing generalized failure rate (IGFR). These classes of shape constraints have not previously been studied in the literature, in part due to their inherent nonconvexities. Nonetheless, these classes of distributions are useful in practice with applications in revenue management, reliability, and inventory control. We characterize the structure of optimal extreme point distributions. We show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces.
This is joint work with Xi Chen (NYU, Stern School of Business), Simai He (Shanghai University of Finance and Economics, School of Information Management and Engineering), Bo Jiang (Shanghai University of Finance and Economics, School of Information Management and Engineering), and Teng Zhang (Stanford, Management Science and Engineering).
hide

UBC

Tue 29 Oct 2019, 4:00pm
Discrete Math Seminar
ESB 4127

TBA

ESB 4127
Tue 29 Oct 2019, 4:00pm5:00pm
Abstract
hide


Tue 14 Jan 2020, 4:00pm
Discrete Math Seminar
ESB 4127


ESB 4127
Tue 14 Jan 2020, 4:00pm5:00pm
Abstract
hide

Seminar Information Pages
