| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Concrete problems

Here we collect a list of problems collected during the workshop to which one could hope to find a concrete answer.

    1. Exhibit a model for phase transitions!


      Add remark

      Problem 2.1.

      [A. Bastounis] Exhibit a model that has 3 phase transitions, as basis pursuit is known to have (at least) 2. For example one with a transition from polynomial to exponential time or unbounded time(arbitrary long time).
          Follow-up comment/question: "Leaning with errors" (CS theory related to phase transition) by Oded Regev.

        • Smales’ 9th problem.


          Add remark

          Problem 2.2.

          [J. Lagarias] Does there exist an algorithm for linear programming over the reals done by an algorithm that is independent of the bit-size. (in the framework of the sci-hierarchy).
              Follow-up comment/question: This is Smale’s 9th problem: Find a strongly-polynomial time algorithm which for given matrix $A$ and $b$ decides if there is $x$ such that $Ax \ge b.$ What is the right input set to obtain a polynomial time algorithm?

            • Create computer-assisted eigenvalue solver for matrices!


              Add remark

              Problem 2.3.

              [S. Olver] Given a n by n matrix, can you output the spectrum/eigenvalues to given accuracy? - In polynomial time.
                  Many of the desired features are included in the software package ’arb’

                • 2D Euler equation - From graph-like interface to splash


                  Add remark

                  Problem 2.1.

                  [C. Fefferman] Find a computer-assisted proof that the 2D Euler equation can develop a splash when starting from a graph-like structure.

                    • Find a dimension where the densest sphere packing is not a lattice!


                      Add remark

                      Problem 2.4.

                      [J. Lagarias]
                          Follow-up comments/questions: d=10, 11,13?.

                        • How many regular tetraheadra in $\mathbb R^3$ can touch at a single point?


                          Add remark

                          Problem 2.1.

                          [J. Lagarias] How many regular tetraheadra in $\mathbb R^3$ can touch at a single point? Follow-up comments/question: How many regular tetrahedra with side length $=1$ fit into a unit ball?

                              Cite this as: AimPL: Computational mathematics in computer assisted proofs , available at http://aimpl.org/compproofs.