Pawel Wocjan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Pawel Wocjan has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Clive Elphick
Department of Computer Science University of Central Florida USA
7 shared publications Anura Abeyesinghe
School of Electrical Engineering and Computer Science University of Central Florida 32816 Orlando FL USA
3 shared publications- Chen-Fu Chiang
Department of Electrical Engineering and Computer Science University of Central Florida 32816 Orlando FL USA
3 shared publications - Daniel Nagaj
Institute of Physics RCQI Slovak Academy of Sciences Bratislava Slovakia
3 shared publications - Felix Fontein
Universität Zürich
3 shared publications - Adam D. Bookatz
Center for Theoretical Physics Massachusetts Institute of Technology 02139 Cambridge Massachusetts USA
2 shared publications
Latest Publications
- Open Access
Conjectured bounds for the sum of squares of positive eigenvalues of a graph
A well known upper bound for the spectral radius of a graph, due to Hong, is that $\mu_1^2 \le 2m - n + 1$. It is conjectured that for connected graphs $n - 1 \le s^+ \le 2m - n + 1$, where $s^+$ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete $q$-partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.Open AccessConjectured bounds for the sum of squares of positive eigenvalues of a graph
A well known upper bound for the spectral radius of a graph, due to Hong, is that $\mu_1^2 \le 2m - n + 1$. It is conjectured that for connected graphs $n - 1 \le s^+ \le 2m - n + 1$, where $s^+$ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete $q$-partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general. - Open Access
Bounds and power means for the general Randic index
We review bounds for the general Randi\'c index, $R_{\alpha} = \sum_{ij \in E} (d_i d_j)^\alpha$, and use the power mean inequality to prove, for example, that $R_\alpha \ge m\lambda^{2\alpha}$ for $\alpha < 0$, where $\lambda$ is the spectral radius of a graph. This enables us to strengthen various known lower and upper bounds for $R_\alpha$ and to generalise a non-spectral bound due to Bollob\'as \emph{et al}. We also prove that the zeroth-order general Randi\'c index, $Q_\alpha = \sum_{i \in V} d_i^\alpha \ge n\lambda^\alpha$ for $\alpha < 0$.Open AccessBounds and power means for the general Randic index
We review bounds for the general Randi\'c index, $R_{\alpha} = \sum_{ij \in E} (d_i d_j)^\alpha$, and use the power mean inequality to prove, for example, that $R_\alpha \ge m\lambda^{2\alpha}$ for $\alpha < 0$, where $\lambda$ is the spectral radius of a graph. This enables us to strengthen various known lower and upper bounds for $R_\alpha$ and to generalise a non-spectral bound due to Bollob\'as \emph{et al}. We also prove that the zeroth-order general Randi\'c index, $Q_\alpha = \sum_{i \in V} d_i^\alpha \ge n\lambda^\alpha$ for $\alpha < 0$. - Open Access
New measures of graph irregularity
In this paper, we define and compare four new measures of graph irregularity. We use these measures to prove upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.
Open AccessNew measures of graph irregularity
In this paper, we define and compare four new measures of graph irregularity. We use these measures to prove upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.
- Open Access
Unified spectral bounds on the chromatic number
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: chi >= 1 + mu_1 / (- mu_n). We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.
Open AccessUnified spectral bounds on the chromatic number
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: chi >= 1 + mu_1 / (- mu_n). We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.
- 1 August 2014
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 64, 3-15
On the probability of generating a lattice
- 1 August 2014
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 64, 3-15
On the probability of generating a lattice
- Open Access
- 1 January 2014
- Published by The Institute for Research and Community Services (LPPM) ITB in Electronic Journal of Graph Theory and Applications
- Vol. 2 (1) , 52-65
New measures of graph irregularity
New measures of graph irregularity
- 1 January 2014
- Published by The Institute for Research and Community Services (LPPM) ITB in Electronic Journal of Graph Theory and Applications
- Vol. 2 (1) , 52-65
Open AccessNew measures of graph irregularity
New measures of graph irregularity
- Open Access
Hamiltonian quantum simulation with bounded-strength controls
We propose dynamical control schemes for Hamiltonian simulation in many-body quantum systems that avoid instantaneous control operations and rely solely on realistic bounded-strength control Hamiltonians. Each simulation protocol consists of periodic repetitions of a basic control block, constructed as a suitable modification of an "Eulerian decoupling cycle," that would otherwise implement a trivial (zero) target Hamiltonian. For an open quantum system coupled to an uncontrollable environment, our approach may be employed to engineer an effective evolution that simulates a target Hamiltonian on the system, while suppressing unwanted decoherence to the leading order. We present illustrative applications to both closed- and open-system simulation settings, with emphasis on simulation of non-local (two-body) Hamiltonians using only local (one-body) controls. In particular, we provide simulation schemes applicable to Heisenberg-coupled spin chains exposed to general linear decoherence, and show how to simulate Kitaev's honeycomb lattice Hamiltonian starting from Ising-coupled qubits, as potentially relevant to the dynamical generation of a topologically protected quantum memory. Additional implications for quantum information processing are discussed.
Open AccessHamiltonian quantum simulation with bounded-strength controls
We propose dynamical control schemes for Hamiltonian simulation in many-body quantum systems that avoid instantaneous control operations and rely solely on realistic bounded-strength control Hamiltonians. Each simulation protocol consists of periodic repetitions of a basic control block, constructed as a suitable modification of an "Eulerian decoupling cycle," that would otherwise implement a trivial (zero) target Hamiltonian. For an open quantum system coupled to an uncontrollable environment, our approach may be employed to engineer an effective evolution that simulates a target Hamiltonian on the system, while suppressing unwanted decoherence to the leading order. We present illustrative applications to both closed- and open-system simulation settings, with emphasis on simulation of non-local (two-body) Hamiltonians using only local (one-body) controls. In particular, we provide simulation schemes applicable to Heisenberg-coupled spin chains exposed to general linear decoherence, and show how to simulate Kitaev's honeycomb lattice Hamiltonian starting from Ising-coupled qubits, as potentially relevant to the dynamical generation of a topologically protected quantum memory. Additional implications for quantum information processing are discussed.
- Open Access
- 19 July 2013
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (3) , P39
New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix
The purpose of this article is to improve existing lower bounds on the chromatic number $\chi$. Let $\mu_1,\ldots,\mu_n$ be the eigenvalues of the adjacency matrix sorted in non-increasing order.First, we prove the lower bound $\chi \ge 1 + \max_m\{\sum_{i=1}^m \mu_i / -\sum_{i=1}^m \mu_{n - i +1}\}$ for $m=1,\ldots,n-1$. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case $m=1$. We provide several examples for which the new bound exceeds the Hoffman lower bound.Second, we conjecture the lower bound $\chi \ge 1 + s^+ / s^-$, where $s^+$ and $s^-$ are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the bound $\chi \ge s^+/s^-$. We show that the conjectured lower bound is true for several families of graphs. We also performed various searches for a counter-example, but none was found.Our proofs rely on a new technique of considering a family of conjugates of the adjacency matrix, which add to the zero matrix, and use majorization of spectra of self-adjoint matrices.We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected.All these bounds are also valid when we replace the adjacency matrix $A$ by $W * A$ where $W$ is an arbitrary self-adjoint matrix and $*$ denotes the Schur product, that is, entrywise product of $W$ and $A$.- 19 July 2013
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (3) , P39
Open AccessNew Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix
The purpose of this article is to improve existing lower bounds on the chromatic number $\chi$. Let $\mu_1,\ldots,\mu_n$ be the eigenvalues of the adjacency matrix sorted in non-increasing order.First, we prove the lower bound $\chi \ge 1 + \max_m\{\sum_{i=1}^m \mu_i / -\sum_{i=1}^m \mu_{n - i +1}\}$ for $m=1,\ldots,n-1$. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case $m=1$. We provide several examples for which the new bound exceeds the Hoffman lower bound.Second, we conjecture the lower bound $\chi \ge 1 + s^+ / s^-$, where $s^+$ and $s^-$ are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the bound $\chi \ge s^+/s^-$. We show that the conjectured lower bound is true for several families of graphs. We also performed various searches for a counter-example, but none was found.Our proofs rely on a new technique of considering a family of conjugates of the adjacency matrix, which add to the zero matrix, and use majorization of spectra of self-adjoint matrices.We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected.All these bounds are also valid when we replace the adjacency matrix $A$ by $W * A$ where $W$ is an arbitrary self-adjoint matrix and $*$ denotes the Schur product, that is, entrywise product of $W$ and $A$. - Open Access
On the Probability of Generating a Lattice
We study the problem of determining the probability that m vectors selected uniformly at random from the intersection of the full-rank lattice L in R^n and the window [0,B)^n generate $\Lambda$ when B is chosen to be appropriately large. This problem plays an important role in the analysis of the success probability of quantum algorithms for solving the Discrete Logarithm Problem in infrastructures obtained from number fields and also for computing fundamental units of number fields. We provide the first complete and rigorous proof that 2n+1 vectors suffice to generate L with constant probability (provided that B is chosen to be sufficiently large in terms of n and the covering radius of L and the last n+1 vectors are sampled from a slightly larger window). Based on extensive computer simulations, we conjecture that only n+1 vectors sampled from one window suffice to generate L with constant success probability. If this conjecture is true, then a significantly better success probability of the above quantum algorithms can be guaranteed.Open AccessOn the Probability of Generating a Lattice
We study the problem of determining the probability that m vectors selected uniformly at random from the intersection of the full-rank lattice L in R^n and the window [0,B)^n generate $\Lambda$ when B is chosen to be appropriately large. This problem plays an important role in the analysis of the success probability of quantum algorithms for solving the Discrete Logarithm Problem in infrastructures obtained from number fields and also for computing fundamental units of number fields. We provide the first complete and rigorous proof that 2n+1 vectors suffice to generate L with constant probability (provided that B is chosen to be sufficiently large in terms of n and the covering radius of L and the last n+1 vectors are sampled from a slightly larger window). Based on extensive computer simulations, we conjecture that only n+1 vectors sampled from one window suffice to generate L with constant success probability. If this conjecture is true, then a significantly better success probability of the above quantum algorithms can be guaranteed. - Open Access
- 15 April 2013
- Published by American Physical Society (APS) in Physical Review A
- Vol. 87 (4)
Quantum nonexpander problem is quantum-Merlin-Arthur-complete
A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that the problem of deciding whether a quantum channel is not rapidly mixing is a complete problem for the quantum Merlin-Arthur complexity class. This has applications to testing randomized constructions of quantum expanders and studying thermalization of open quantum systems.
- 15 April 2013
- Published by American Physical Society (APS) in Physical Review A
- Vol. 87 (4)
Open AccessQuantum nonexpander problem is quantum-Merlin-Arthur-complete
A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that the problem of deciding whether a quantum channel is not rapidly mixing is a complete problem for the quantum Merlin-Arthur complexity class. This has applications to testing randomized constructions of quantum expanders and studying thermalization of open quantum systems.