Michael E Saks

Ontology type: schema:Person     

Person Info


Michael E



Publications in SciGraph latest 50 shown

  • 2020-03-04 An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function in COMBINATORICA
  • 2018-04-25 Online Labeling: Algorithms, Lower Bounds and Open Questions in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2016-04-22 Backtracking Based k-SAT Algorithms in ENCYCLOPEDIA OF ALGORITHMS
  • 2016-01-11 Composition limits and separating examples for some boolean function complexity measures in COMBINATORICA
  • 2015-04-17 Special issue “Conference on Computational Complexity 2014” Guest Editor’s Foreword in COMPUTATIONAL COMPLEXITY
  • 2015-02-26 Backtracking Based k-SAT Algorithms in ENCYCLOPEDIA OF ALGORITHMS
  • 2014 Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • 2013 On Randomized Online Labeling with Polynomially Many Labels in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • 2012 On Online Labeling with Polynomially Many Labels in ALGORITHMS – ESA 2012
  • 2010-05-17 Lower Bounds on the Randomized Communication Complexity of Read-Once Functions in COMPUTATIONAL COMPLEXITY
  • 2010 Local Property Reconstruction and Monotonicity in PROPERTY TESTING
  • 2009-07-07 An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times in ALGORITHMICA
  • 2008 Backtracking Based k-SAT Algorithms in ENCYCLOPEDIA OF ALGORITHMS
  • 2005 Three Optimal Algorithms for Balls of Three Colors in STACS 2005
  • 2004-07 A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks in COMBINATORICA
  • 2004 A Lower Bound on the Competitive Ratio of Truthful Auctions in STACS 2004
  • 2003-06 Complexity of some arithmetic problems for binary polynomials in COMPUTATIONAL COMPLEXITY
  • 2000-11 Exponential lower bounds for depth three Boolean circuits in COMPUTATIONAL COMPLEXITY
  • 1999 Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families in RANDOMIZATION, APPROXIMATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • 1999 On List Update and Work Function Algorithms in ALGORITHMS - ESA’ 99
  • 1998-12 Low distortion euclidean embeddings of trees in ISRAEL JOURNAL OF MATHEMATICS
  • 1997-06 Efficient construction of a small hitting set for combinatorial rectangles in high dimension in COMBINATORICA
  • 1997 Sample spaces with small bias on neighborhoods and error-correcting communication protocols in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE
  • 1993-12 Low diameter graph decompositions in COMBINATORICA
  • 1993-09 Correlation inequalities and a conjecture for permanents in COMBINATORICA
  • 1992-09 Sharpening the LYM inequality in COMBINATORICA
  • 1991-12 On computing majority by comparisons in COMBINATORICA
  • 1989-09 Some extremal problems arising from discrete control processes in COMBINATORICA
  • 1989-06 A Dynamic location problem for graphs in COMBINATORICA
  • 1989-01 On the cover time of random walks on graphs in JOURNAL OF THEORETICAL PROBABILITY
  • 1988-03 Combinatorial representation and convex dimension of convex geometries in ORDER
  • 1987-06 The smallestn-uniform hypergraph with positive discrepancy in COMBINATORICA
  • 1985-09 Largest induced suborders satisfying the chain condition in ORDER
  • 1985-09 Unsolved problems in ORDER
  • 1985 The Information Theoretic Bound for Problems on Ordered Sets and Graphs in GRAPHS AND ORDER
  • 1984-12 A topological approach to evasiveness in COMBINATORICA
  • 1984-06 Balancing poset extensions in ORDER
  • 1984-06 A polyomino with no stochastic function in COMBINATORICA
  • 1983-03 Largest digraphs contained in alln-tournaments in COMBINATORICA
  • JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "affiliation": [
            "affiliation": {
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "type": "Organization"
            "isCurrent": true, 
            "type": "OrganizationRole"
            "id": "http://www.grid.ac/institutes/grid.266100.3", 
            "type": "Organization"
            "id": "http://www.grid.ac/institutes/grid.19006.3e", 
            "type": "Organization"
            "id": "http://www.grid.ac/institutes/grid.480024.a", 
            "type": "Organization"
            "id": "http://www.grid.ac/institutes/grid.116068.8", 
            "type": "Organization"
            "id": "http://www.grid.ac/institutes/grid.432790.b", 
            "type": "Organization"
        "familyName": "Saks", 
        "givenName": "Michael E", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
        "sdDataset": "persons", 
        "sdDatePublished": "2022-08-04T17:38", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/person/person_670.jsonl", 
        "type": "Person"

    Download the RDF metadata as:  json-ld nt turtle xml License info


    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/person.011520224512.05'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/person.011520224512.05'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/person.011520224512.05'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/person.011520224512.05'


    This table displays all metadata directly associated to this object as RDF triples.

    26 TRIPLES      10 PREDICATES      16 URIs      7 LITERALS      2 BLANK NODES

    Subject Predicate Object
    1 sg:person.011520224512.05 schema:affiliation Ndd29de1e20104f209beb722dfc2a57cd
    2 grid-institutes:grid.116068.8
    3 grid-institutes:grid.19006.3e
    4 grid-institutes:grid.266100.3
    5 grid-institutes:grid.432790.b
    6 grid-institutes:grid.480024.a
    7 schema:familyName Saks
    8 schema:givenName Michael E
    9 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
    10 schema:sdDatePublished 2022-08-04T17:38
    11 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    12 schema:sdPublisher N75b5dcbed75c4e8daa6f637ccfea529c
    13 sgo:license sg:explorer/license/
    14 sgo:sdDataset persons
    15 rdf:type schema:Person
    16 N75b5dcbed75c4e8daa6f637ccfea529c schema:name Springer Nature - SN SciGraph project
    17 rdf:type schema:Organization
    18 Ndd29de1e20104f209beb722dfc2a57cd schema:affiliation grid-institutes:grid.430387.b
    19 sgo:isCurrent true
    20 rdf:type schema:OrganizationRole
    21 grid-institutes:grid.116068.8 schema:Organization
    22 grid-institutes:grid.19006.3e schema:Organization
    23 grid-institutes:grid.266100.3 schema:Organization
    24 grid-institutes:grid.430387.b schema:Organization
    25 grid-institutes:grid.432790.b schema:Organization
    26 grid-institutes:grid.480024.a schema:Organization

    Preview window. Press ESC to close (or click here)