NDLI: On the size of homogeneous and of depth four formulas with low individual degree

Please wait, while we are loading the content...

Almost tight bounds for eliminating depth cycles in three dimensions

Constant-round interactive proofs for delegating computation

Complexity theoretic limitations on learning halfspaces

Lift-and-round to improve weighted completion time on unrelated machines

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Optimal principal component analysis in distributed and streaming models

Two-source dispersers for polylogarithmic entropy and improved ramsey graphs

Parallel exhaustive search without coordination

A tight space bound for consensus

Cell-probe lower bounds for dynamic problems via a new communication model

Algorithmic Bayesian persuasion

Distributed (∆+1)-coloring in sublogarithmic rounds

Fault tolerant subgraph for single source reachability: generic and optimal

Improved approximation for node-disjoint paths in planar graphs

Near-optimal small-depth lower bounds for small distance connectivity

Reed-Muller codes achieve capacity on erasure channels

Tight bounds for single-pass streaming complexity of the set cover problem

Bipartite perfect matching is in quasi-NC

Semidefinite programs on sparse random graphs and their application to community detection

Separations in query complexity using cheat sheets

A duality based unified approach to Bayesian mechanism design

Exponential separation of communication and external information

A polynomial lower bound for testing monotonicity

Algebraic attacks against random local functions and their countermeasures

Geometric median in nearly linear time

Candidate hard unique game

A cost function for similarity-based hierarchical clustering

A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies

Repairing Reed-solomon codes

Weighted low rank approximations with provable guarantees

Non-malleable extractors and codes, with their many tampered extensions

Beyond matroids: secretary problem and prophet inequality with general constraints

The 4/3 additive spanner exponent is tight

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

The sample complexity of auctions with side information

A lower bound for the distributed Lovász local lemma

Deterministic and probabilistic binary search in graphs

A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting

On the size of homogeneous and of depth four formulas with low individual degree

Explicit two-source extractors and resilient functions

Streaming algorithms for embedding and computing edit distance in the low distance regime

Exact algorithms via monotone local search

How robust are reconstruction thresholds for community detection?

Entangled simultaneity versus classical interactivity in communication complexity

Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders

Interactive compression for product distributions

Relating two property testing models for bounded degree directed graphs

Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations

Separating subadditive euclidean functionals

On the effect of randomness on planted 3-coloring models

The computational power of optimization in online learning

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

Efficiently decoding Reed-Muller codes from random errors

Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time

Extractors for sumset sources

Online matching: haste makes waste!

Deterministic decremental single source shortest paths: beyond the o(mn) bound

Do prices coordinate markets?

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Ramanujan coverings of graphs

Approximating connectivity domination in weighted bounded-genus graphs

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

Graph isomorphism in quasipolynomial time [extended abstract]

On approximating functions of the singular values in a stream

Basis collapse for holographic algorithms over all domain sizes

Sparsified Cholesky and multigrid solvers for connection laplacians

Classical verification of quantum proofs

Watch and learn: optimizing from revealed preferences feedback

Constant-rate coding for multiparty interactive communication is impossible

Algorithmic stability for adaptive data analysis

Watermarking cryptographic capabilities

Bounded degree cosystolic expanders of every dimension

Matrix rigidity of random toeplitz matrices

Instance optimal learning of discrete distributions

Maximizing determinants under partition constraints

New deterministic approximation algorithms for fully dynamic matching

A discrete and bounded envy-free cake cutting protocol for four agents

Contention resolution with log-logstar channel accesses

Enumerating parametric global minimum cuts by random interleaving

Routing under balance

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

Beating CountSketch for heavy hitters in insertion streams

Base collapse of holographic algorithms

Parallel algorithms for select and partition with noisy comparisons

Efficient quantum tomography

The price of anarchy in large games

Communication lower bounds for statistical estimation problems via a distributed data processing inequality

The fourier transform of poisson multinomial distributions and its algorithmic applications

Textbook non-malleable commitments

Separations in query complexity based on pointer functions

Sample-optimal tomography of quantum states

A size-free CLT for poisson multinomials and its applications

On the size of homogeneous and of depth four formulas with low individual degree

Content Provider	ACM Digital Library
Author	Tavenas, Sébastien Saha, Chandan Kayal, Neeraj
Abstract	Let r be an integer. Let us call a polynomial f as a multi-r-ic polynomial if the degree of f with respect to any variable is at most r (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output is syntactically forced to be a multi-r-ic polynomial and refer to these as multi-r-ic circuits. Specifically, first define the formal degree of a node a with respect to a variable x inductively as follows. For a leaf it is 1 if a is labelled with x and zero otherwise; for an internal node labelled with * (respectively +) it is the sum of (respectively the maximum of) the formal degrees of the children with respect to x. We call an arithmetic circuit as a multi-r-ic circuit if the formal degree of the output node with respect to any variable is at most r. We prove lower bounds for various subclasses of multi-r-ic circuits. .
Starting Page	626
Ending Page	632
Page Count	7
File Format	PDF
ISBN	9781450341325
DOI	10.1145/2897518.2897550
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Lower bounds Arithmetic circuits Iterated matrix multiplication Elementary symmetric polynomials Log product Individual degree Shifted partials
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in