NDLI: Affine projections of polynomials: extended abstract

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

Faster approximate multicommodity flow using quadratically coupled flows

Quantum money from hidden subspaces

The cell probe complexity of dynamic range counting

Polyhedral clinching auctions and the adwords polytope

Computing a nonnegative matrix factorization -- provably

Short proofs for the determinant identities

Solution of the propeller conjecture in $R^{3}$

From irreducible representations to locally decodable codes

Approximation algorithms for semi-random partitioning problems

Prior-free auctions with ordered bidders

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Fast matrix rank algorithms and applications

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Learning poisson binomial distributions

Competitive contagion in networks

Pseudorandom generators with long stretch and low locality from random local one-way functions

Routing in undirected graphs with constant congestion

Catching the k-NAESAT threshold

Tight bounds for distributed functional monitoring

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities

Monotone expansion

Multi-way spectral partitioning and higher-order cheeger inequalities

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks

Certifiable quantum dice: or, true random number generation secure against quantum adversaries

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

Matroid prophet inequalities

On identity testing of tensors, low-rank recovery and compressed sensing

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space

2log1-ε n hardness for the closest vector problem with preprocessing

Folded codes from function field towers and improved optimal rate list decoding

A near-linear time ε-approximation algorithm for geometric bipartite matching

On the limits of black-box reductions in mechanism design

Tight bounds for monotone switching networks via fourier analysis

Nearly optimal sparse fourier transform

Separating multilinear branching programs and formulas

On vertex sparsifiers with Steiner nodes

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Finding red balloons with split contracts: robustness to individuals' selfishness

Characterizing pseudoentropy and simplifying pseudorandom generator constructions

Improving christofides' algorithm for the s-t path TSP

Complexity of counting CSP with complex weights

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance

Rational proofs

Nearly complete graphs decomposable into large induced matchings and their applications

Many sparse cuts via higher eigenvalues

Multiparty computation secure against continual memory leakage

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Span programs for functions with constant-sized 1-certificates: extended abstract

Online matching with concave returns

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity

A new point of NP-hardness for unique games

Subspace evasive sets

Using petal-decompositions to build a low stretch spanning tree

Budget feasible mechanism design: from prior-free to bayesian

Interactive information complexity

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars

Reconstruction of depth-4 multilinear circuits with top fan-in 2

Approximation algorithms and hardness of integral concurrent flow

Making polynomials robust to noise

An analysis of one-dimensional schelling segregation

Design extractors, non-malleable condensers and privacy amplification

Multiplying matrices faster than coppersmith-winograd

The freezing threshold for k-colourings of a random graph

Tight time-space tradeoff for mutual exclusion

Minimax option pricing meets black-scholes in the limit

Probabilistic existence of rigid combinatorial structures

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

Beating randomized response on incoherent matrices

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

Hypercontractivity, sum-of-squares proofs, and their applications

Edge transitive ramanujan graphs and symmetric LDPC good codes

Improved smoothed analysis of multiobjective optimization

An algorithmic characterization of multi-dimensional mechanisms

The multiparty communication complexity of set disjointness

Optimal online buffer scheduling for block devices

Affine projections of polynomials: extended abstract

Robust satisfiability of constraint satisfaction problems

A tight RMR lower bound for randomized mutual exclusion

A quantitative gibbard-satterthwaite theorem without neutrality

From query complexity to computational complexity

Matroids and integrality gaps for hypergraphic steiner tree relaxations

Unconditional differentially private mechanisms for linear queries

Strict fibonacci heaps

Optimal private halfspace counting via discrepancy

Tight lower bounds for the online labeling problem

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

Affine projections of polynomials: extended abstract

Content Provider	ACM Digital Library
Author	Kayal, Neeraj
Abstract	An m-variate polynomial f is said to be an affine projection of some n-variate polynomial g if there exists an nm matrix A and an n-dimensional vector b such that f(x)=g(Ax+b). In other words, if f can be obtained by replacing each variable of g by an affine combination of the variables occurring in f, then it is said to be an affine projection of g. Some well known problems (such as the determinant versus permanent and matrix multiplication for example) are instances of this problem. Given f and g can we determine whether f is an affine projection of g? The intention of this paper is to understand the complexity of the corresponding computational problem: given polynomials f and g find A and b such that f=g(Ax+b), if such an (Ab) exists. We first show that this is an NP-hard problem. We then focus our attention on instances where g is a member of some fixed, well known family of polynomials so that the input consists only of the polynomial f(x) having m variables and degree d. We consider the situation where f(x) is given to us as a blackbox (i.e. for any point aFm we can query the blackbox and obtain f(a) in one step) and devise randomized algorithms with running time poly(mnd) in the following special cases. Firstly where g is the Permanent (respectively the Determinant) of an nxn matrix and A is of rank n2. Secondly where g is the sum of powers polynomial (respectively the sum of products polynomial), and A is a random matrix of the appropriate dimensions (also d should not be too small).
Starting Page	643
Ending Page	662
Page Count	20
File Format	PDF MP4
ISBN	9781450312455
DOI	10.1145/2213977.2214036
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Reconstruction Waring problem for polynomials Affine projection Permanent Determinant Depth three circuit Polynomial equivalence
Content Type	Audio 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