NDLI: Probabilistic rank and matrix rigidity

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

Recent trends in decentralized cryptocurrencies (invited talk)

Twenty (simple) questions

Learning from untrusted data

New hardness results for routing on disjoint paths

Strongly refuting random CSPs below the spectral threshold

Bernoulli factories and black-box reductions in mechanism design

Faster space-efficient algorithms for subset sum and k-sum

Explicit, almost optimal, epsilon-balanced codes

Exponential separation of quantum communication and classical information

Uniform sampling through the Lovasz local lemma

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs

Pseudorandomness of ring-LWE for any ring and modulus

Removal lemmas with polynomial bounds

The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

A polynomial restriction lemma with applications

An SDP-based algorithm for linear-sized spectral sparsification

A time- and message-optimal distributed algorithm for minimum spanning trees

Complexity of short Presburger arithmetic

Efficient empirical revenue maximization in single-parameter auction environments

Approximate near neighbors for general symmetric norms

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

Efficient quantum tomography II

The limitations of optimization from samples

DecreaseKeys are expensive for external memory priority queues

Improved non-malleable extractors, non-malleable codes and independent source extractors

Finding approximate local minima faster than gradient descent

Addition is exponentially harder than counting for shallow monotone circuits

Why prices need algorithms (invited talk)

Kolmogorov complexity version of Slepian-Wolf coding

Beating 1-1/e for ordered prophets

A simpler and faster strongly polynomial algorithm for generalized flow maximization

Sum of squares lower bounds for refuting any CSP

Simple mechanisms for subadditive buyers via duality

Homomorphisms are a good basis for counting small subgraphs

Deciding parity games in quasipolynomial time

Compression of quantum multi-prover interactive proofs

Approximate counting, the Lovasz local lemma, and inference in graphical models

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

Non-interactive delegation and batch NP verification from standard computational assumptions

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

On independent sets, 2-to-2 games, and Grassmann graphs

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

Low rank approximation with entrywise $l_{1}-norm$ error

Distributed exact shortest paths in sublinear time

Linear matroid intersection is in quasi-NC

The menu-size complexity of revenue approximation

Algorithmic discrepancy beyond partial coloring

Quantum entanglement, sum of squares, and the log rank conjecture

Approximate modularity revisited

Set similarity search beyond MinHash

Towards optimal two-source extractors and Ramsey graphs

Katyusha: the first direct acceleration of stochastic gradient methods

Strongly exponential lower bounds for monotone computation

Optimizing tree pattern queries: why cutting is not enough (invited talk)

Synchronization strings: codes for insertions and deletions approaching the Singleton bound

Kernel-based methods for bandit convex optimization

Finding even cycles faster via capped k-walks

Information-theoretic thresholds from the cavity method

Stability of service under time-of-use pricing

Lossy kernelization

A weighted linear matroid parity algorithm

Hardness amplification for entangled games via anchoring

Real stable polynomials and matroids: optimization and counting

Local max-cut in smoothed polynomial time

Average-case fine-grained hardness

Online and dynamic algorithms for set cover

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Probabilistic rank and matrix rigidity

An adaptive sublinear-time block sparse fourier transform

Exponential separations in the energy complexity of leader election

Randomized polynomial time identity testing for noncommutative circuits

Communication complexity of approximate Nash equilibria

Geodesic walks in polytopes

Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

Trace reconstruction with $exp(O(n^{1/3}))$ samples

Decremental single-source reachability in planar digraphs

Non-malleable codes and extractors for small-depth circuits, and affine functions

A strongly polynomial algorithm for bimodular integer linear programming

Formula lower bounds via the quantum method

Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk)

The computational complexity of ball permutations

A generalization of permanent inequalities and applications in counting and optimization

Algorithms for stable and perturbation-resilient problems

Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model

Online service with delay

How well do local algorithms solve semidefinite programs?

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

Streaming symmetric norms via measure concentration

On the complexity of local distributed graph problems

Holographic algorithm with matchgates is universal for planar #CSP over boolean domain

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria

A reverse Minkowski theorem

A quantum linearity test for robustly verifying entanglement

Optimal mean-based algorithms for trace reconstruction

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy

Subquadratic submodular function minimization

Fast convergence of learning in games (invited talk)

The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling

Area-convexity, $l_{&infty;}$ regularization, and undirected multicommodity flow

Pseudodeterministic constructions in subexponential time

Sampling random spanning trees faster than matrix multiplication

Efficient massively parallel methods for dynamic programming

Provable learning of noisy-OR networks

Fully-dynamic minimum spanning forest with improved worst-case update time

Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)

Time-space hardness of learning sparse parities

The next 700 network programming languages (invited talk)

Practical post-quantum key agreement from generic lattices (invited talk)

Probabilistic rank and matrix rigidity

Content Provider	ACM Digital Library
Author	Williams, Ryan Alman, Josh
Abstract	We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measure the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds. The most interesting outcomes are: The Walsh-Hadamard Transform is Not Very Rigid. We give surprising upper bounds on the rigidity of a family of matrices whose rigidity has been extensively studied, and was conjectured to be highly rigid. For the $2^{n}$ Ã $2^{n}$ Walsh-Hadamard transform $H_{n}$ (a.k.a. Sylvester matrices, a.k.a. the communication matrix of Inner Product modulo 2), we show how to modify only 2Îµ n entries in each row and make the rank of $H_{n}$ drop below 2n(1â $Î©(Îµ^{2}/log(1/Îµ)))},$ for all small Îµ > 0, over any field. That is, it is not possible to prove arithmetic circuit lower bounds on Hadamard matrices such as $H_{n},$ via L.Â Valiantâ s matrix rigidity approach. We also show non-trivial rigidity upper bounds for $H_{n}$ with smaller target rank. Matrix Rigidity and Threshold Circuit Lower Bounds. We give new consequences of rigid matrices for Boolean circuit complexity. First, we show that explicit n Ã n Boolean matrices which maintain rank at least 2(logn)1â Î´ after $n^{2}/2^{(logn)^{Î´/2}}$ modified entries (over any field, for any Î´ > 0) would yield an explicit function that does not have sub-quadratic-size $AC^{0}$ circuits with two layers of arbitrary linear threshold gates. Second, we prove that explicit 0/1 matrices over the reals which are modestly more rigid than the best known rigidity lower bounds for sign-rank would imply exponential-gate lower bounds for the infamously difficult class of depth-two linear threshold circuits with arbitrary weights on both layers. In particular, we show that matrices defined by these seemingly-difficult circuit classes actually have low probabilistic rank and sign-rank, respectively. An Equivalence Between Communication, Probabilistic Rank, and Rigidity. It has been known since Razborov [1989] that explicit rigidity lower bounds would resolve longstanding lower-bound problems in communication complexity, but it seemed possible that communication lower bounds could be proved without making progress on matrix rigidity. We show that for every function f which is randomly self-reducible in a natural way (the inner product mod 2 is an example), bounding the communication complexity of f (in a precise technical sense) is equivalent to bounding the rigidity of the matrix of f, via an equivalence with probabilistic rank. .
Starting Page	641
Ending Page	652
Page Count	12
File Format	PDF
ISBN	9781450345286
DOI	10.1145/3055399.3055484
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-06-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Threshold circuit Walsh-hadamard transform Matrix rigidity Probabilistic rank
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