An improved list decoding algorithm for the second order Reed–Muller codes and its applications

We propose an algorithm which is an improved version of the Kabatiansky–Tavernier list decoding algorithm for the second order Reed–Muller code RM(2, m), of length n = 2 ^m , and we analyse its theoretical and practical complexity. This improvement allows a better theoretical complexity. Moreover, we conjecture another complexity which corresponds to the results of our simulations. This algorithm has the strong property of being deterministic and this fact drives us to consider some applications, like determining some lower bounds concerning the covering radius of the RM(2, m) code.     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

Applying sieving to the computation of quadratic class groups

We present a new algorithm for computing the ideal class group of an imaginary quadratic order which is based on the multiple polynomial version of the quadratic sieve factoring algorithm. Although no formal analysis is given, we conjecture that our algorithm has sub-exponential complexity, and computational experience shows that it is significantly faster in practice than existing algorithms.

     

Square classes of totally positive units

In this article, we investigate some conditions for a real cyclic extension K over Q to satisfy the property that every totally positive unit of K is a square. As an application, we give a partial answer to Taussky's conjecture. We then extend our result to real abelian extensions of certain type.     

An algorithm for testing Leopoldt's conjecture

Based on an elementary version of Leopoldt's conjecture due to Iwasawa and Sands we develop an algorithm for testing this conjecture in an arbitrary algebraic number field for any prime p. Using this algorithm we are able to prove Leopoldt's conjecture for several pure fields of degree 5 and 7. We also discuss relations with class numbers.     

A note on blow-up phenomena for mass critical nonlinear Schrödinger equation

In this paper, we mainly discuss the radial case for L² critical nonlinear Schrödinger equation with finite blow-up time. We describe that the solution may concentrate some points with different speeds. Furthermore, we give further research to the conjecture given by F. Merle and P. Raphael (2005) in [13] and we proved the conjecture for some cases.     

An algorithm for the difference between set covers

A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

On the multigraded Hilbert and Poincaré-Betti series and the Golod property of monomial rings

In this paper we study the multigraded Hilbert and Poincaré-Betti series of A=S/a, where S is the ring of polynomials in n indeterminates divided by the monomial ideal a. There is a conjecture about the multigraded Poincaré-Betti series by Charalambous and Reeves which they proved in the case where the Taylor resolution is minimal. We introduce a conjecture about the minimal A-free resolution of the residue class field and show that this conjecture implies the conjecture of Charalambous and Reeves and, in addition, gives a formula for the Hilbert series. Using Algebraic Discrete Morse theory, we prove that the homology of the Koszul complex of A with respect to x₁,…,x_n is isomorphic to a graded commutative ring of polynomials over certain sets in the Taylor resolution divided by an ideal r of relations. This leads to a proof of our conjecture for some classes of algebras A. We also give an approach for the proof of our conjecture via Algebraic Discrete Morse theory in the general case.The conjecture implies that A is Golod if and only if the product (i.e. the first Massey operation) on the Koszul homology is trivial. Under the assumption of the conjecture we finally prove that a very simple purely combinatorial condition on the minimal monomial generating system of a implies Golodness for A.     

Weak Leopoldt's conjecture for Hecke characters of imaginary quadratic fields

We give a proof of the weak Leopoldt's conjecture à la Perrin-Riou, under some technical condition, for the p-adic realizations of the motive associated to Hecke characters over an imaginary quadratic field K of class number 1, where p is a prime >3 and where the CM elliptic curve associated to the Hecke character has good reduction at the primes above p in K. This proof makes use of the 2-variable Iwasawa main conjecture proved by Rubin. Thus we prove the Jannsen conjecture for the above p-adic realizations for almost all Tate twists.     

On Complete Functions in Jucys-Murphy Elements

The problem of computing the class expansion of some symmetric functions evaluated in Jucys-Murphy elements appears in different contexts, for instance, in the computation of matrix integrals. Recently, Lassalle gave a unified algebraic method to obtain some induction relations on the coefficients in this kind of expansion. In this paper, we give a simple purely combinatorial proof of his result. Besides, using the same type of argument, we obtain new simpler formulas. We also prove an analogous formula in the Hecke algebra of (S _2n , H _n ) and use it to solve a conjecture of Matsumoto on the subleading term of orthogonal Weingarten function. Finally, we propose a conjecture for a continuous interpolation between both problems.     

The crystal structure on the set of Mirkovi?-Vilonen polytopes

In an earlier work, we proved that MV polytopes parameterize both Lusztig's canonical basis and the Mirkovi?-Vilonen cycles on the affine Grassmannian. Each of these sets has a crystal structure (due to Kashiwara-Lusztig on the canonical basis side and due to Braverman-Finkelberg-Gaitsgory on the MV cycles side). We show that these two crystal structures agree. As an application, we consider a conjecture of Anderson-Mirkovi? which describes the BFG crystal structure on the level of MV polytopes. We prove their conjecture for sln and give a counterexample for sp₆. Finally we explain how Kashiwara data can be recovered from MV polytopes.     

