Let χk′(G) ${\chi }_{k}^{^{\prime} }(G)$ denote the minimum number of colors needed to color the edges of a graph G $G$ in a way that the subgraph spanned by the edges of each color has all degrees ...congruent to 1 (
modk) $1\unicode{x02007}(\,\text{mod}\,\,k)$. Scott proved that χk′(G)≤
5
k
2log k ${\chi }_{k}^{^{\prime} }(G)\le 5{k}^{2}\mathrm{log}\unicode{x0200A}\unicode{x0200A}k$, and thus settled a question of Pyber, who had asked whether χk′(G) ${\chi }_{k}^{^{\prime} }(G)$ can be bounded solely as a function of k $k$. We prove that χk′(G)=O(k) ${\chi }_{k}^{^{\prime} }(G)=O(k)$, answering affirmatively a question of Scott.
In this paper we mainly focus on some determinants with Legendre symbol entries. Let p be an odd prime and let (⋅p) be the Legendre symbol. We show that (−S(d,p)p)=1 for any d∈Z with (dp)=1, and ...that(Wpp)={(−1)|{0<k<p4:(kp)=−1}|ifp≡1(mod4),(−1)⌊(p+1)/8⌋ifp≡3(mod4), whereS(d,p)=det(i2+dj2p)1⩽i,j⩽(p−1)/2 andWp=det(i2−((p−1)/2)!jp)0⩽i,j⩽(p−1)/2. We also pose some conjectures on determinants, one of which states that (−1)⌊(p+1)/8⌋Wp is a square when p≡3(mod4).
The development of efficient exact and approximate algorithms for probabilistic inference is a long-standing goal of artificial intelligence research. Whereas substantial progress has been made in ...dealing with purely discrete or purely continuous domains, adapting the developed solutions to tackle hybrid domains, characterized by discrete and continuous variables and their relationships, is highly non-trivial. Weighted Model Integration (WMI) recently emerged as a unifying formalism for probabilistic inference in hybrid domains. Despite a considerable amount of recent work, allowing WMI algorithms to scale with the complexity of the hybrid problem is still a challenge. In this paper we highlight some substantial limitations of existing state-of-the-art solutions, and develop an algorithm that combines SMT-based enumeration, an efficient technique in formal verification, with an effective encoding of the problem structure. This allows our algorithm to avoid generating redundant models, resulting in drastic computational savings. Additionally, we show how SMT-based approaches can seamlessly deal with different integration techniques, both exact and approximate, significantly expanding the set of problems that can be tackled by WMI technology. An extensive experimental evaluation on both synthetic and real-world datasets confirms the substantial advantage of the proposed solution over existing alternatives. The application potential of this technology is further showcased on a prototypical task aimed at verifying the fairness of probabilistic programs.
On Unlimited Sampling and Reconstruction Bhandari, Ayush; Krahmer, Felix; Raskar, Ramesh
IEEE transactions on signal processing,
2021, Volume:
69
Journal Article
Peer reviewed
Open access
Shannon's sampling theorem, at the heart of digital signal processing, is well understood and explored. However, its practical realization still suffers from a fundamental bottleneck due to dynamic ...range limitations of the underlying analog-to-digital converters (ADCs). This results in clipping or saturation for signal amplitudes exceeding their maximum recordable voltage thus leading to a significant information loss. In this paper, we develop an alternative paradigm for sensing and recovery, called the Unlimited Sampling Framework . The key observation is that applying a modulo operation to the signal before the ADC prevents saturation; instead, one encounters a different type of information loss. Such a setup can be implemented, for example, via so-called folding or self-reset ADCs, as proposed in various contexts in the circuit design literature. The key challenge for this new type of information loss is to recover a bandlimited signal from its modulo samples. We derive conditions when perfect recovery is possible and complement them with a stable recovery algorithm. The required sampling density is independent of the maximum recordable ADC voltage and depends on the signal bandwidth only. Our guarantees extend to measurements affected by bounded noise, which includes round-off quantization. Numerical experiments validate our approach. For example, it is possible to recover functions with amplitudes orders of magnitude higher than the ADC's threshold from quantized modulo samples up to the unavoidable quantization error. Applications of the unlimited sampling paradigm can be found in a number of fields such as signal processing, communication and imaging.
In this paper, we introduce the symplectic graph Spm(2ν) modulo m, and show that it is arc transitive. When m is a product of two distinct primes, we determine the suborbits of the symplectic group ...on Spm(2ν) and compute the parameters of Spm(2ν) as a quasi-strongly regular graph.
We define the class of rapidly left expansive cellular automata, which contains Wolfram's Rule 30, fractional multiplication automata, and many others. Previous results on aperiodicity of columns in ...space-time diagrams of certain cellular automata generalize to this new class. We also present conditions that imply periodic behavior in cellular automata and use these to prove new results on rapidly left expansive cellular automata that originate from the theory of distribution modulo 1.
Let k be an odd natural number ≥5, and let G be a (6k−7)-edge-connected graph of bipartite index at least k−1. Then, for each mapping f:V(G)→N, G has a subgraph H such that each vertex v has H-degree ...f(v) modulo k. We apply this to prove that, if c:V(G)→Zk is a proper vertex-coloring of a graph G of chromatic number k≥5 or k−1≥6, then each edge of G can be assigned a weight 1 or 2 such that each weighted vertex-degree of G is congruent to c modulo k. Consequently, each nonbipartite (6k−7)-edge-connected graph of chromatic number at most k (where k is any odd natural number ≥3) has an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees (even after reducing these weighted degrees modulo k). We characterize completely the bipartite graph having an edge-weighting with weights 1,2 such that neighboring vertices have distinct weighted degrees. In particular, that problem belongs to P while it is NP-complete for nonbipartite graphs. The characterization also implies that every 3-edge-connected bipartite graph with at least 3 vertices has such an edge-labeling, and so does every simple bipartite graph of minimum degree at least 3.
In this paper, investigation is performed on the design of efficient modulo 2n+1 adders, subtractors and add/subtract units for weighted operands. The existing modulo 2n+1 adder, subtractor ...architectures are reviewed and compared. A new efficient modulo 2n+1 adder architecture for weighted operands is also presented. The proposed modulo 2n+1 adders and one of the existing most efficient modulo 2n+1 subtractors are combined into a modulo 2n+1 add/subtract unit. The proposed modulo 2n+1 add/subtract units exhibit decreased area and power complexity when compared to existing ones.
Let G be a graph, let k be a positive integer, and let p:V(G)→{−1,…,k−2} be a mapping with |E(G)|≡k∑v∈V(G)p(v). In this paper, we show that if G is essentially (3k−3)-edge-connected and for each ...vertex v, dG(v)≥2k−1+p(v), then G has an orientation such that for each vertex v, dG+(v)≡kp(v), and⌊dG(v)2⌋−(k−1)≤dG+(v)≤⌈dG(v)2⌉+(k−1). In addition, we show that if G can be decomposed into 2k−2 edge-disjoint spanning trees and a factor F having an orientation such that for each vertex v, dF+(v)≥l0(v), then G has an orientation such that for each vertex v, dG+(v)≡kp(v), ands(v)≤dG+(v)≤dG(v)−s0(v), where s, s0, and l0 are three integer-valued functions on V(G) satisfying s(v)+s0(v)+k−1≤dG(v) and max{s(v),s0(v)}≤l0(v)+(k−1) for each vertex v, and max{s(z),s0(z)}≤l0(z) for a vertex z.
The zero-error helper capacity of the modulo-additive noise channel is studied both in the presence and in the absence of feedback. In its presence, a complete solution of said capacity is provided. ...In its absence, a solution is provided when the alphabet size is prime. For all other cases, upper and lower bounds are derived, and a necessary and sufficient condition for positivity is provided. Thanks to the help, the zero-error capacity may increase by more than the help's rate, and it can be positive yet smaller than one bit.
PDF
