PittsburghV1, Hal, Corpus, bibRecord, 000437

On the Spectral Properties of Symmetric Functions

Identifieur interne : 000437 ( Hal/Corpus ); précédent : 000436; suivant : 000438

On the Spectral Properties of Symmetric Functions

Auteurs : Anil Ada ; Omar Fawzi ; Raghav Kulkarni

Source :

RBID : Hal:hal-01505075

Abstract

We characterize the approximate monomial complexity, sign monomial complexity , and the approximate L 1 norm of symmetric functions in terms of simple combinatorial measures of the functions. Our characterization of the approximate L 1 norm solves the main conjecture in [AFH12]. As an application of the characterization of the sign monomial complexity, we prove a conjecture in [ZS09] and provide a characterization for the unbounded-error communication complexity of symmetric-xor functions.

Url:

https://hal.archives-ouvertes.fr/hal-01505075

Links to Exploration step

Hal:hal-01505075

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Spectral Properties of Symmetric Functions</title>
<author><name sortKey="Ada, Anil" sort="Ada, Anil" uniqKey="Ada A" first="Anil" last="Ada">Anil Ada</name>
<affiliation><hal:affiliation type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Fawzi, Omar" sort="Fawzi, Omar" uniqKey="Fawzi O" first="Omar" last="Fawzi">Omar Fawzi</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-35418" status="VALID">  <orgName>Laboratoire de l'Informatique du Parallélisme</orgName>
  <orgName type="acronym">LIP</orgName>
  <desc>    <address>      <addrLine>46 Allée d'Italie 69364 LYON CEDEX 07</addrLine>
      <country key="FR"></country>
    </address>
    <ref type="url">http://www.ens-lyon.fr/LIP/</ref>
  </desc>
  <listRelation>    <relation active="#struct-6818" type="direct"></relation>
    <relation active="#struct-194495" type="direct"></relation>
    <relation active="#struct-300009" type="direct"></relation>
    <relation active="#struct-301088" type="direct"></relation>
    <relation name="UMR5668" active="#struct-441569" type="direct"></relation>
  </listRelation>
<tutelles><tutelle active="#struct-6818" type="direct"><org type="institution" xml:id="struct-6818" status="VALID">          <idno type="IdRef">149154992</idno>
          <orgName>École normale supérieure - Lyon</orgName>
          <orgName type="acronym">ENS Lyon</orgName>
          <desc>            <address>              <addrLine>15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ens-lyon.eu/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-194495" type="direct"><org type="institution" xml:id="struct-194495" status="VALID">          <orgName>Université Claude Bernard Lyon 1</orgName>
          <orgName type="acronym">UCBL</orgName>
          <desc>            <address>              <addrLine>43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-lyon1.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301088" type="direct"><org type="institution" xml:id="struct-301088" status="VALID">          <orgName>Université de Lyon</orgName>
          <desc>            <address>              <addrLine>92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07</addrLine>
              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR5668" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Kulkarni, Raghav" sort="Kulkarni, Raghav" uniqKey="Kulkarni R" first="Raghav" last="Kulkarni">Raghav Kulkarni</name>
<affiliation><hal:affiliation type="institution" xml:id="struct-95440" status="VALID">  <orgName>Chennai Mathematical Institute [Inde]</orgName>
  <desc>    <address>      <addrLine>Plot H1, SIPCOT IT Park Padur PO, Siruseri 603103</addrLine>
      <country key="IN"></country>
    </address>
    <ref type="url">http://www.cmi.ac.in/</ref>
  </desc>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01505075</idno>