Lower bounds on the worst-case complexity of some oracle algorithms

To give a proper definition of the complexity of very general computational problems such as optimization problems over arbitrary independence systems or fixed-point problems for continuous functions, it is useful to consider the input for these problems as “oracles” R which can be called by the algorithms for some values x ∈ X and which then give back some information R(x) about x, e.g. whether x belongs to the independence system or the point into which x is mapped by the continuous function. A lower bound on the complexity of an algorithm using an oracle R is the number of calls on R in the worst case. Using this technique it is shown that there is no polynomial approximative algorithm for the maximization problem over a general independence system which has a better worst-case behaviour than the greedy algorithm. Moreover several formalizations of the problem of approximating a fixed point of a continuous function are considered, and it is shown that none of these problems can be solved by a bounded algorithm.     

Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio

The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within at most a factor of 2. We consider the problem of finding among these tours the one that gives the closest approximation, i.e. the minimum-weight double-tree shortcutting. Previously, we gave an efficient algorithm for this problem, and carried out its experimental analysis. In this paper, we address the related question of the worst-case approximation ratio for the minimum-weight double-tree shortcutting method. In particular, we give lower bounds on the approximation ratio in some specific metric spaces: the ratio of 2 in the discrete shortest path metric, 1.622 in the planar Euclidean metric, and 1.666 in the planar Minkowski metric. The first of these lower bounds is tight; we conjecture that the other two bounds are also tight, and in particular that the minimum-weight double-tree method provides a 1.622-approximation for planar Euclidean TSP.     

Explicit Heegner points: Kolyvagin's conjecture and non-trivial elements in the Shafarevich-Tate group

Kolyvagin used Heegner points to associate a system of cohomology classes to an elliptic curve over Q and conjectured that the system contains a non-trivial class. His conjecture has profound implications on the structure of Selmer groups. We provide new computational and theoretical evidence for Kolyvagin's conjecture. More precisely, we explicitly approximate Heegner points over ring class fields and use these points to give evidence for the conjecture for specific elliptic curves of rank two. We explain how Kolyvagin's conjecture implies that if the analytic rank of an elliptic curve is at least two then the Zp-corank of the corresponding Selmer group is at least two as well. We also use explicitly computed Heegner points to produce non-trivial classes in the Shafarevich-Tate group.     

The negative answer to Kameko's conjecture on the hit problem

The goal of this paper is to give a negative answer to Kameko's conjecture on the hit problem stating that the cardinal of a minimal set of generators for the polynomial algebra Pk, considered as a module over the Steenrod algebra A, is dominated by an explicit quantity depending on the number of the polynomial algebra's variables k. The conjecture was shown by Kameko himself for k?3 in his PhD thesis in the Johns Hopkins University in 1990, and recently proved by us and Kameko for k=4. However, we claim that it turns out to be wrong for any k>4.In order to deny Kameko's conjecture we study a minimal set of generators for A-module Pk in some so-call generic degrees. What we mean by generic degrees is a bit different from that of other authors in the fields such as Crabb-Hubbuck, Nam, Repka-Selick, Wood …We prove an inductive formula for the cardinal of the minimal set of generators in these generic degrees when the number of the variables, k, increases. As an immediate consequence of this inductive formula, we recognize that Kameko's conjecture is no longer true for any k>4.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

On the quiver Grassmannian in the acyclic case

Let A be the path algebra of a quiver Q with no oriented cycle. We study geometric properties of the Grassmannians of submodules of a given A-module M. In particular, we obtain some sufficient conditions for smoothness, polynomial cardinality and we give different approaches to Euler characteristics. Our main result is the positivity of Euler characteristics when M is an exceptional module. This solves a conjecture of Fomin and Zelevinsky for acyclic cluster algebras.     

20 Years of Negami’s Planar Cover Conjecture

In 1988, Seiya Negami published a conjecture stating that a graph G has a finite planar cover (i.e. a homomorphism from some planar graph onto G which maps the vertex neighbourhoods bijectively) if and only if G embeds in the projective plane. Though the “if” direction is easy, and over ten related research papers have been published during the past 20 years of investigation, this beautiful conjecture is still open in 2008. We give a short accessible survey on Negami’s conjecture and all the (so far) published partial results, and outline some further ideas to stimulate future research towards solving the conjecture.     

On the direct sum conjecture

We prove the direct sum conjecture for various sets of systems of bilinear forms. Our results depend on a priori knowledge of the complexity of at least one of the direct summands and its underlying algebraic structure. We also briefly survey some previous results concerning the complexity and structure of minimal algorithms for various direct sum systems.