Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBreaking Generator Symmetry
155
0
0.0
(
0
)
Added by
Nina Narodytska
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Dealing with large numbers of symmetries is often problematic. One solution is to focus on just symmetries that generate the symmetry group. Whilst there are special cases where breaking just the symmetries in a generating set is complete, there are also cases where no irredundant generating set eliminates all symmetry. However, focusing on just generators improves tractability. We prove that it is polynomial in the size of the generating set to eliminate all symmetric solutions, but NP-hard to prune all symmetric values. Our proof considers row and column symmetry, a common type of symmetry in matrix models where breaking just generator symmetries is very effective. We show that propagating a conjunction of lexicographical ordering constraints on the rows and columns of a matrix of decision variables is NP-hard.
rate research
Read More
We propose a new family of constraints which combine together lexicographical ordering constraints for symmetry breaking with other common global constraints. We give a general purpose propagator for this family of constraints, and show how to improve its complexity by exploiting properties of the included global constraints.
A graph is weakly $2$-colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we study the distributed computational complexity of weak $2$-coloring in the standard LOCAL model of distributed computing, and how it is related to the distributed computational complexity of other graph problems. First, we show that weak $2$-coloring is a minimal distributed symmetry-breaking problem for regular even-degree trees and high-girth graphs: if there is any non-trivial locally checkable labeling problem that is solvable in $o(log^* n)$ rounds with a distributed graph algorithm in the middle of a regular even-degree tree, then weak $2$-coloring is also solvable in $o(log^* n)$ rounds there. Second, we prove a tight lower bound of $Omega(log^* n)$ for the distributed computational complexity of weak $2$-coloring in regular trees; previously only a lower bound of $Omega(log log^* n)$ was known. By minimality, the same lower bound holds for any non-trivial locally checkable problem inside regular even-degree trees.
We review and expand upon recent work demonstrating that Weyl invariant theories can be broken inertially, which does not depend upon a potential. This can be understood in a general way by the current algebra of these theories, independently of specific Lagrangians. Maintaining the exact Weyl invariance in a renormalized quantum theory can be accomplished by renormalization conditions that refer back to the VEVs of fields in the action. We illustrate the computation of a Weyl invariant Coleman-Weinberg potential that breaks a U(1) symmetry together,with scale invariance.
Symmetry-breaking phase transitions are ubiquitous in condensed matter systems and in quantum field theories. There is also good reason to believe that they feature in the very early history of the Universe. At many such transitions topological defects of one kind or another are formed. Because of their inherent stability, they can have important effects on the subsequent behaviour of the system. In the first of these lectures I shall review a number of examples of spontaneous symmetry breaking, many of which will be discussed in more detail by other lecturers, and discuss their general features. The second lecture will be mainly devoted to the conditions under which topological defects can appear and their classification in terms of homotopy groups of the underlying vacuum manifold. In my final lecture, I will discuss the `cosmology in the laboratory experiments which have been done to try to test some of the ideas thrown up by discussions of defect formation in the early Universe by looking at analogous processes in condensed-matter systems.
We present a novel real-time, collaborative, and interactive AI painting system, Mappa Mundi, for artistic Mind Map creation. The system consists of a voice-based input interface, an automatic topic expansion module, and an image projection module. The key innovation is to inject Artificial Imagination into painting creation by considering lexical and phonological similarities of language, learning and inheriting artists original painting style, and applying the principles of Dadaism and impossibility of improvisation. Our system indicates that AI and artist can collaborate seamlessly to create imaginative artistic painting and Mappa Mundi has been applied in art exhibition in UCCA, Beijing
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
