Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNotes on ${a,b,c}$-Modular Matrices
124
0
0.0
(
0
)
Added by
Christoph Glanzer
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $A in mathbb{Z}^{m times n}$ be an integral matrix and $a$, $b$, $c in mathbb{Z}$ satisfy $a geq b geq c geq 0$. The question is to recognize whether $A$ is ${a,b,c}$-modular, i.e., whether the set of $n times n$ subdeterminants of $A$ in absolute value is ${a,b,c}$. We will succeed in solving this problem in polynomial time unless $A$ possesses a duplicative relation, that is, $A$ has nonzero $n times n$ subdeterminants $k_1$ and $k_2$ satisfying $2 cdot |k_1| = |k_2|$. This is an extension of the well-known recognition algorithm for totally unimodular matrices. As a consequence of our analysis, we present a polynomial time algorithm to solve integer programs in standard form over ${a,b,c}$-modular constraint matrices for any constants $a$, $b$ and $c$.
rate research
Read More
This is a set of lecture notes suitable for a Masters course on quantum computation and information from the perspective of theoretical computer science. The first version was written in 2011, with many extensions and improvements in subsequent years. The first 10 chapters cover the circuit model and the main quantum algorithms (Deutsch-Jozsa, Simon, Shor, Hidden Subgroup Problem, Grover, quantum walks, Hamiltonian simulation and HHL). They are followed by 3 chapters about complexity, 4 chapters about distributed (Alice and Bob) settings, and a final chapter about quantum error correction. Appendices A and B give a brief introduction to the required linear algebra and some other mathematical and computer science background. All chapters come with exercises, with some hints provided in Appendix C.
We study the problem of maximizing the geometric mean of $d$ low-degree non-negative forms on the real or complex sphere in $n$ variables. We show that this highly non-convex problem is NP-hard even when the forms are quadratic and is equivalent to optimizing a homogeneous polynomial of degree $O(d)$ on the sphere. The standard Sum-of-Squares based convex relaxation for this polynomial optimization problem requires solving a semidefinite program (SDP) of size $n^{O(d)}$, with multiplicative approximation guarantees of $Omega(frac{1}{n})$. We exploit the compact representation of this polynomial to introduce a SDP relaxation of size polynomial in $n$ and $d$, and prove that it achieves a constant factor multiplicative approximation when maximizing the geometric mean of non-negative quadratic forms. We also show that this analysis is asymptotically tight, with a sequence of instances where the gap between the relaxation and true optimum approaches this constant factor as $d rightarrow infty$. Next we propose a series of intermediate relaxations of increasing complexity that interpolate to the full Sum-of-Squares relaxation, as well as a rounding algorithm that finds an approximate solution from the solution of any intermediate relaxation. Finally we show that this approach can be generalized for relaxations of products of non-negative forms of any degree.
Machine scheduling problems are a long-time key domain of algorithms and complexity research. A novel approach to machine scheduling problems are fixed-parameter algorithms. To stimulate this thriving research direction, we propose 15 open questions in this area whose resolution we expect to lead to the discovery of new approaches and techniques both in scheduling and parameterized complexity theory.
This is a collection of the lecture notes of the three authors for a first-year graduate course on control system theory and design (ECE 515 , formerly ECE 415) at the ECE Department of the University of Illinois at Urbana-Champaign. This is a fundamental course on the modern theory of dynamical systems and their control, and builds on a first-level course in control that emphasizes frequency-domain methods (such as the course ECE 486 , formerly ECE 386, at UIUC ). The emphasis in this graduate course is on state space techniques, and it encompasses modeling , analysis (of structural properties of systems, such as stability, controllability, and observability), synthesis (of observers/compensators and controllers) subject to design specifications, and optimization . Accordingly, this set of lecture notes is organized in four parts, with each part dealing with one of the issues identified above. Concentration is on linear systems , with nonlinear systems covered only in some specific contexts, such as stability and dynamic optimization. Both continuous-time and discrete-time systems are covered, with the former, however, in much greater depth than the latter. The main objective of this course is to teach the student some fundamental principles within a solid conceptual framework, that will enable her/him to design feedback loops compatible with the information available on the states of the system to be controlled, and by taking into account considerations such as stability, performance, energy conservation, and even robustness. A second objective is to familiarize her/him with the available modern computational, simulation, and general software tools that facilitate the design of effective feedback loops
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of $O(1)$, $Theta(log^* n)$, or $Theta(n)$, and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: $O(1)$, $Theta(log^* n)$, and $Theta(n)$. However, given an LCL problem it is undecidable whether its complexity is $Theta(log^* n)$ or $Theta(n)$ in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is $Theta(log^* n)$, we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form $A circ S_k$, where $A$ is a finite function, $S_k$ is an algorithm for finding a maximal independent set in $k$th power of the grid, and $k$ is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
