researchmap

Publisher：Rinton Press, Incorporated  

DOI： 10.26421/QIC19.5-6

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Rinton Press  

Buhrman showed that an efficient communication protocol implies a reliable XOR game protocol. This idea rederives Linial and Shraibman’s lower bound of randomized and quantum communication complexities, which was derived by using factorization norms, with worse constant factor in much more intuitive way. In this work, we improve and generalize Buhrman’s idea, and obtain a class of lower bounds for randomized communication complexity including an exact Linial and Shraibman’s lower bound as a special case. In the proof, we explicitly construct a protocol for XOR game from a randomized communication protocol by using a concept of nonlocal boxes and Paw lowski et al.’s elegant protocol, which was used for showing the violation of information causality in superquantum theories.

DOI： 10.26421/qic17.15-16-1

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Association for Computing Machinery  

Let P: {0, 1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem CSP(P) on n variables with An constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfes Δ ≥≥ 1, such an instance is unsatisfable with high probability. The refutation problem is to efficiently find a proof of unsatisfability. We show that whenever the predicate P supports a t-wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree d = Θ(n/Δ2/(t-1)longΔ) (which runs in time nO(d)) cannot refute a random instance of CSP(P). In particular, the polynomial-time SOS algorithm requires Ω(n(t+1)/2) constraints to refute random instances of CSP(P) when P supports a t-wise uniform distribution on its satisfying assignments. Together with recent work of Lee, Raghavendra, Steurer (2015), our result also implies that any polynomial-size semidefinite programming relaxation for refutation requires at least Ω(n(t+1)/2) constraints. More generally, we consider the δ-refutation problem, in which the goal is to certify that at most a (1 - δ)-fraction of constraints can be simultaneously satisfed. We show that if P is δ-close to supporting a t-wise uniform distribution on satisfying assignments, then the degree-Ω(n/Δ2/(t-1)logΔ) SOS algorithm cannot (δ + o(1))- refute a random instance of CSP(P). This is the first result to show a distinction between the degree SOS needs to solve the refutation problem and the degree it needs to solve the harder δ-refutation problem. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate P, they give a three-way hardness tradeof between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen, O'Donnell, Witmer (2015) and Raghavendra, Rao, Schramm (2016), this full three-way tradeof is tight, up to lower-order factors.

DOI： 10.1145/3055399.3055485

Scopus

researchmap

Other Link： http://orcid.org/0000-0001-5474-5145

Language：English   Publishing type：Research paper (scientific journal)   Publisher：AMER PHYSICAL SOC  

Brassard et al. [Phys. Rev. Lett. 96, 250401 (2006)] showed that shared nonlocal boxes with a CHSH (Clauser, Horne, Shimony, and Holt) probability greater than 3+root 6/6 yield trivial communication complexity. There still exists a gap with the maximum CHSH probability 2+root 2/4 achievable by quantum mechanics. It is an interesting open question to determine the exact threshold for the trivial communication complexity. Brassard et al.'s idea is based on recursive bias amplification by the three-input majority function. It was not obvious if another choice of function exhibits stronger bias amplification. We show that the three-input majority function is the unique optimal function, so that one cannot improve the threshold 3+root 6/6 by Brassard et al.'s bias amplification. In this work, protocols for computing the function used for the bias amplification are restricted to be nonadaptive protocols or a particular adaptive protocol inspired by Pawlowski et al.'s protocol for information causality [Nature (London) 461, 1101 (2009)]. We first show an adaptive protocol inspired by Pawlowski et al.'s protocol, and then show that the adaptive protocol improves upon nonadaptive protocols. Finally, we show that the three-input majority function is the unique optimal function for the bias amplification if we apply the adaptive protocol to each step of the bias amplification.

DOI： 10.1103/PhysRevA.94.052130

Web of Science

researchmap

Other Link： http://orcid.org/0000-0001-5474-5145

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

For a k-Ary predicate P, a random instance of CSP(P) with n variables and m constraints is unsatisfiable with high probability when m ≥ O(n). The natural algorithmic task in this regime is refutation: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP(P) using an SDP is determined by a parameter cmplx(P), the smallest t for which there does not exist a t-wise uniform distribution over satisfying assignments to P. In particular they show that random instances of CSP(P) with m ≥ ncmplx(P)/2 can be refuted efficiently using an SDP. In this work, we give evidence that ncmplx(P)/2 constraints are also necessary for refutation using SDPs. Specifically, we show that if P supports a (t-1)-wise uniform distribution over satisfying assignments, then the Sherali-Adams+ and Lovász-Schrijver+ SDP hierarchies cannot refute a random instance of CSP(P) in polynomial time for any m ≤ nt/2-ϵ.

DOI： 10.4230/LIPIcs.APPROX-RANDOM.2016.41

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

A network topology with low average shortest path length (ASPL) provides efficient data transmission while the number of nodes and the number of links incident to each node are often limited due to physical constraints. In this paper, we consider the construction of low ASPL graphs under these constraints by using stochastic local search (SLS) algorithms. Since the ASPL cannot be calculated efficiently, the ASPL is not suitable for the evaluation function of SLS algorithms. We first derive an equality and bounds for the ASPL of graphs of diameter 3. On the basis of the simplest upper bound of the ASPL, we propose to use 3 Delta + 2 square as the evaluation function for graphs of diameter 3 where Delta and square denote the number of triangles and squares in a graph, respectively. We show that the proposed evaluation function can be evaluated in O(1) time as the number of nodes and the maximum degree tend to infinity by using some data tables. By using the simulated annealing with the proposed evaluation function, we construct low ASPL regular graphs of diameter 3 with 10 000 nodes.

DOI： 10.1109/NOCS.2016.7579335

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC  

The Bethe approximation is a well-known approximation of the partition function used in statistical physics. Recently, an equality relating the partition function and its Bethe approximation was obtained for graphical models with binary variables by Chertkov and Chernyak. In this equality, the multiplicative error in the Bethe approximation is represented as a weighted sum over all generalized loops in the graphical model. In this paper, the equality is generalized to graphical models with nonbinary alphabet using concepts from information geometry.

DOI： 10.1109/TIT.2015.2403239

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

The holographic transformation, belief propagation and loop calculus are generalized to problems in generalized probabilistic theories including quantum mechanics. In this work, the partition function of classical factor graph is represented by an inner product of two high-dimensional vectors both of which can be decomposed to tensor products of low-dimensional vectors. On the representation, the holographic transformation is clearly understood by using adjoint linear maps. Furthermore, on the formulation using inner product, the belief propagation is naturally defined from the derivation of the loop calculus formula. As a consequence, the holographic transformation, the belief propagation and the loop calculus are generalized to measurement problems in quantum mechanics and generalized probabilistic theories.

DOI： 10.1109/ISIT.2015.7282625

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC  

Polarization phenomenon over any finite field F-q with size q being a power of a prime is considered. This problem is a generalization of the original proposal of channel polarization by Arikan for the binary field, as well as its extension to a prime field by, Sasoglu, Telatar, and Arikan. In this paper, a necessary and sufficient condition of a matrix over a finite field F-q is shown under which any source and channel are polarized. Furthermore, the result of the speed of polarization for the binary alphabet obtained by Arikan and Telatar is generalized to arbitrary finite field. It is also shown that the asymptotic error probability of polar codes is improved by using the Reed-Solomon matrices, which can be regarded as a natural generalization of the 2 x 2 binary matrix used in the original proposal by Arikan.

DOI： 10.1109/TIT.2014.2312181

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC  

We consider the asymptotic behavior of the polarization process in the large block-length regime when transmission takes place over a binary-input memoryless symmetric channel W. In particular, we study the asymptotics of the cumulative distribution, P(Z(n) <= z), where {Z(n)} is the Bhattacharyya process associated with W, and its dependence on the rate of transmission. On the basis of this result, we characterize the asymptotic behavior, as well as its dependence on the rate, of the block error probability of polar codes using the successive cancellation decoder. This refines the original asymptotic bounds by Arikan and Telatar. Our results apply to general polar codes based on l x l kernel matrices. We also provide asymptotic lower bounds on the block error probability of polar codes using the maximum a posteriori (MAP) decoder. The MAP lower bound and the successive cancellation upper bound coincide when l = 2, but there is a gap for l > 2.

DOI： 10.1109/TIT.2012.2228295

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC  

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as the blockength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like alpha(epsilon, t)/n + Theta (n(-2)) as the blocklength tends to infinity where alpha(epsilon, t) denotes a specific constant determined by the code ensemble considered, the number of iterations, and the erasure probability of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant alpha(epsilon, t) for standard irregular ensembles. The dominant difference alpha(epsilon, t)/n can be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using alpha(epsilon, t) is accurate even for small blocklengths.

DOI： 10.1109/TIT.2012.2216252

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

In statistical physics and information theory, while asymptotic behavior of the partition function is often of our primary interest, the most of works are dedicated to analysis of the exponent of the partition function. In our previous paper on sparse random factor graph ensembles, we show that the exponent of the expectation of the partition function is represented as the minimum of the Bethe free energy of the small averaged graph by using the method of types. In this paper, we present a general framework to study more precise asymptotic behaviors of the partition function, using the central approximation in conjunction with the method of types.

DOI： 10.1109/ISIT.2012.6283556

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Recently, Vontobel showed the relationship between Bethe free energy and annealed free energy for protograph factor graph ensembles. In this paper, annealed free energy of any random regular factor graph ensembles are connected to Bethe free energy. The annealed free energy is expressed as the solution of maximization problem whose stationary condition coincides with equations of belief propagation since the contribution to partition function of particular type of variable and factor nodes has similar form of minus Bethe free energy. It gives simple derivation of quenched free energy by using the replica method. It implies equivalence of the replica and cavity methods for any random irregular factor graph ensembles. As consequence, it is shown that the replica symmetric solution and annealed free energy are equal for regular ensemble.

DOI： 10.1109/ISIT.2011.6033907

Web of Science

researchmap

DOI： 10.1109/ISIT.2011.6034145

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

A method of channel polarization, proposed by Arikan, allows us to construct efficient capacity-achieving channel codes. In the original work, binary input discrete memoryless channels are considered. A special case of q-ary channel polarization is considered by Sasoglu, Telatar, and Arikan. In this paper, we consider more general channel polarization on q-ary channels. We further show explicit constructions using Reed-Solomon codes, on which asymptotically fast channel polarization is induced.

DOI： 10.1109/ISIT.2010.5513568

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

A rate-dependent upper bound of the best achievable block error probability of polar codes with successive-cancellation decoding is derived.

DOI： 10.1109/ISIT.2010.5513574

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Polar codes, introduced by Arikan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.

DOI： 10.1109/CIG.2010.5592755

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC  

Polar coding, proposed by Arikan, makes it possible to construct capacity-achieving codes for symmetric binary-input discrete memoryless channels, with low encoding and decoding complexity. Complexity of the originally proposed code construction method, however, grows exponentially in the blocklength unless a channel is the binary erasure channel. Recently, the authors have proposed a new capacity-achieving code construction method with linear complexity in the blocklength for arbitrary symmetric binary-input memoryless channels. In this letter, we evaluate performance of polar codes designed with the new construction method, and compare it with that of the codes constructed with another heuristic method with linear complexity proposed by Arikan.

DOI： 10.1109/LCOMM.2009.090428

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding is considered. The average bit error probability of an irregular LDPC code ensemble after a fixed number of iterations converges to a limit, which is calculated via density evolution, as the blocklength n tends to infinity. The difference between the bit error probability with blocklength ii and the large-blocklength limit behaves asymptotically like alpha/n, where the coefficient alpha depends on the ensemble, the number of iterations and the erasure probability of the BEC. In [1], alpha is calculated for regular ensembles. In this paper, alpha for irregular expurgated ensembles is derived. It is demonstrated that convergence of numerical estimates of alpha to the analytic result is significantly fast for irregular unexpurgated ensembles.

DOI： 10.1109/ISIT.2009.5206063

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Channel polarization is a method of constructing capacity achieving codes for symmetric binary-input discrete memoryless channels (B-DMCs) [1]. In the original paper, the construction complexity is exponential in the blocklength. In this paper, a new construction method for arbitrary symmetric binary memoryless channel (B-MC) with linear complexity in the blocklength is proposed. Furthermore, new upper bound and lower bound of the block error probability of polar codes are derived for the BEC and arbitrary symmetric B-MC, respectively.

DOI： 10.1109/ISIT.2009.5205857

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. Furthermore, a gap between the bit error probability after finite number of iterations for finite block length n and that for infinite block length is asymptotically alpha/n, where alpha denotes a specific constant determined by a degree distribution, a number of iterations and erasure probability. Our main result is to derive an efficient algorithm for calculating alpha for regular ensembles.

DOI： 10.1109/ISIT.2008.4595026

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Wanner graph but only a neighborhood graph of fixed depth preferred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding.
The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.

DOI： 10.1109/TURBOCODING.2008.4658691

Web of Science

researchmap

Event date： 2011.11 - 2011.12

Presentation type：Oral presentation (invited, special)  

researchmap

Event date： 2011.3

Presentation type：Oral presentation (invited, special)  

researchmap

Event date： 2011.2

Presentation type：Oral presentation (invited, special)  

researchmap

Event date： 2010.9

Presentation type：Oral presentation (invited, special)  

researchmap