<idno type="halId">hal-01505075</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01505075</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01505075</idno>
<date when="2017-04-11">2017-04-11</date>
<idno type="wicri:Area/Hal/Corpus">000437</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">On the Spectral Properties of Symmetric Functions</title>
<author><name sortKey="Ada, Anil" sort="Ada, Anil" uniqKey="Ada A" first="Anil" last="Ada">Anil Ada</name>
<affiliation><hal:affiliation type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Fawzi, Omar" sort="Fawzi, Omar" uniqKey="Fawzi O" first="Omar" last="Fawzi">Omar Fawzi</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-35418" status="VALID">  <orgName>Laboratoire de l'Informatique du Parallélisme</orgName>
  <orgName type="acronym">LIP</orgName>
  <desc>    <address>      <addrLine>46 Allée d'Italie 69364 LYON CEDEX 07</addrLine>
      <country key="FR"></country>
    </address>
    <ref type="url">http://www.ens-lyon.fr/LIP/</ref>
  </desc>
  <listRelation>    <relation active="#struct-6818" type="direct"></relation>
    <relation active="#struct-194495" type="direct"></relation>
    <relation active="#struct-300009" type="direct"></relation>
    <relation active="#struct-301088" type="direct"></relation>
    <relation name="UMR5668" active="#struct-441569" type="direct"></relation>
  </listRelation>
<tutelles><tutelle active="#struct-6818" type="direct"><org type="institution" xml:id="struct-6818" status="VALID">          <idno type="IdRef">149154992</idno>
          <orgName>École normale supérieure - Lyon</orgName>
          <orgName type="acronym">ENS Lyon</orgName>
          <desc>            <address>              <addrLine>15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ens-lyon.eu/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-194495" type="direct"><org type="institution" xml:id="struct-194495" status="VALID">          <orgName>Université Claude Bernard Lyon 1</orgName>
          <orgName type="acronym">UCBL</orgName>
          <desc>            <address>              <addrLine>43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-lyon1.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301088" type="direct"><org type="institution" xml:id="struct-301088" status="VALID">          <orgName>Université de Lyon</orgName>
          <desc>            <address>              <addrLine>92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07</addrLine>
              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR5668" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Kulkarni, Raghav" sort="Kulkarni, Raghav" uniqKey="Kulkarni R" first="Raghav" last="Kulkarni">Raghav Kulkarni</name>
<affiliation><hal:affiliation type="institution" xml:id="struct-95440" status="VALID">  <orgName>Chennai Mathematical Institute [Inde]</orgName>
  <desc>    <address>      <addrLine>Plot H1, SIPCOT IT Park Padur PO, Siruseri 603103</addrLine>
      <country key="IN"></country>
    </address>
    <ref type="url">http://www.cmi.ac.in/</ref>
  </desc>
</hal:affiliation>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We characterize the approximate monomial complexity, sign monomial complexity , and the approximate L 1 norm of symmetric functions in terms of simple combinatorial measures of the functions. Our characterization of the approximate L 1 norm solves the main conjecture in [AFH12]. As an application of the characterization of the sign monomial complexity, we prove a conjecture in [ZS09] and provide a characterization for the unbounded-error communication complexity of symmetric-xor functions.</div>
</front>
</TEI>
<hal api="V3">          <titleStmt>            <title xml:lang="en">On the Spectral Properties of Symmetric Functions</title>
            <author role="aut">              <persName>                <forename type="first">Anil</forename>
                <surname>Ada</surname>
              </persName>
              <idno type="halauthorid">1525529</idno>
              <affiliation ref="#struct-67135"></affiliation>
            </author>
            <author role="aut">              <persName>                <forename type="first">Omar</forename>
                <surname>Fawzi</surname>
              </persName>
              <idno type="halauthorid">804555</idno>
              <affiliation ref="#struct-35418"></affiliation>
            </author>
            <author role="aut">              <persName>                <forename type="first">Raghav</forename>
                <surname>Kulkarni</surname>
              </persName>
              <idno type="halauthorid">156558</idno>
              <affiliation ref="#struct-95440"></affiliation>
            </author>
            <editor role="depositor">              <persName>                <forename>Omar</forename>
                <surname>Fawzi</surname>
              </persName>
              <email type="md5">c5f7353a4e3056ada30627bddf1eb76b</email>
              <email type="domain">ens-lyon.fr</email>
            </editor>
          </titleStmt>
          <editionStmt>            <edition n="v1" type="current">              <date type="whenSubmitted">2017-04-11 08:25:09</date>
              <date type="whenModified">2017-06-15 09:09:18</date>
              <date type="whenReleased">2017-04-11 09:37:38</date>
              <date type="whenProduced">2017-04-11</date>
              <date type="whenEndEmbargoed">2017-04-11</date>
              <ref type="file" target="https://hal.archives-ouvertes.fr/hal-01505075/document">                <date notBefore="2017-04-11"></date>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal.archives-ouvertes.fr/hal-01505075/file/sym.pdf">                <date notBefore="2017-04-11"></date>
              </ref>
            </edition>
            <respStmt>              <resp>contributor</resp>
              <name key="461366">                <persName>                  <forename>Omar</forename>
                  <surname>Fawzi</surname>
                </persName>
                <email type="md5">c5f7353a4e3056ada30627bddf1eb76b</email>
                <email type="domain">ens-lyon.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>            <distributor>CCSD</distributor>
            <idno type="halId">hal-01505075</idno>
            <idno type="halUri">https://hal.archives-ouvertes.fr/hal-01505075</idno>
            <idno type="halBibtex">ada:hal-01505075</idno>
            <idno type="halRefHtml">2017</idno>
            <idno type="halRef">2017</idno>
          </publicationStmt>
          <seriesStmt>            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="INSMI">CNRS-INSMI - INstitut des Sciences Mathématiques et de leurs Interactions</idno>
            <idno type="stamp" n="LIP">Laboratoire de l'Informatique du Parallélisme</idno>
            <idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
            <idno type="stamp" n="ENS-LYON">École Normale Supérieure de Lyon</idno>
            <idno type="stamp" n="INRIA2017">INRIA2017</idno>
          </seriesStmt>
          <notesStmt></notesStmt>
          <sourceDesc>            <biblStruct>              <analytic>                <title xml:lang="en">On the Spectral Properties of Symmetric Functions</title>
                <author role="aut">                  <persName>                    <forename type="first">Anil</forename>
                    <surname>Ada</surname>
                  </persName>
                  <idno type="halauthorid">1525529</idno>
                  <affiliation ref="#struct-67135"></affiliation>
                </author>
                <author role="aut">                  <persName>                    <forename type="first">Omar</forename>
                    <surname>Fawzi</surname>
                  </persName>
                  <idno type="halauthorid">804555</idno>
                  <affiliation ref="#struct-35418"></affiliation>
                </author>
                <author role="aut">                  <persName>                    <forename type="first">Raghav</forename>
                    <surname>Kulkarni</surname>
                  </persName>
                  <idno type="halauthorid">156558</idno>
                  <affiliation ref="#struct-95440"></affiliation>
                </author>
              </analytic>
              <monogr>                <imprint></imprint>
              </monogr>
              <idno type="arxiv">1704.03176</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>            <langUsage>              <language ident="en">English</language>
            </langUsage>
            <textClass>              <classCode scheme="halDomain" n="info.info-cc">Computer Science [cs]/Computational Complexity [cs.CC]</classCode>
              <classCode scheme="halDomain" n="math.math-fa">Mathematics [math]/Functional Analysis [math.FA]</classCode>
              <classCode scheme="halTypology" n="UNDEFINED">Preprints, Working Papers, ...</classCode>
            </textClass>
            <abstract xml:lang="en">We characterize the approximate monomial complexity, sign monomial complexity , and the approximate L 1 norm of symmetric functions in terms of simple combinatorial measures of the functions. Our characterization of the approximate L 1 norm solves the main conjecture in [AFH12]. As an application of the characterization of the sign monomial complexity, we prove a conjecture in [ZS09] and provide a characterization for the unbounded-error communication complexity of symmetric-xor functions.</abstract>
          </profileDesc>
        </hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/Hal/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000437 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 000437 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    Hal
   |étape=   Corpus
   |type=    RBID
   |clé=     Hal:hal-01505075
   |texte=   On the Spectral Properties of Symmetric Functions
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

On the Spectral Properties of Symmetric Functions

On the Spectral Properties of Symmetric Functions

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri